【基础算法系列】栈的运用题之中缀表达式求值

⭐️前面的话⭐️

本篇文章将介绍中缀表达式的求值，在博主历史文章中介绍过后缀表达式求值，本文来介绍一题中缀表达式求值的问题，就是给定一个中缀计算式，编写程序将这个式子运算结果给计算出来，其实和后缀表达式的思路差不多，都是栈的运用问题，解题代码：Java/C++。

栈运用题：中缀表达式求值

题目详情

3302. 表达式求值

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

注意：

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

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

数据范围
表达式的长度不超过 $10^5$。

输入样例：
(2+2)*(1+1)
输出样例：
8

解题思路

对于这道题，我们可以使用两个栈，一个栈nums用来存运算数，另外一个栈ops可以用来存运算符，但是运算符之间是存在优先级的，我们还可以使用一个哈希表来储存每个运算符的优先级，可以使用数字的大小表示优先级的高低。

第一步，遍历字符串，可能会遇到以下情况：
1）遇到数字，将数组储存到栈nums中。
2）遇到（，直接将（存到栈ops中。
3）遇到），取出栈顶两个数，取出栈顶运算符，进行运算，将运算结果存入栈nums中，如果栈ops栈顶不为空并且栈顶元素不为（，则继续运算，直到栈为空或者栈顶元素为（为止。
4）遇到运算符+，-，*，/，检查栈ops栈顶运算符优先级是否大于或等于遍历遇到的运算符，如果优先级大，则进行运算操作（同上取出栈nums两个数，栈ops一个操作符进行运算，并将结果储存到nums中），然后继续检查，直到栈ops为空或者ops栈顶元素为（，最后将遍历的运算符入栈ops。
第二步，检查是否运算完成。
字符串遍历完成后，此时运算不一定结束，检查栈ops是否为空，不为空继续进行运算操作，直到栈ops为空为止，最终nums剩余的一个数就是运算结果。

对于运算符优先级的判断我们可以通过建立哈希表，将运算符映射一个数字，其中数字越大就表示优先级越大。

动图演示：

实现代码

Java版本实现：

import java.util.*;

class Main {
    //栈nums 存运算数
    private static Deque<Integer> nums = new ArrayDeque<>();
    //栈ops 存运算符
    private static Deque<Character> ops = new ArrayDeque<>();
    
    //哈希表用来映射运算符优先级
    private static HashMap<Character, Integer> hash = new HashMap<>();
    
    //初始化哈希表
    static {
        hash.put('+', 1);
        hash.put('-', 1);
        hash.put('*', 2);
        hash.put('/', 2);
    }
    
    //判断某个字符是否是数字
    private static boolean isDigit(char c) {
        return c >= '0' &&c <= '9';
    }
    
    //实现运算方法
    private static void eval() {
        //去除第二个运算数
        int b = nums.pollLast();
        //取出第一个运算数
        int a = nums.pollLast();
        //取出运算符
        char op = ops.pollLast();
        
        //判断符号，对应进行运算
        if (op == '+') nums.offerLast(a + b);
        else if (op == '-') nums.offerLast(a - b);
        else if (op == '*') nums.offerLast(a * b);
        else if (op == '/') nums.offerLast(a / b);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String s = sc.nextLine();
        
        char[] cs = s.toCharArray();
        
        for (int i = 0; i < cs.length; i++) {
            char c = cs[i];
            
            if (isDigit(c)) {
                //遍历的字符为数字，取出完整的数字放在数组当中
                int ret = c - '0';
                int j = i + 1;
                while (j < cs.length && isDigit(cs[j])) {
                    ret = ret * 10 + (cs[j] - '0');
                    j++;
                }
                //更新i
                i = j - 1;
                //将数字入栈
                nums.offerLast(ret);
            } else if (c == '(') {
                //遇到(，直接入栈ops
                ops.offerLast(c);
            } else if (c == ')') {
                //遇到)，进行运算操作，直到栈顶遇到(为止
                while (!ops.isEmpty() && ops.peekLast() != '(') eval();
                //遇到(，将(出栈
                ops.pollLast();
            } else {
                //遇到运算符，则比较优先级，如栈顶运算符优先级大，则进行运算，直到栈为空或栈顶运算符较小或栈顶运算符为(
                while (!ops.isEmpty() && ops.peekLast() != '(' && hash.get(ops.peekLast()).compareTo(hash.get(c)) >= 0) eval();
                
                //将当前运算符入栈
                ops.offerLast(c);
            }
        }
        
        //检查ops栈内是否还有运算符，如果还有，则表示运算还没结束，继续运算，直到ops栈无运算符为止
        while (!ops.isEmpty()) eval();
        
        //输出nums栈顶元素，即是最终运算结果
        System.out.println(nums.peekLast());
    }
}

C++版本实现：

include <iostream>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <string>

using namespace std;

//栈1 存储元素
stack<int> nums;
//栈2 存储操作符号
stack<char> ops;
//哈希表 用来存储运算符优先级
unordered_map<char, int> pri = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

void eval()
{
    //取第二个操作数
    int b = nums.top();
    nums.pop();
    //取第一个操作数
    int a = nums.top();
    nums.pop();
    
    //取操作符
    char op = ops.top();
    ops.pop();
    
    //进行运算
    if (op == '+') nums.push(a + b);
    else if (op == '-') nums.push(a - b);
    else if (op == '*') nums.push(a * b);
    else if (op == '/') nums.push(a / b);
    
    //cout << a << " " << op << " " << b << "=";
    
    //cout << nums.top() << endl;
}

int main()
{
    string s;
    cin >> s;
    
    for (int i = 0; i < s.size(); i++) 
    {
        char c = s[i];
        if (isdigit(c)) 
        {
            //字符为数字，将该数字放入到储存数字的栈中
            int j = i + 1;
            int ret = s[i] - '0';
            while (j < s.size() && isdigit(s[j]))
            {
                ret = ret * 10 + (s[j] - '0');
                j++;
            }
            //更新i
            i = j  - 1;
            nums.push(ret);
        } else if (c == '(') 
        {
            ops.push(c);
        } else if (c == ')') 
        {
            //遇到右括号对栈元素进行运算，直到遇到(为止
            while (ops.size() > 0 && ops.top() != '(') eval();
            ops.pop();
        } else {
            //遇到运算符，比较优先级，如果优先级较高，则进行运算
            while (ops.size() > 0 && ops.top() != '(' && pri[ops.top()] >= pri[c]) eval();
            ops.push(c);
        }
    }
    
    //如果还有剩余运算符 则继续运算
    while (ops.size() > 0) eval();
    //栈顶元素即为最终的运算结果
    cout << nums.top() << endl;
    return 0;
}