题目描述

给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值。
数据可能会出现括号情况，还有可能出现多余括号情况。如：1+((((((((1+(((3+2)

数据保证不会出现大于或等于$2^{31}$的答案。

数据可能会出现负数情况。如：3/(-5), 3/-5

数据保证不会出现指数为负数的情况。也就是不会有$2^{-5}$的情况

过程

本题大体是使用3302. 表达式求值的模板来进行的求解

1. 如何应对多余括号呢？
   – 如果是多余的左括号，我们的操作是直接入栈，不会有什么后果
   – 但是如果多余的是右括号，while(op.top() != '(') eval();，就会出错。
   所以，我们的预处理方法是：在输入的表达式前面加上表达式长度的左括号。保证左括号的数量一定大于右括号，这样面对右括号的操作就不会出错了。
2. 如何应对负数
   – 对于一个’-‘，如果’-‘出现在起始位置即i == 0，或者
   – 当前’-‘前面的字符既不是数字也不是右括号(这两种情况下’-‘都是作为运算符)，!isdigit(s[i-1]) && s[i-1] != ')'
   那就是作为负号而不是运算符。
3. 最后扫尾的时候，如何应对多余的左括号
   是左括号就跳过，否则就正常计算

while(!op.empty()){
    if(op.top() == '(')
        op.pop();
    else
        eval();
}

了解到指数运算有着左结合(即 a^b^c 解释为 (a^b)^c )和右结合(即 a^b^c 解释为 a^(b^c))之分
这里的代码是左结合

代码

#include<iostream>
#include<stack>
#include<unordered_map>
using namespace std;

// 指数运算'^' 的优先级在里面最高
unordered_map<char, int> pr = {{'+', 1}, {'-', 1}, {'*', 2}, {'/',2}, {'^', 3}};
stack<int> num;
stack<char> op;

void eval(){
    int b = num.top();
    num.pop();
    int a = num.top();
    num.pop();
    char c = op.top();
    op.pop();
    int res = 0;
    if(c == '+') res = a + b;
    else if(c == '-') res = a - b;
    else if(c == '*') res = a * b;
    else if(c == '/') res = a / b;
    else {
        res = 1;
        while(b--) res *= a;
    }
    num.push(res);
}

int main(){
    string s; cin >> s;
    string left="";
    for(int i = 0; i < s.size(); ++i) left += '(';
    s = left + s; // 在前面加左括号
    for(int i = 0; i < s.size(); ++i){
        char c = s[i];
        // 对数字和负数的操作
        if(isdigit(c) || c == '-' && (i == 0 || (!isdigit(s[i - 1]) && s[i - 1] != ')'))){ // 如果当前字符是数字，那就得把数抠出来 
            int sign = 1;
            if(c == '-'){
                sign = -1;
                i ++;// 跳过这个负号
                if (!isdigit(s[i])) op.push(c); // 处理-(-3)  -(-3+4)这种表达式
            }
            int x = 0;
            int j = i;
            while(j < s.size() && isdigit(s[j])){
                x = x * 10 + s[j ++] - '0';
            }
            i = j - 1;
            num.push(x * sign);
        }
        else if(c == '('){
            op.push(c);
        }
        else if(c == ')'){
            while(op.top() != '(') eval(); // 用末尾的运算符操作末尾的两个数
            op.pop(); // 将左括号弹出 
        }
        else{ // 一般运算符
            while(!op.empty() && pr[op.top()] >= pr[c]) eval(); 
            op.push(c);
        } 
    }

    while(!op.empty()){
        if(op.top() == '(') // 针对多余的左括号
            op.pop();
        else
            eval();
    }
    cout << num.top(); 
    return 0;
}