AcWing 3302. 表达式求值

题目连接

https://www.acwing.com/problem/content/3305/

思路

我们用一个map记录不同符号的一个优先级，然后用两个栈分别记录数字和操作符，如果当前的符号是右括号，那么我们就得强制处理到左括号去，如果当前读到的是一个数字，那么我们直接把数字放入数字栈里面就好了，如果当前读到的是一个运算符，那么我们就得先处理栈中优先级大于等于当前运算符的一些运算，最后将当前的运算符加入到栈中，那么这个栈就一个运算符单调递增的一个栈，详情请看代码

代码

#include
using namespace std;

unordered_map pr{{'+',1},{'-',1},{'*',2},{'/',2}};

stack num;
stack op;

void eval(){
	int b = num.top();num.pop();
	int a = num.top();num.pop();
	char c = op.top();op.pop();
	if(c == '+') a += b;
	else if(c == '-') a -= b;
	else if(c == '*') a *= b;
	else if(c == '/') a /= b;
	num.push(a);
}

int main()
{
	string ch;
	cin>>ch;
	int n = ch.size();
	for(int i = 0;i  20-1000+24-15+6 如果不处理相等的话我们就多减去了一个6，少加了一个6
			while(op.size() && pr[op.top()] >= pr[ch[i]]) eval();
			op.push(ch[i]);//将当前的符号放进符号栈里面
		}
	}
	while(op.size()) 
		eval();
	cout