C++: Evaluate Reverse Polish Notation

Thought Process

To evaluate Reverse Polish Notation (RPN), we use a stack to keep track of operands. When we encounter an operator, we pop the top two elements from the stack, perform the operation, and push the result back onto the stack. For numbers, we simply push them onto the stack. The key is to process tokens sequentially and use the stack to handle operands and operations efficiently. At the end, the final result is the only element left on the stack. 

class Solution {
public:
    int evalRPN(vector<string>& tokens) {

        stack<int> st;
        bool isOperator=false;

        for(int i=0;i<tokens.size();i++){

            string str = tokens[i];
            if(str=="+" || str=="-" || str=="*" || str=="/")
                isOperator = true;
            else
                isOperator = false;
            
            if(isOperator){
                int a = st.top(); 
                st.pop();
                int b = st.top(); 
                st.pop();
                if(str=="+"){
                    st.push(b+a);
                }
                else if(str=="-"){
                    st.push(b-a);
                }
                else if(str=="*"){
                    st.push(b*a);
                }
                else{
                    st.push(b/a);
                }
            }
            else{
                int val = stoi(str);
                st.push(val);
            }
        }
        return st.top();
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm processes each token once, where 'n' is the number of tokens.

Space Complexity: O(n)

The stack can store up to 'n' elements in the worst case.

Code copied!