题目

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

  • Division between two integers should truncate toward zero.
  • The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1:

  1. Input: ["2", "1", "+", "3", "*"]
  2. Output: 9
  3. Explanation: ((2 + 1) * 3) = 9

Example 2:

  1. Input: ["4", "13", "5", "/", "+"]
  2. Output: 6
  3. Explanation: (4 + (13 / 5)) = 6

Example 3:

  1. Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
  2. Output: 22
  3. Explanation: 
  4.   ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
  5. = ((10 * (6 / (12 * -11))) + 17) + 5
  6. = ((10 * (6 / -132)) + 17) + 5
  7. = ((10 * 0) + 17) + 5
  8. = (0 + 17) + 5
  9. = 17 + 5
  10. = 22

题意

计算逆波兰表达式(即后缀表达式)的值。

思路

遇到数字就压栈；遇到符号则从栈中弹出两个数字进行运算(注意后出栈的在前，先出栈的在后)，将得到的结果再压入栈中；最后栈中只剩一个数，即所求结果。

代码实现

Java

  1. class Solution {
  2.     public int evalRPN(String[] tokens) {
  3.         Deque<Integer> stack = new ArrayDeque<>();
  5.         for (String token : tokens) {
  6.             if (token.equals("+")) {
  7.                 int y = stack.pop(), x = stack.pop();
  8.                 stack.push(x + y);
  9.             } else if (token.equals("-")) {
  10.                 int y = stack.pop(), x = stack.pop();
  11.                 stack.push(x - y);
  12.             } else if (token.equals("*")) {
  13.                 int y = stack.pop(), x = stack.pop();
  14.                 stack.push(x * y);
  15.             } else if (token.equals("/")) {
  16.                 int y = stack.pop(), x = stack.pop();
  17.                 stack.push(x / y);
  18.             } else {
  19.                 stack.push(Integer.parseInt(token));
  20.             }
  21.         }
  23.         return stack.pop();
  24.     }
  25. }

JavaScript

  1. /**
  2.  * @param {string[]} tokens
  3.  * @return {number}
  4.  */
  5. var evalRPN = function (tokens) {
  6.   const stack = []
  8.   for (const token of tokens) {
  9.     if (!isNaN(token)) {
  10.       stack.push(+token)
  11.     } else {
  12.       const b = stack.pop()
  13.       const a = stack.pop()
  14.       if (token === '+') stack.push(a + b)
  15.       else if (token === '-') stack.push(a - b)
  16.       else if (token === '*') stack.push(a * b)
  17.       else stack.push(Math.trunc(a / b))
  18.     }
  19.   }
  21.   return stack.pop()
  22. }