2014年10月6日星期一

[LeetCode] 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
_____________________________________________________________________

1. About Reverse Polish Notation
Searched Wikipedia, and find it. Just remember the example below.
Polish Notation (Prefix Notation): + 3 4
Infix Notation: 3 + 4
Reverse Polish Notation (Postfix Notation): 3 4 +

2. Solutions
Traverse the String array token. if the string is a number, push it to stack. if it is an operator, pop 2 elements from the stack and take this two elements as operand, and push the result of the operation into stack. In the end, pop the result from stack and return.
2.1 My solution

Accepted

Time Complexity: O(n)
Space Complexity: O(n)
___________________code___________________
public class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens == null) {
            return 0;
        }
       
        Stack s = new Stack();
       
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].equals("+")) {
                int a = (int)s.pop();
                int b = (int)s.pop();
                s.push(b + a);
            } else if (tokens[i].equals("-")) {
                int a = (int)s.pop();
                int b = (int)s.pop();
                s.push(b - a);
            } else if (tokens[i].equals("*")) {
                int a = (int)s.pop();
                int b = (int)s.pop();
                s.push(b * a);
            } else if (tokens[i].equals("/")) {
                int a = (int)s.pop();
                int b = (int)s.pop();
                s.push(b / a);
            } else {
                s.push(Integer.parseInt(tokens[i]));
            }
        }
       
        int result = (int)s.pop();
        return result;
    }
}
___________________code___________________

2.2 Mistake Made
Used  token[i] == "/", which is grammatically correct but cannot really work.
Should use token[i].equals("/")  here.

2.3 Better solution
They used operations.contains(token), which I think is better.
http://answer.ninechapter.com/solutions/evaluate-reverse-polish-notation/

没有评论:

发表评论