LeetCode LCR 036. 逆波兰表达式求值

Categories:

题目描述
思路分析
1. 解法一：栈模拟（推荐）
相似题目

题目描述

✅ LCR 036. 逆波兰表达式求值

思路分析

解法一：栈模拟（推荐）

核心思路：

遇到数字入栈，遇到运算符弹出两个数计算后再入栈。

注意减法与除法顺序：先弹出的为右操作数。

复杂度分析：

时间复杂度：O(n)，其中 n 表示 tokens 长度。

空间复杂度：O(n)，使用栈保存数字。

// 栈模拟逆波兰表达式
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();

        for (String token : tokens) {
            switch (token) {
                case "+": {
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a + b);
                    break;
                }
                case "-": {
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a - b);
                    break;
                }
                case "*": {
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a * b);
                    break;
                }
                case "/": {
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a / b);
                    break;
                }
                default:
                    stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }
}

// 栈模拟逆波兰表达式
func evalRPN(tokens []string) int {
	stack := make([]int, 0, len(tokens))

	for _, token := range tokens {
		switch token {
		case "+", "-", "*", "/":
			b := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			a := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			var res int
			switch token {
			case "+":
				res = a + b
			case "-":
				res = a - b
			case "*":
				res = a * b
			case "/":
				res = a / b
			}
			stack = append(stack, res)
		default:
			val, _ := strconv.Atoi(token)
			stack = append(stack, val)
		}
	}

	return stack[0]
}

相似题目

题目	难度	考察点
224. 基本计算器	困难	栈
227. 基本计算器 II	中等	栈
772. 基本计算器 III	困难	栈
20. 有效的括号	简单	栈
71. 简化路径	中等	栈
155. 最小栈	简单	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/42754912