Sunday, January 11, 2015

LeetCode 150: 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:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
public class Solution {
    public int evalRPN(String[] tokens) {
        int n = tokens.length;
        
        if (n == 0)
            return 0;

        Stack<Integer> num = new Stack<>();
        
        for (int i = 0; i < n; i++)
        {
            char ch = tokens[i].charAt(0);
            
            if (tokens[i].length()==1 && (ch=='+' || ch=='-' || ch=='*' || ch=='/'))
            {
                int b = num.pop();
                int a = num.pop();
                int c;
                
                if (ch == '+')
                    c = a+b;
                else if (ch == '-')
                    c = a-b;
                else if (ch == '*')
                    c = a*b;
                else
                    c = a/b;
                    
                num.push(c);
            }
            else
                num.push(Integer.valueOf(tokens[i]));
        }
        
        return num.pop();
    }
}

No comments:

Post a Comment