Evaluate Reverse Polish Notation

描述

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

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

Some examples:

  1.   ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  2.   ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

分析

逆波兰表达式是典型的递归结构，所以可以用递归来求解，也可以用栈来求解。

递归版

递归的写法，C++版可以AC，但Java版会爆栈StackOverflowError，所以Java 只能用栈来解决。

  1. // Evaluate Reverse Polish Notation
  2. // 递归，时间复杂度O(n)，空间复杂度O(logn)
  3. // StackOverflowError
  4. class Solution {
  5.     public int evalRPN(final String[] tokens) {
  6.         return evalRPN(tokens, tokens.length - 1);
  7.     }
  8.     private static int evalRPN(final String[] tokens, int i) {
  9.         if (i < 0) return 0;
  10.         int x, y;
  11.         final String token = tokens[i--];
  12.         if (isOperator(token))  {
  13.             y = evalRPN(tokens, i--);
  14.             x = evalRPN(tokens, i--);
  16.             switch (token.charAt(0)) {
  17.                 case '+': x += y; break;
  18.                 case '-': x -= y; break;
  19.                 case '*': x *= y; break;
  20.                 default: x /= y;
  21.             }
  22.         } else  {
  23.             x = Integer.parseInt(token);
  24.         }
  25.         return x;
  26.     }
  27.     private static boolean isOperator(final String op) {
  28.         return op.length() == 1 && OPS.indexOf(op) != -1;
  29.     }
  30.     private static String OPS = new String("+-*/");
  31. }

迭代版

  1. // Max Points on a Line
  2. // 迭代，时间复杂度O(n)，空间复杂度O(logn)
  3. class Solution {
  4.     public int evalRPN(String[] tokens) {
  5.         Stack<String> s = new Stack<>();
  6.         for (String token : tokens) {
  7.             if (!isOperator(token)) {
  8.                 s.push(token);
  9.             } else {
  10.                 int y = Integer.parseInt(s.pop());
  11.                 int x = Integer.parseInt(s.pop());
  12.                 switch (token.charAt(0)) {
  13.                     case '+': x += y; break;
  14.                     case '-': x -= y; break;
  15.                     case '*': x *= y; break;
  16.                     default: x /= y;
  17.                 }
  18.                 s.push(String.valueOf(x));
  19.             }
  20.         }
  21.         return Integer.parseInt(s.peek());
  22.     }
  23.     private static boolean isOperator(final String op) {
  24.         return op.length() == 1 && OPS.indexOf(op) != -1;
  25.     }
  26.     private static String OPS = new String("+-*/");
  27. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/stack-and-queue/stack/evaluate-reverse-polish-notation.html