151. 表达式计算4
AcWing
来源151. 表达式计算4
栈模拟计算器表达式的计算
首先明确加减号的优先级低于乘除号，乘除号的优先级低于乘方号
stack<ll> nums;存放数stack<char> ops;存放符号
由于此题符号可能会出现不匹配的状况，所以我们进行字符串的补充，向字符串的前面加上str.size()个‘(‘，在字符串最后再加上一个‘)‘，因为我们是从左往右看的，就可以一定使所有计算都正常进行了
对于一个表达式，如果单看一个 +号 我们无法判断是否需要计算，因为我们不知道下一个符号的优先级，所以我们可以多个符号一起看
对于加减号，每当我们看遇见一个加减号，我就去找符号栈的栈顶，也就是离这个符号最近的符号，只要不是‘(‘，都进行计算前面的符号，因为我们知道，加减号级别最低，要放在最后计算，等算完我们再把当前加减号加入栈中
对于乘除号同理，乘除号往前看，看到和自己级别一样或比自己级别高的先算，然后把自己放入栈
对于乘方，往前找乘方，找到就算，然后加入栈
最后遍历到‘)‘，这使，从右往左，就可以放心算了，也就是一次把栈算完，模拟一下就明白了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
stack<int> nums;
stack<char> ops;
void cal(){
char c = ops.top();
ops.pop();
int a = nums.top();
nums.pop();
int b = nums.top();
nums.pop();
int res = 0;
if(c == ‘+‘) res = b + a;
else if(c == ‘-‘) res = b - a;
else if(c == ‘*‘) res = b * a;
else if(c == ‘/‘) res = b / a;
else{
res = 1;
while(a--){
res *= b;
}
}
nums.push(res);
}
int main(){
string str;
string left;
cin >> str;
for(int i = 0;i < str.size();i++) left += ‘(‘;
str = left + str + ‘)‘;
// cout << str;
for(int i = 0;i < str.size();i++){
if(str[i] <= ‘9‘ && str[i] >= ‘0‘){
int j = i, t = 0;
while(str[j] <= ‘9‘ && str[j] >= ‘0‘){//如果后面是数字，就找到这个数字
t = t * 10 + str[j] - ‘0‘;
j++;
}
i = j - 1;
nums.push(t);
}
else
{
char c = str[i];
if(c == ‘+‘ || c == ‘-‘){
if(c == ‘-‘ && !(str[i - 1] <= ‘9‘ && str[i - 1] >= ‘0‘ || str[i - 1] == ‘)‘)){
//如果是符号，且前面不是数字和‘)‘，那么一定是‘(‘，直接当成一个负数加入栈
int j = i + 1, t = 0;
while(str[j] <= ‘9‘ && str[j] >= ‘0‘){//如果后面是数字，就找到这个数字
t = t * 10 + str[j] - ‘0‘;
j++;
}
i = j - 1;
nums.push(-t);
if(str[i + 1] == ‘(‘) ops.push(c);
}
else{
while(ops.top() != ‘(‘) cal();
ops.push(c);
}
}else if(c == ‘*‘ || c == ‘/‘){
while(ops.top() == ‘*‘ || ops.top() == ‘/‘ || ops.top() == ‘^‘) cal();
ops.push(c);
}else if(c == ‘^‘){
while(ops.top() == ‘^‘) cal();
ops.push(c);
}else if(c == ‘)‘){
while(ops.top() != ‘(‘) cal();
ops.pop();
}else if(c == ‘(‘){
ops.push(c);
}
}
}
cout << nums.top() << endl;
return 0;
}