Wednesday, January 21, 2015

Evaluate Reverse Polish Notation (LeetCode Stack)

Question: 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

Idea: Use stack. Scan the input string array from left to right. If the current position is a number, push it to the stack, otherwise pop two numbers and apply the operator and push the result back to the stack. The last element in the stack is the final result.

Time: O(n) Space: O(n)

Code:
 public class Solution {  
   public int evalRPN(String[] tokens) {  
     Stack<Integer> stack=new Stack<Integer>();  
     for(int i=0;i<tokens.length;i++)  
     {  
       String s=tokens[i];  
       if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))  
       {  
         int second=stack.pop();  
         int first=stack.pop();  
         int result=0;  
         if(s.equals("+"))  
           result=first+second;  
         if(s.equals("-"))  
           result=first-second;  
         if(s.equals("*"))  
           result=first*second;  
         if(s.equals("/"))  
           result=first/second;  
         stack.push(result);  
       }  
       else  
         stack.push(Integer.parseInt(s));  
     }  
     return stack.pop();  
   }  
 }  

No comments:

Post a Comment