reverse-polish-notation

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. 思路：逆波兰表达式的计算十分方便，对于运算符，其运算的两个数就是这个运算符前面的两个数。所以我们只要用一个栈，每次遇到数字就压入栈内，每次遇到运算符就弹出两个数，计算后再压回栈内，最后栈内剩下的那个数就是计算结果了。

算法实现：

import java.util.*; public class Solution { public int evalRPN(String[] tokens) { // if(tokens.size()==1) return tokens[0]; Stack<Integer> stk = new Stack<Integer>(); for(String token : tokens){ switch(token){ case"+": stk.push(stk.pop() + stk.pop()); break; case"-": stk.push(-stk.pop() + stk.pop()); break; case"/": int num1 = stk.pop(); int num2 = stk.pop(); stk.push(num2 / num1); break; case"*": stk.push(stk.pop() * stk.pop()); break; default: stk.push(Integer.parseInt(token)); } } return stk.pop(); } }

时间复杂度：o(n);空间复杂度为：o(n);