AcWing 3302. (模拟栈)表达式求值
原题链接
中等
作者:
Avetre
,
2024-11-30 14:24:13
,
所有人可见
,
阅读 1
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
// opd(operand)存储操作数 opt(operator)存储操作符
int opd[N], opt[N], top1 = 0, top2 = 0;
bool precede(char top, char curr)
{
// 如果栈顶操作符优先级高于或等于当前操作符 返回true
// 为何是高于等于呢?因为减法和除法的操作数有先后顺序性 只是高于的话 会出现1-2+3<->1-(2+3)<->1-5的错误情况
if ((top == '*' || top == '/') && (curr == '+' || curr == '-'))
return true;
if ((top == '+' || top == '-') && (curr == '+' || curr == '-'))
return true;
if ((top == '*' || top == '/') && (curr == '*' || curr == '/'))
return true;
return false;
}
signed main()
{
string s;
cin >> s;
for (int i = 0; i < s.size(); i++)
{
// 处理数字
if (s[i] >= '0' && s[i] <= '9')
{
// 多位数
int x = 0;
while (i < s.size() && s[i] >= '0' && s[i] <= '9')
{
x = x * 10 + s[i] - '0';
i++;
}
opd[++top1] = x;
// 因为for循环中有i++ 所以这里要i-- 否则会跳过一个字符
i--;
}
// 处理操作符
else
{
// 左括号:直接入栈
if (s[i] == '(')
opt[++top2] = s[i];
// 右括号:弹出操作符栈中的操作符 并逐次从操作数栈中弹出两个数计算 直到遇到左括号
else if (s[i] == ')')
{
while (opt[top2] != '(')
{
int b = opd[top1--];
int a = opd[top1--];
if (opt[top2] == '+')
opd[++top1] = a + b;
else if (opt[top2] == '-')
opd[++top1] = a - b;
else if (opt[top2] == '*')
opd[++top1] = a * b;
else if (opt[top2] == '/')
opd[++top1] = a / b;
// 弹出操作符
top2--;
}
// 弹出左括号
top2--;
}
// 加减乘除
else
{
// 栈非空 且栈顶操作符不为左括号 且栈顶操作符优先级高于等于当前操作符 则弹出栈顶操作符 并计算
while (top2 && opt[top2] != '(' && precede(opt[top2], s[i]))
{
int b = opd[top1--];
int a = opd[top1--];
if (opt[top2] == '+')
opd[++top1] = a + b;
else if (opt[top2] == '-')
opd[++top1] = a - b;
else if (opt[top2] == '*')
opd[++top1] = a * b;
else if (opt[top2] == '/')
opd[++top1] = a / b;
// 弹出操作符
top2--;
}
// 当前操作符入栈
opt[++top2] = s[i];
}
}
}
// 处理栈中剩余操作符
while (top2)
{
int b = opd[top1--];
int a = opd[top1--];
if (opt[top2] == '+')
opd[++top1] = a + b;
else if (opt[top2] == '-')
opd[++top1] = a - b;
else if (opt[top2] == '*')
opd[++top1] = a * b;
else if (opt[top2] == '/')
opd[++top1] = a / b;
top2--;
}
// 操作数栈中剩下的唯一元素即为结果
cout << opd[top1] << endl;
return 0;
}