2021-10-17：逆波兰表达式求值。根据 逆波兰表示法，求表
原创2021-10-17：逆波兰表达式求值。根据 逆波兰表示法，求表
原创
福大大架构师每日一题
修改于 2021-10-18 10:33:03
修改于 2021-10-18 10:33:03
2021-10-17：逆波兰表达式求值。根据 逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。说明：整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。力扣150。
福大大 答案2021-10-17：
栈。遇到数字，压栈。遇到运算符，计算。
时间复杂度：O(N)。
空间复杂度：O(N)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"strconv"
)
func main() {
tokens := []string{"2", "1", "+", "3", "*"}
ret := evalRPN(tokens)
fmt.Println(ret)
}
func evalRPN(tokens []string) int {
stack := make([]int, 0)
for _, str := range tokens {
if str == "+" || str == "-" || str == "*" || str == "/" {
compute(&stack, str)
} else {
i, _ := strconv.Atoi(str)
stack = append(stack, i)
}
}
return stack[len(stack)-1]
}
func compute(stack *[]int, op string) {
num2 := (*stack)[len(*stack)-1]
*stack = (*stack)[0 : len(*stack)-1]
num1 := (*stack)[len(*stack)-1]
*stack = (*stack)[0 : len(*stack)-1]
ans := 0
switch op {
case "+":
ans = num1 + num2
break
case "-":
ans = num1 - num2
break
case "*":
ans = num1 * num2
break
case "/":
ans = num1 / num2
break
}
*stack = append(*stack, ans)
}执行结果如下：
图片
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读