150.evaluate-reverse-polish-notation.md

根据逆波兰表示法，求表达式的值。

有效的运算符包括  +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。 示例  1：

输入: ["2", "1", "+", "3", "*"] 输出: 9 解释: ((2 + 1) * 3) = 9 示例  2：

输入: ["4", "13", "5", "/", "+"] 输出: 6 解释: (4 + (13 / 5)) = 6 示例  3：

输入: ["10", "6", "9", "3", "+", "-11", "", "/", "", "17", "+", "5", "+"] 输出: 22 解释: ((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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

相似题目

224.基本计算器 [hard] 带括号

227.基本计算器 II [medium] 不带括号

---

逆波兰表达式求值

思路：用栈，遇到运算符，则弹出前两个数，计算，然后重新压栈，直到遍历结束

• js 实现

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
  let stack = [];
  for (let c of tokens) {
    let a, b;
    switch (c) {
      case "+":
        b = stack.pop();
        a = stack.pop();
        stack.push(a + b);
        break;
      case "-":
        b = stack.pop();
        a = stack.pop();
        stack.push(a - b);
        break;
      case "*":
        b = stack.pop();
        a = stack.pop();
        stack.push(a * b);
        break;
      case "/":
        b = stack.pop();
        a = stack.pop();
        stack.push(parseInt(a / b));
        break;
      default:
        stack.push(+c);
        break;
    }
  }
  return stack[0];
};

• golang 实现

func evalRPN(tokens []string) int {
	stack := make([]int, 0)
	for _, str := range tokens {
		var a, b int
		switch str {
		case "+":
			b = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			a = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			stack = append(stack, a+b)
			break
		case "-":
			b = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			a = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			stack = append(stack, a-b)
			break
		case "*":
			b = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			a = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			stack = append(stack, a*b)
			break
		case "/":
			b = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			a = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			stack = append(stack, a/b)
			break
		default:
			s, _ := strconv.Atoi(str)
			stack = append(stack, s)
		}
	}
	return stack[len(stack)-1]
}