AcWing 3302. 表达式求值
原题链接
中等
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stack>
#include <unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
void cal()
{
int a = num.top();
num.pop();
int b = num.top();
num.pop();
char c = op.top();
op.pop();
int x;
if(c == '+')
x = a + b;
else if(c == '-')
x = b - a;
else if(c == '*')
x = a * b;
else
x = b / a;
num.push(x);
}
int main()
{
string str;
cin >> str;
unordered_map<char, int> pr{{'+',1},{'-',1},{'*',2},{'/',2}};
for(int i = 0; i < str.length(); i ++ )
{
auto c = str[i];
if(isdigit(c))
{
int x = 0, j = i;
while(j < str.length() && isdigit(str[j]))
{
x = x * 10 + str[j] - '0';
j ++ ;
}
i = j - 1;
num.push(x);
}
else if(c == '(')
{
op.push(c);
}
else if(c == ')')
{
while(op.top() != '(')
cal();
op.pop();
}
else
{
while(op.size() && op.top() != '(' && pr[op.top()] >= pr[c])
cal();
op.push(c);
}
}
while(op.size())
cal();
cout << num.top();
return 0;
}