题目描述
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, and /. Each operand may be an integer or another expression.
Note that division between two integers should truncate toward zero.
It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.
Example 1:
Input: tokens = [“2”,“1”,"+",“3”,"*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = [“4”,“13”,“5”,"/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = [“10”,“6”,“9”,“3”,"+","-11","*","/","*",“17”,"+",“5”,"+"]
Output: 22
Explanation: ((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
Constraints:
- 1 <= tokens.length <= 10^4
- tokens[i] is either an operator: “+”, “-”, “*”, or “/”, or an integer in the range [-200, 200].
题目分析
题目中的Reverse Polish Notation即 逆波兰表示法，是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式形式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。逆波兰结构由弗里德里希·鲍尔（Friedrich L. Bauer）和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值，以利用堆栈结构减少计算机内存访问。
以上这段从百科中查询到的资料已经很明确的指出应当使用stack求解，因此我们利用stack实现一个简单的逆波兰表达式的解释器就行。核心逻辑就是遍历tokens，如果是操作数，就压栈；如果是操作符，则弹栈2次，分别得到左右操作数，执行对应的计算后，将结果再压栈；然后如此循环迭代即可。
代码比较简单， 直接看代码
示例代码
func evalRPN(tokens []string) int {
stack := stack{}
for _, v := range tokens {
if v == "+" {
// 此时位于栈顶的是右操作数
// 对于减法和除法这两种不满足交换律的运算，一定不能混淆左右操作数的顺序
rightop := stack.Pop()
leftop := stack.Pop()
stack.Push(leftop + rightop)
continue
}
if v == "-" {
rightop := stack.Pop()
leftop := stack.Pop()
stack.Push(leftop - rightop)
continue
}
if v == "*" {
rightop := stack.Pop()
leftop := stack.Pop()
stack.Push(leftop * rightop)
continue
}
if v == "/" {
rightop := stack.Pop()
leftop := stack.Pop()
stack.Push(leftop / rightop)
continue
}
ele, _ := strconv.Atoi(v)
stack.Push(ele)
}
return stack.Pop()
}
type stack struct {
list []int
}
func (s *stack) Pop() int {
if len(s.list) == 0 {
return 0
}
ans := s.list[len(s.list)-1]
s.list = s.list[:len(s.list)-1]
return ans
}
func (s *stack) Push(ele int) {
s.list = append(s.list, ele)
}