逆波兰表达式求值

描述

根据 逆波兰表示法，求表达式的值。

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

• 输入: [“2”, “1”, “+”, “3”, “ * “]
• 输出: 9
• 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

• 输入: [“4”, “13”, “5”, “/“, “+”]
• 输出: 6
• 解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

• 输入: [“10”, “6”, “9”, “3”, “+”, “-11”, “ * “, “/“, “ * “, “17”, “+”, “5”, “+”]

• 输出: 22

• 解释:该算式转化为常见的中缀算术表达式为：

  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5       
  = ((10 * (6 / (12 * -11))) + 17) + 5       
  = ((10 * (6 / -132)) + 17) + 5     
  = ((10 * 0) + 17) + 5     
  = (0 + 17) + 5    
  = 17 + 5    
  = 22    

逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

题解

C++

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s; // 定义一个栈，用于存储操作数
        for (const string& token : tokens) { // 遍历逆波兰表达式中的每一个元素
            if (token == "+" || token == "-" || token == "*" || token == "/") { // 如果当前元素是操作符
                int num2 = s.top(); // 弹出栈顶元素作为第二个操作数
                s.pop();
                int num1 = s.top(); // 弹出栈顶元素作为第一个操作数
                s.pop();
                int result; // 定义一个变量用于存储计算结果
                if (token == "+") { // 如果操作符为加号，则执行加法运算
                    result = num1 + num2;
                } else if (token == "-") { // 如果操作符为减号，则执行减法运算
                    result = num1 - num2;
                } else if (token == "*") { // 如果操作符为乘号，则执行乘法运算
                    result = num1 * num2;
                } else if (token == "/") { // 如果操作符为除号，则执行除法运算
                    result = num1 / num2;
                }
                s.push(result); // 将计算结果压入栈中
            } else { // 如果当前元素是操作数，则将其转化为整数并压入栈中
                s.push(stoi(token));
            }
        }
        return s.top(); // 返回栈顶元素，即为最终的计算结果
    }
};

该算法的时间复杂度为 $O(n)$，其中 $n$ 表示逆波兰表达式中的元素个数。算法的空间复杂度为 $O(n)$，其中 $n$ 表示逆波兰表达式中的元素个数。

算法的具体步骤如下：

1. 定义一个栈，用于存储操作数。
2. 遍历逆波兰表达式中的每一个元素：
   • 如果当前元素是操作符，则弹出栈顶的两个元素作为操作数，执行对应的运算，并将运算结果压入栈中。
   • 如果当前元素是操作数，则将其转化为整数并压入栈中。
3. 返回栈顶元素，即为最终的计算结果。

例如，当输入逆波兰表达式为 [“2”, “1”, “+”, “3”, “*”] 时，该算法的执行过程如下：

1. 初始化栈为空。
2. 遍历逆波兰表达式中的每一个元素：
   • 当前元素为 “2”，将其转化为整数并压入栈中，栈中的元素为 [2]。
   • 当前元素为 “1”，将其转化为整数并压入栈中，栈中的元素为 [2, 1]。
   • 当前元素为 “+”，弹出栈顶的两个元素（1 和 2），执行加法运算得到 3，并将运算结果压入栈中，栈中的元素为 [3]。
   • 当前元素为 “3”，将其转化为整数并压入栈中，栈中的元素为 [3, 3]。
   • 当前元素为 “*”，弹出栈顶的两个元素（3 和 3），执行乘法运算得到 9，并将运算结果压入栈中，栈中的元素为 [9]。
3. 返回栈顶元素，即为最终的计算结果 9。

该算法在遍历逆波兰表达式的过程中，每个元素最多只会被压入和弹出栈一次，因此时间复杂度为 $O(n)$，其中 $n$ 表示逆波兰表达式中的元素个数。同时，该算法需要使用一个栈来保存中间结果，因此空间复杂度为 $O(n)$。

Python

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []  # 初始化栈
        for token in tokens:  # 遍历逆波兰表达式中的每一个元素
            if token in ["+", "-", "*", "/"]:  # 当前元素为运算符
                # 弹出栈顶的两个元素，执行相应的运算，将运算结果压入栈中
                right = stack.pop()
                left = stack.pop()
                if token == "+":
                    stack.append(left + right)
                elif token == "-":
                    stack.append(left - right)
                elif token == "*":
                    stack.append(left * right)
                else:
                    stack.append(int(left / right))
            else:  # 当前元素为数字
                stack.append(int(token))  # 将其转化为整数并压入栈中
        return stack[0]  # 返回栈顶元素，即为最终的计算结果