数据结构与算法之栈

leetcode 的题目： 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: [“2”, “1”, “+”, “3”, ““] -> ((2 + 1) 3) -> 9 [“4”, “13”, “5”, “/”, “+”] -> (4 + (13 / 5)) -> 6

解题思路就是利用栈的先进后出的特性

import java.util.*; public class Solution { public int evalRPN(String[] tokens) { if(tokens == null){ return -1; }

Stack<Integer> stack=new Stack(); for(int i=0;i<tokens.length;i++){ try{ int num=Integer.parseInt(tokens[i]); stack.add(num); }catch(Exception e){ int a=stack.pop(); int b=stack.pop(); stack.push(getIt(a,b,tokens[i])); } } return stack.pop(); } public static int getIt(int a,int b,String str){ switch(str){ case "+": return b+a; case "-": return b-a; case "/": return b/a; case "*": return b*a; default : return 0; } }

}