AcWing 3302. 表达式求值
原题链接
简单
作者:
刘杰
,
2024-01-09 10:56:34
,
所有人可见
,
阅读 41
//1.数值计算
// 字符优先级
//2.数值拆分
//2.1 数字 push x
//2.3 字符 ( push c
//2.4 字符 ) 先判断 字符 ( 之前的优先计算 push x
//2.5 计算优先级
//3 合并计算
//4 输出结果
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <stack>
using namespace std;
stack<int> num;
stack<char> op;
void eval(){
auto b = num.top(); num.pop();
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];
if(isdigit(c)){
int x= 0, j = i;
while(j < str.size() && 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() != '(') eval();
op.pop();
}
else{
while(op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
while(op.size()) eval();
cout << num.top() << endl;
return 0;
}