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;
}