Best Run Time for Reverse Polish Notation?


  • 0
    M

    What is the best Run Time you people are getting.

    I got a run time of 532 ms with the following solution in JAVA. Does anyone have a more optimized solution in java or any other language. I'd love to see it. Thanks!

    public class Solution {
        public int evalRPN(String[] tokens) {
            Stack<Integer> operands = new Stack<Integer>();
            int answer = 0;
            String operators = "+-*/";
            
            
            for(String op : tokens){
                int index = operators.indexOf(op);
                
                if(index == -1){
                    operands.push(Integer.valueOf(op));
                }
                else{
                    if(operands.size() < 2){
                        return 0; //raise exception?
                    }
                    
                    int op2 = operands.pop();
                    int op1 = operands.pop();
                    
                    
                    switch (index){
                        case 0: answer = op1 + op2;
                        break;
                        case 1: answer = op1 - op2;
                        break;
                        case 2: answer = op1 * op2;
                        break;
                        case 3: 
                            if(op2 == 0){
                                return 0;
                            }
                                
                                answer = op1 / op2;
                                
                        break;
                        default:
                            return 0;
                        
                    }
                    operands.push(answer);
                }
            }
            return operands.pop();
        }
    }

  • 2
    B

    My CPP solution which is very similar to yours takes 12ms on OJ.

    class Solution {
    public:
        int evalRPN(vector<string> &tokens) {
            stack<int> s;
            
            for (unsigned i = 0; i < tokens.size(); ++i) {
                if (tokens[i] == "+") {
                    int v1 = s.top(); s.pop();
                    int v2 = s.top(); s.pop();
                    s.push(v2+v1);
                    
                } else if (tokens[i] == "-") {
                    int v1 = s.top(); s.pop();
                    int v2 = s.top(); s.pop();
                    s.push(v2-v1);
                } else if (tokens[i] == "*") {
                    int v1 = s.top(); s.pop();
                    int v2 = s.top(); s.pop();
                    s.push(v2*v1);    
                } else if (tokens[i] == "/") {
                    int v1 = s.top(); s.pop();
                    int v2 = s.top(); s.pop();
                    s.push(v2/v1);   
                } else {
                    s.push(atoi(tokens[i].c_str()));
                }
            }
            
            return s.top();
        }
    };

  • 0
    M

    Wow, thanks for sharing. That's a huge difference.
    Any thoughts on why the difference, or how my java code can be optimized?

    One of the reasons is obviously that Stack in java uses Integer object instead of primitive int, so theres the overhead of Boxing and Unboxing involved. But that still doesn't explain the big difference.


  • 0
    G

    I have tried three implementations:

    1. with a Stack (524ms)
    2. with an array simulating a stack and avoid boxing(544ms)
    3. with a HashMap (488ms)
      I think your have the same complexity. Slowness is due to overhead somewhere.

  • 0
    M

    Thanks, this is really interesting. I mean the difference is just too big to not care.


  • 0
    M

    my code in cpp is very similar to that of bigOh. i have just avoided the redundant statements of popping, and used switch case instead. my code takes 56 ms.

    class Solution {
    public:
        int evalRPN(vector<string> &tokens) {
            stack<int> S;
            for(int i = 0; i<tokens.size();++i)
            {
               if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/" )
                {
                    int b = S.top();
                    S.pop();
                    int a = S.top();
                    S.pop();
                    char c = *(tokens[i].c_str()); // dereferencing the pointer to string to get char value.
                    switch(c)
                    {
                        case '+' : S.push(a + b);
                                    break;
                        case '-' : S.push(a - b);
                                    break;
                        case '*' : S.push(a * b);
                                    break;
                        case '/' : S.push(a / b);
                                    break;
                    }
                }
                else
                    S.push(atoi(tokens[i].c_str()));
                }
                
            
            return S.top();
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.