用栈来解决表达式问题（算法村第四关黄金挑战）

表达式计算是编译原理、自然语言处理、文本分析等领域非常重要的问题。我们来看两道常见且难度中等的问题：“计算器问题”和“逆波兰表达式求值”

计算器问题

227. 基本计算器 II - 力扣（LeetCode）

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

**注意：**不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "3+2*2"
输出：7

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

输入：s = " 3+5 / 2 "
输出：5

提示：

• 1 <= s.length <= 3 * 105
• s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
• s 表示一个 有效表达式
• 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
• 题目数据保证答案是一个 32-bit 整数

栈

遍历字符串 s，并用变量 preSign 记录每个数字之前的运算符，对于第一个数字，其之前的运算符视为加号。每次遍历到数字末尾时，根据 preSign 来决定计算方式

• 加号：将数字压入栈
• 减号：将数字的相反数压入栈
• 乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果

若读到一个运算符，或者遍历到字符串末尾，即认为是遍历到了数字末尾。处理完该数字后，更新 preSign 为当前遍历的字符。

遍历完字符串 s 后，将栈中元素累加，即为该字符串表达式的值。

public int calculate(String s)
{
   
    int operand = 0;    //运算数(s中的数都是非负整数)
    char preOperator = '+';  //运算数之前的运算符
    ArrayDeque<Integer> stack = new ArrayDeque<>(); //存储运算数的栈

    for (int i = 0; i < s.length(); i++)
    {
   
        char c = s.charAt(i);

        //获取运算数，可能是个位数，也可能是百位数、千位数...
        if(Character.isDigit(c))
            operand = operand * 10 + Character.getNumericValue(c);

        //遍历到操作符，或者遍历到最后一个操作数的最后一位
        if (!Character.isDigit(c) && c != ' ' || i == s.length() - 1)
        {
   
            switch (preOperator)
            {
   
                case '+' ->
                    stack.push(operand);
                case '-' ->
                    stack.push(-operand);
                case '*' ->
                    stack.push(stack.pop() * operand);
                case '/' ->
                    stack.push(stack.pop() / operand);
            }

            //更新运算符
            preOperator = c;
            //更新操作数
            operand = 0;
        }
    }

    //最后把栈中的所有数加起来即可得到答案
    int ans = 0;
    while (!stack.isEmpty())
        ans = ans + stack.pop();

    return ans;
}

逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

1. 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
2. 两个整数之间的除法只保留整数部分。
3. 可以保证给定的逆波兰表达式总是有效的，即表达式总会得出有效数值且不存在除数为 0 的情况。

解

中缀表达式：1 + (2 + 3) × 4 - 5 
前缀表达式：- + 1 × + 2 3 4 5 
后缀表达式：1 2 3 + 4 × + 5 -

1. 中缀表达式一种通用的算术或逻辑公式表示方法，运算符处于两个操作数之间
2. 前缀表达式也称为前缀记法或波兰式，运算符位于两个操作数之前。
3. 后缀表达式也称为逆波兰式，运算符位于两个操作数之后。

观察后缀表达式可以发现，其特点就是数字先保存下来，然后遇到符号就计算，例如“1 2 3 +”，遇到 +号就将2+3加起来变成5再继续其他操作，直到最后完成。

如果用栈来解释，就是遇见数字即进栈，遇见运算符则取出栈中最上面的两个元素进行计算，最后将运算结果入栈。

public int evalRPN(String[] tokens)
{
   
    ArrayDeque<Integer> stack = new ArrayDeque<>();

    for (String token : tokens)
    {
   
        //遍历到运算符则从栈中取两数出来运算。
        //字符串的第一个字符不是数字的，除了单个运算符还有负数，所有要多一个限制条件
        if (!Character.isDigit(token.charAt(0)) && token.length() == 1)
        {
   
            int a = stack.pop();
            int b = stack.pop();

            switch (token.charAt(0))
            {
   
                case '+'->
                    stack.push(a + b);
                case '-'->
                    stack.push(b- a);   //注意顺序
                case '*'->
                    stack.push(a * b);
                case '/'->
                    stack.push(b / a);  //注意顺序
            }
        }
        else    //遍历到数字则直接入栈
            stack.push(Integer.parseInt(token));
    }

    return stack.pop(); //最后一个元素就是运算结果
}