1 条题解
-
0
#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
- 上传者