表达式计算(栈模拟)

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;
}
上一篇:C# 从零开始 vol.1


下一篇:关于 DevOps ,咱们聊的可能不是一回事[转]