力扣 150. 逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
方案一：利用栈的最近相关性在遇到运算符时取出栈顶两个元素计算。
func evalRPN(tokens []string) int {
// 定义栈
stk := make([]int, 0, len(tokens))
// 遍历数组
for _, token := range tokens {
// 判断是否是数字
num, err := strconv.Atoi(token)
// 将数字入栈
if err == nil {
stk = append(stk, num)
continue
}
// 将最近两个数字取出并出栈
num1, num2 := stk[len(stk) - 2], stk[len(stk) - 1]
stk = stk[:len(stk) - 2]
// 将最近两个数字通过运算符计算并将其入栈
stk = append(stk, calc(num1, num2, token))
}
// 因为题目保证给定表达式必定有结果，所以直接返回栈中第一个元素
return stk[0]
}
func calc(a, b int, op string) int {
switch op {
case "+":
return a + b
case "-":
return a - b
case "*":
return a * b
case "/":
return a / b
}
return 0
}
- 时间复杂度：O(n)，因为需要遍历数组中所有元素，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，因为使用了一个长度不超过 n 的栈辅助计算，所以空间复杂度为 O(n)。