AcWing 3302. 数组模拟栈求解
原题链接
简单
作者:
hairrrrr
,
2021-03-26 20:29:03
,
所有人可见
,
阅读 311
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<unordered_map>
using namespace std;
const int N = 100010;
char op[N];
int num[N];
int tt1, tt2;
// 计算 num 栈顶两个元素的值
void eval()
{
// 注意 a 和 b 的顺序
int b = num[tt1--];
int a = num[tt1--];
char c = op[tt2--];
int x;
if(c == '+') x = a + b;
else if(c == '-') x = a - b;
else if(c == '*') x = a * b;
else x = a / b;
num[++tt1] = x;
}
int main(void)
{
string str;
cin >> str;
int len = str.length();
// 优先级
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
for(int i = 0; i < len; ++i)
{
char c = str[i];
if(isdigit(c))
{
int x = 0, j = i;
// 取出数字
while(j < len && isdigit(str[j]))
x = x * 10 + str[j++] - '0';
num[++tt1] = x;
// 更新 j,因为循环控制中还会 ++i,所以 i 更新为 j - 1
i = j - 1;
}
else if(c == '(')
op[++tt2] = '(';
else if(c == ')')
{
while(op[tt2] != '(') eval();
// 弹出 (
--tt2;
}
else
{
// 注意!!!:这里应该用循环且第三个条件为 >=
while(tt2 > 0 && op[tt2] != '(' && pr[op[tt2]] >= pr[c]) eval();
op[++tt2] = c;
}
}
while(tt2) eval();
cout << num[tt1] << endl;
return 0;
}