AcWing 3302. 表达式求值(个人理解+详细注释)
原题链接
简单
作者:
现代修士o_O
,
2021-04-26 11:31:09
,
所有人可见
,
阅读 216
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int> num;
stack<char> op;//符号栈 以(为分割点,最多存两个运算符-加减乘除,且该栈是优先级严格递增的单调栈
//因为符号的优先级只会对三个“数”有影响而三个数中间最多两个运算符。
//a * b + c
//a + b * c
//a * b * c
//a + b + c
void eval() // 取出两个数,一个运算符,得出一个数,将其放入数字栈
{
auto b = num.top(); num.pop();//a .. b 放入数字栈时,是先放入a再放入b的,按照栈先进后出的原则,b先取出来,再取a
auto a = num.top(); num.pop();
auto c = op.top(); op.pop();
int x;
if (c == '+') x = a + b;
else if (c == '-') x = a - b;
else if (c == '*') x = a * b;
else x = a / b;
num.push(x); // 结果放回数字栈
}
int main()
{
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; //运算符优先级
string str;
cin >> str;
for (int i = 0; i < str.size(); i ++ )
{
auto c = str[i];
//以下有四种可能,1:数字,2:左括号,3:右括号,4:运算符-加减乘除
if (isdigit(c))//如果是数字,则放进num数字栈里
{
int x = 0, j = i;
while (j < str.size() && isdigit(str[j])) //连续的数字取出来
x = x * 10 + str[j ++ ] - '0';
i = j - 1;// while 结束时 j要么指向str.size(),要么指向一个非数字的符号,为了配合for里的i ++ , i 取j - 1
num.push(x);
}
else if (c == '(') op.push(c); // 如果是左括号,则把左括号放入op操作栈中
else if (c == ')')//遇到右括号,则将括号内的数都算出来
{
while (op.top() != '(') eval(); //这时,op栈中'('之上最多有两个运算符 下面是加减之一,上面是乘除之一
op.pop();//while 停止时,op栈顶为'(',将其弹出
}
else // 否则都是加减乘除运算符了,注意维护单调运算符栈,严格单调递增!
{
while (op.size() && pr[op.top()] >= pr[c] ) eval();//若当前op栈不为空,而且栈顶运算符优先级不低于要加的运算符
// 例如 栈顶是*/ 而要加的是 */ 按照同级运算,从左到右的规则,自然要先算栈顶的*/
// 栈顶是*/ 而要加的是 +- 按照优先级运算高低,先算栈顶的*/
// 栈顶是+- 而要加的是 +- 按照同级运算,从左到右的规则,自然要先算栈顶的+-
// 而当栈顶是+- 而要加的是 */ 不满足单调递增。而且按照运算符优先级理当先算*/
// 但我们eval是算栈顶的运算符,所以就把该*/放入op栈中。
// 循环退出可以是由上述的不满足单调递增的情况引起的,那这个时候会放*/进去
// 同时,栈为空时也会退出循环。那这个时候,不管时*/ 还是+- 都可以放进去了,因为前面没有运算符限制它了
op.push(c);
}
}
while (op.size()) eval();//当op栈还不为空时,还剩最多两个运算符时,进行运算就ok了
//最终op栈为空,num栈会只剩一个数字,这个数字就是表达式运算的结果
cout << num.top() << endl;
return 0;
}