算法

。。。。

时间复杂度 $O(n)$

C++ 代码

class Solution {
public:
    stack<int> sk;
    int evalRPN(vector<string>& tokens) {
        for(auto str:tokens)
        {
            if(str.size()>1||str[0]>='0'&&str[0]<='9')
                sk.push(atoi(str.c_str()));
            else
            {

                int a = sk.top();
                sk.pop();
                int b= sk.top();
                sk.pop();
                // cout << a<<str[0]<<b<<endl;
                if(str[0]=='+')
                    sk.push(a+b);
                else if(str[0]=='*')
                    sk.push(a*b);
                else if(str[0]=='-')
                    sk.push(b-a);
                else
                    sk.push(b/a);
            }
        }
        return sk.top();
    }
};