Java Evaluate Reverse Polish Notation(逆波兰式)

表情:： ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

题目大意：给定一个逆波兰表达式，求该表达式的值

思路：因为逆波兰表达式本身不须要括号来限制哪个运算该先进行。因此能够直接利用栈来模拟计算：遇到操作数直接压栈，碰到操作符直接取栈顶的2个操作数进行计算（注意第一次取出来的是右操作数），然后再把计算结果压栈，如此循环下去。最后栈中剩下的唯一一个元素便是整个表达式的值。

import java.io.IOException;

import java.util.Stack;

public class EvaluateTest {

 /**

  * @param args

  */

 public static void main(String[] args) throws IOException {

  String[] tokens = new String[] { "2", "1", "+", "3", "*" };

  System.out.println(evalRPN(tokens));

 }

 public static int evalRPN(String[] tokens) {

  int returnValue = 0;

  String operators = "+-*/";

  Stack<String> stack = new Stack<String>();

  for (String t : tokens) {

   if (!operators.contains(t)) {

    stack.push(t);

   } else {

    int a = Integer.valueOf(stack.pop());

    int b = Integer.valueOf(stack.pop());

    switch (t) {

    case "+":

     stack.push(String.valueOf(a + b));

     break;

    case "-":

     stack.push(String.valueOf(b - a));

     break;

    case "*":

     stack.push(String.valueOf(a * b));

     break;

    case "/":

     stack.push(String.valueOf(b / a));

     break;

    }

   }

  }

  returnValue = Integer.valueOf(stack.pop());

  return returnValue;

 }

}