AcWing 454. 表达式求值
原题链接
中等
作者:
ywt51
,
2023-06-01 22:45:12
,
所有人可见
,
阅读 131
算法1:两个栈分别维护数字和符号-模拟() $O(n)$
//先算和后算的问题
#include <bits/stdc++.h>
using namespace std;
string s;
stack<int> num; //遇到乘法就拿出两个数相乘,数字全部加到栈中,最后栈全部加起来
stack<char> op;
unordered_map<char, int> prio = {{'+', 1}, {'*', 2}};
void cal() {//拿出数字栈中的两个数字,以及栈顶的符号出来计算,结果再放会数字栈
int b = num.top(); num.pop();
int a = num.top(); num.pop();
char c = op.top(); op.pop();
if (c == '*') num.push(a * b % 10000);
else num.push(a + b % 10000);
}
int main() {
cin >> s;
for (int i = 0; i < s.size(); ++ i) {
if (s[i] >= '0' && s[i] <= '9') { //数字就加入栈中
int x = 0, j = i;
while (j < s.size() && s[j] >= '0' && s[j] <= '9')
x = x*10 + (s[j++] - '0');
num.push(x);
i = j-1;
} else { //栈顶元素的优先级高就可以进行计算了
while (op.size() && prio[op.top()] >= prio[s[i]]) cal();
op.push(s[i]);
}
}
while (op.size()) cal();
cout << num.top() % 10000;
return 0;
}
算法2:栈维护要计算的数字() $O(n)$
#include <bits/stdc++.h>
using namespace std;
const int N = 1E5+10;
int stk[N], tt = 1;
int x;
char op;
int main() {
cin >> stk[1];
while (cin >> op >> x) {
//读入的时候就是分离的,边读入边判断是否可以计算
if (op == '*') stk[tt] = x * stk[tt] % 10000;
else stk[++tt] = x;
}
int res = 0;
for (int i = 1; i <= tt; ++ i)
res = (res + stk[i]) % 10000;
cout << res;
return 0;
}
算法3:栈维护要计算的数字,变量记录上一个符号() $O(n)$
//如果是加减乘除都有的情况
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
stack<int> stk;
cin >> s;
int n = 0;
char op = '+';
for (int i = 0; i < s.size(); ++ i) {
if (s[i] >= '0' && s[i] <= '9')
n = n*10 + s[i] - '0';
if (s[i] == '+' || s[i] == '*' || i == s.size()-1) {
if (op == '*') stk.top() = stk.top() * n % 10000;
if (op == '+') stk.push(n);
n = 0;
op = s[i]; //记录上一个符号
}
}
int res = 0;
while (stk.size()) {
res = (res + stk.top()) % 10000;
stk.pop();
}
cout << res;
return 0;
}