LeetCode 150. 逆波兰表达式求值

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 150. 逆波兰表达式求值

思路分析

我们可以使用栈来解决这个问题。遍历逆波兰表达式中的每一个元素：

如果是数字，则将其压入栈中。

如果是运算符，则从栈中弹出两个数字，进行相应的运算，然后将结果压回栈中。

最后栈中只会剩下一个元素，即为表达式的结果。

参考代码

func evalRPN(tokens []string) int {
	var stack []int

	calc := func(op string, b, a int) int {
		switch op {
		case "+":
			return a + b
		case "-":
			return a - b
		case "*":
			return a * b
		case "/":
			return a / b
		}
		return 0
	}

	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]
			stack = append(stack, calc(token, b, a))
		default:
			num, _ := strconv.Atoi(token)
			stack = append(stack, num)
		}
	}

	return stack[0]
}

时间复杂度：O(n)，其中 n 是 token 的个数，每个 token 只被访问一次。

空间复杂度：O(n)，使用了栈结构，最坏情况下所有元素都是数字都要压入栈中。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/00551611