中缀表达式求值-acwing

题目：

3302. 表达式求值 - AcWing题库

解析：模拟

2*10-1000+24-(5*3)+(3*2)

使用两种栈：

遍历：(暂时用it指向）

it ： 2 存入 num {2}

it：* 栈空，存入 op{*}

it：10 存入 num{2, 10}

it : - ：栈不空，比较优先级，前面字符是否>=后面的，*优先级> 当前未入栈 - ，弹出*计算，再压入 - op {- } num{20}

it : 1000 : 存入 num {20, 1000}

it : + : 栈栈不空， - == +（优先级）弹出 - 计算，然后+压入栈，num{-980} op{ + }

it：24 ：存入 num{-980, 24}

it - : 不空，比较优先级， + 和 - ,计算。 num{-956} op{-}

it : ( : 入栈 op{ '-', '(' }

it:5 存入 num{-956，5}

it:* 不空比较优先级：自然而然是*优先级高， op{ - , ( , * }

it 3: 存入 num {-956， 5， 3}

it ) : 计算括号内， num {-956,15} op {- , ( } => op{ - } " " ( "" 要弹出

it ; + 不空，- == +（优先级比较）计算 num {-971} op{ + }

it ( : 存入 op { +, ( }

it 3 : 存入 num {-971，3}

it * ：不空，优先级高，存入 op { +, ( , * }

it : 2 : 存入 num {-971，3，2}

it :) : 计算括号内， num{-971,6} op {+}

计算剩下的：op非空

num{-965} op{ }

代码1(unordered_map<char,int> pr 作优先级

#include<bits/stdc++.h>
using namespace std;stack<char> op;
stack<int> num;void eval() { // 弹出数字栈两个数，弹出字符栈，然后计算结果压入数字栈int a = num.top(); num.pop();int b = num.top(); num.pop();auto ch = op.top(); op.pop();switch(ch) {case '+' : num.push(b+a);break;case '-' : num.push(b-a);break;case '*' : num.push(b*a);break;case '/' : num.push(b/a);break;}
}int main() {//优先级关系unordered_map<char,int> pr = { {'+','1'}, {'-','1'}, {'*','2'}, {'/','2'} };string str;cin >> str;//遍历stringfor(int i = 0; i <str.size(); i ++) {auto c = str[i];//数字：例如 112if(isdigit(c) ) {int j = i, x = 0;while(j < str.size() && isdigit(str[j]) ) {x = x*10 + str[j++]-'0'; // 这里j有++}i = j-1; // i更新num.push(x);}else if(c=='(') op.push(str[i]);//右括号，先计算括号内else if(c==')') {while(op.top()!='(') eval();op.pop();}//当前字符为运算符//前面运算符和当前运算符比较优先级，前面优先级>= 先计算前面的优先else {// 非空且优先级底while(!op.empty() && pr[op.top()] >= pr[c] ) eval();//压入当前运算符 cop.push(c);}}// 没计算的运算符计算while(!op.empty()) eval();cout << num.top() << endl;return 0;
}