[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

Hide Tags

 Stack

 

分析：stack的典型应用，逆波兰表达式就是后缀式，遇到操作数入栈，遇到操作符弹出两个操作数，运算后再次入栈。

 

class Solution {
    private:
        int string2Int(const string& str)
        {   
            stringstream strstrm;
            strstrm << str;
            int rtn;
            strstrm >> rtn;
            return rtn;
        }   

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

            if(tokens.size() == 0)
                return 0;

            stack<int> st; 
            int operand1;
            int operand2;
            int rtn;

            for(int i = 0; i < tokens.size(); i++)
            {   
                if(tokens[i] == "+" ||
                        tokens[i] == "-" ||
                        tokens[i] == "*" ||
                        tokens[i] == "/" 
                  )   
                {   
                    operand2 = st.top();
                    st.pop();
                    operand1 = st.top();
                    st.pop();

                    if(tokens[i] == "+")
                        rtn = operand1 + operand2;
                    else if(tokens[i] == "-")
                        rtn = operand1 - operand2;
                    else if(tokens[i] == "*")
                        rtn = operand1 * operand2;
                    else // if(tokens[i] == "/")
                        rtn = operand1 / operand2;

                    st.push(rtn);
                }
                else
                {
                    st.push(string2Int(tokens[i]));
                }

            }
            
            if(!st.empty())
            {
                rtn = st.top();
                st.pop();
            }
            
            return rtn;

        }
};