AcWing 3302. 表达式求值 (栈，运算符优先级)

浅浅的花香味﹌ 2024-05-08 06:17 146阅读 0赞

##### 题目 #####

给定一个表达式，其中运算符仅包含 +,-,\*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

**注意：**

数据保证给定的表达式合法。  
题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)\*(-(1+1)+2) 之类表达式均不会出现。  
题目保证表达式中所有数字均为正整数。  
题目保证表达式在中间计算过程以及结果中，均不超过 231−1。  
题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。  
C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

**输入格式**  
共一行，为给定表达式。

**输出格式**  
共一行，为表达式的结果。

**数据范围**  
表达式的长度不超过 105。

**输入样例：**

(2+2)*(1+1)

**输出样例：**

##### 思路 #####

首先初始化两个栈，一个操作数栈，一个操作符栈。  
依次遍历表达式的每个字符，分情况讨论：  
如果是数字，用另一个指针继续向后移动，找到这个数的大小，放入操作数栈；  
如果是左括号，直接入操作符栈；  
如果是右括号，则进行计算，直到遇到左括号为止；  
如果是运算符，则与操作符栈顶元素进行优先级比较：

*  若当前操作符优先级低于栈顶优先级，则进行计算，直到遇到优先级低的操作符，然后把当前操作符入栈；
 *  若当前操作符优先级高于栈顶优先级，则可以直接入栈；  
    遍历完表达式所有字符后，若操作符栈不为空，则一直计算，直到操作符栈为空为止。

##### 代码 #####

#include <iostream>
    #include <stack>
    #include <string>
    #include <unordered_map>
    
    using namespace std;
    
    stack<int> num;
    stack<char> op;
    
    unordered_map<char, int> h{
        {
        '+', 1}, {
        '-', 1}, {
        '*', 2}, {
        '/', 2}};
    
    //取栈顶两个数并进行计算
    void eval() {
        
        int a = num.top();
        num.pop();
        
        int b = num.top();
        num.pop();
        
        char c = op.top();
        op.pop();
        
        int res = 0;
        
        if(c == '+') res = b + a;
        if(c == '-') res = b - a;
        if(c == '*') res = b * a;
        if(c == '/') res = b / a;
        
        num.push(res);
    }
    
    int main() {
        
        string s;
        cin >> s;
        int i = 0;
        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';
                    j ++;
                }
                num.push(x);
                i = j - 1;//这里要i=j-1，因为后面会有一个i++
            }
            //如果遇到左括号，直接入操作符栈
            else if(s[i] == '(') {
        
                op.push(s[i]);
            }
            //如果遇到右括号，计算表达式值，直到遇到左括号
            else if(s[i] == ')') {
        
                while(op.top() != '(') eval();
                op.pop();
            }
            else {
        
                //一直计算栈顶优先级高的操作符，直到栈空或遇到优先级低的
                while(op.size() && h[op.top()] >= h[s[i]]) eval();
                op.push(s[i]);//操作符入栈
            }
        }
        while(op.size()) eval();
            cout << num.top() << endl;
        return 0;
    }