1 条题解

  • 0
    @ 2026-1-28 10:28:47
    #include <bits/stdc++.h>
    using namespace std;
    
    // [1] 优先级比较函数:判断栈顶运算符a与当前运算符b的优先级
    // 返回true表示a的优先级 >= b的优先级,需要弹出a;返回false表示a的优先级 < b的优先级,直接入栈b
    bool f(char a,char b){
        // [2] 规则:乘除(*/)优先级高于加减(+-)
        // 若栈顶是乘除,当前是加减 → a优先级更高,返回true(弹出a)
        // 其他情况(同优先级或a优先级更低)返回false(不弹出a)
    	if((b=='*' || b=='/') && (a=='+' || a=='-')){
    		return false;
    	}else{
    		return true;
    	}
    }
    
    int main(){
        // [3] s-存储输入的中缀表达式字符串
        string s;
    	cin>>s;
        // [4] v-运算符栈,用于存储待输出的运算符,控制优先级
    	stack<char> v;
    	
        // [5] 遍历中缀表达式的每个字符
    	for(int i=0;i<s.size();i++){
            // [6] 情况1:当前字符是操作数(数字/大小写字母),直接输出到后缀表达式
    		if((s[i]>='0' && s[i]<='9') || (s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z')){//数字字母直接展示 
    			cout<<s[i];
            // [7] 情况2:当前字符是右括号')',弹出栈顶运算符直到遇到左括号'('
    		}else if(s[i]==')'){//括号里面的先展示 
                // [8] 弹出栈顶并输出,直到栈顶是左括号
    			while(!v.empty() && v.top()!='('){
    				cout<<v.top();
    				v.pop();
    			}
                // [9] 弹出左括号'(',不输出(括号仅用于控制优先级,不加入后缀表达式)
    			v.pop();
            // [10] 情况3:当前字符是左括号'('或其他运算符(+-*/)
    		}else{
                // [11] 若栈为空、栈顶是左括号,或当前是左括号 → 直接入栈(左括号优先级最高,先入栈)
    			if(v.empty() || v.top()=='('||s[i]=='(') v.push(s[i]);
    			else{
                    // [12] 否则比较栈顶与当前运算符的优先级:若栈顶优先级 >= 当前,弹出栈顶并输出
                    // 直到栈空、栈顶是左括号,或栈顶优先级 < 当前
    				while(!v.empty() && f(v.top(),s[i]) && v.top()!='('){
    					cout<<v.top();
    					v.pop();
    				}
                    // [13] 将当前运算符入栈
    				v.push(s[i]);
    			}
    		}
    	}
        // [14] 遍历结束后,弹出栈中剩余的所有运算符并输出
    	while(!v.empty()){
    		cout<<v.top();
    		v.pop();
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    1260
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    3
    已通过
    1
    上传者