Medium

题目描述

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

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

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式的结果。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

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

示例 2：

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

示例 3：

输入：tokens = ["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 <= tokens.length <= 10^4
  • tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

解题思路

解题思路

逆波兰表达式（后缀表达式）的特点是操作符在操作数之后，这种形式天然适合用栈来处理。

核心思想：

  1. 遍历表达式中的每个元素
  2. 如果是数字，直接入栈
  3. 如果是操作符，从栈中弹出两个操作数进行运算，将结果重新入栈
  4. 最终栈中只剩一个元素，即为最终结果

处理细节：

  • 注意操作数的顺序：先弹出的是右操作数，后弹出的是左操作数
  • 除法需要向零截断，可以用 int(a/b) 实现
  • 负数的处理：注意区分负号和减法操作符

算法步骤：

  1. 初始化一个栈
  2. 遍历 tokens 数组
  3. 判断当前元素是数字还是操作符
  4. 数字直接入栈，操作符取出栈顶两元素计算后入栈
  5. 返回栈顶元素

这是一个经典的栈应用问题，时间复杂度为 O(n)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        
        for (const string& token : tokens) {
            if (token == "+") {
                int b = stk.top(); stk.pop();
                int a = stk.top(); stk.pop();
                stk.push(a + b);
            } else if (token == "-") {
                int b = stk.top(); stk.pop();
                int a = stk.top(); stk.pop();
                stk.push(a - b);
            } else if (token == "*") {
                int b = stk.top(); stk.pop();
                int a = stk.top(); stk.pop();
                stk.push(a * b);
            } else if (token == "/") {
                int b = stk.top(); stk.pop();
                int a = stk.top(); stk.pop();
                stk.push(a / b);
            } else {
                stk.push(stoi(token));
            }
        }
        
        return stk.top();
    }
};

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        
        for token in tokens:
            if token in "+-*/":
                b = stack.pop()
                a = stack.pop()
                if token == '+':
                    stack.append(a + b)
                elif token == '-':
                    stack.append(a - b)
                elif token == '*':
                    stack.append(a * b)
                else:  # token == '/'
                    # 向零截断
                    stack.append(int(a / b))
            else:
                stack.append(int(token))
        
        return stack[0]

public class Solution {
    public int EvalRPN(string[] tokens) {
        Stack<int> stack = new Stack<int>();
        
        foreach (string token in tokens) {
            if (token == "+") {
                int b = stack.Pop();
                int a = stack.Pop();
                stack.Push(a + b);
            } else if (token == "-") {
                int b = stack.Pop();
                int a = stack.Pop();
                stack.Push(a - b);
            } else if (token == "*") {
                int b = stack.Pop();
                int a = stack.Pop();
                stack.Push(a * b);
            } else if (token == "/") {
                int b = stack.Pop();
                int a = stack.Pop();
                stack.Push(a / b);
            } else {
                stack.Push(int.Parse(token));
            }
        }
        
        return stack.Peek();
    }
}

var evalRPN = function(tokens) {
    const stack = [];
    const operators = new Set(['+', '-', '*', '/']);
    
    for (let token of tokens) {
        if (operators.has(token)) {
            const b = stack.pop();
            const a = stack.pop();
            
            if (token === '+') {
                stack.push(a + b);
            } else if (token === '-') {
                stack.push(a - b);
            } else if (token === '*') {
                stack.push(a * b);
            } else if (token === '/') {
                stack.push(Math.trunc(a / b));
            }
        } else {
            stack.push(parseInt(token));
        }
    }
    
    return stack[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有token，每次操作都是O(1)
空间复杂度O(n)栈的空间消耗，最坏情况下存储所有数字

相关题目