C++ Solution Using Stack


  • 0
    N
    int evalRPN(vector<string> &tokens) {
        stack<int> st;
        for(int i = 0; i < tokens.size(); ++i) {
            // if the current character is Number
            if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/")
                st.push(atoi(tokens[i].c_str()));
            else {  // current character is Symbol
                int a = st.top();   st.pop();
                int b = st.top();   st.pop();
                
                if(tokens[i] == "+")    st.push(b + a);
                if(tokens[i] == "-")    st.push(b - a);
                if(tokens[i] == "*")    st.push(b * a);
                if(tokens[i] == "/")    st.push(b / a);
            }
        }
        return st.top();
    }

  • 1
    S

    Great solution, but I want to suggest some improvements.

    if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") {
        st.push(atoi(tokens[i].c_str()));
    }
    

    The above block assumes the string does not have any other non-numeric characters other than +, -, *, /.
    So, for example, if it encounters a "?" then it will execute "atoi" and will silently push a e stack, which is wrong. My suggestion code is this:

    char *c;
    int num = strtol(tokens[pos].c_str(), &c, 10);
    if (num != 0 || c != tokens[pos].c_str()) {
        s.push(num);
    }
    

    What this will do is when ever the conversion is 0, it will also check if the scan pointer has actually moved. If the scan pointer has not moved that means we found an invalid character. In such a case we can return error or 0 from the routine. It will also allow us not to not preprocess the token for +, -, *, /.

    One more suggestion: If the vector is empty the code is going to access the top of an empty stack, which I think is illegal according to MSDN documentation.

    Here's what I coded. Comments are most welcome.

    int evalRPN(vector<string> &tokens) {
        stack<int> s;
        char *c;
    
        if (tokens.size() < 1) return 0;
        for (int num1, num2, pos = 0; pos < tokens.size(); pos++) {
            num2 = strtol(tokens[pos].c_str(), &c, 10);
            if (num2 != 0 || c != tokens[pos].c_str()) {
                //
                // Check if the token is numeric before pushing
                // If conversion returns 0, but scan pointer didn't move then it's non-numeric
                //
                s.push(num2);
            }
            else {
                // 
                // Token is non-numeric.  Most likely an operator.
                // This means the stack has to have two operand or else error condition.
                //
                if (s.size() < 2) return 0;
                num2 = s.top();
                s.pop();
                num1 = s.top();
                s.pop();
                    
                if (tokens[pos] == "+") s.push(num1 + num2);
                else if (tokens[pos] == "-") s.push(num1 - num2);
                else if (tokens[pos] == "*") s.push(num1 * num2);
                else if (tokens[pos] == "/") s.push(num1 / num2);
                else return 0; // Encountered invalid operator
            }
        }
            
        return s.top();
    }
    

  • 0
    N

    Good suggestions and the code is very robustness.


Log in to reply
 

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