AcWing 454. 表达式求值
原题链接
中等
作者:
我要出去乱说
,
2021-02-08 21:19:05
,
所有人可见
,
阅读 353
#include <iostream>
#include <stack>
using namespace std;
const int MOD = 10000;
stack<int> nums;
stack<char> ops;
void eval() //记住这个通用写法,不管多少运算符都能支持
{
int b = nums.top(); nums.pop();
int a = nums.top(); nums.pop();
char c = ops.top(); ops.pop();
if (c == '+') nums.push((a + b) % MOD);
else nums.push((a * b) % MOD);
}
int main()
{
string expr;
cin >> expr;
for (int i = 0; expr[i]; i ++ )
{
char c = expr[i];
if (c >= '0' && c <= '9') //读取数串
{
int v = 0;
int j = i;
while (expr[j] && expr[j] >= '0' && expr[j] <= '9')
{
v = v * 10 + expr[j] - '0';
j ++ ;
}
nums.push(v);
i = j - 1;
}
else if (c == '+')
{
while (ops.size()) eval(); //加法优先级最低,当栈中存有其他符号时一起算光
ops.push(c);
}
else
{ //当栈中有乘号时先计算上一个乘法运算
while (ops.size() && ops.top() == '*') eval();
ops.push(c);
}
}
while (ops.size()) eval(); //遍历完后清算
cout << nums.top() % MOD << endl;
return 0;
}