150. Evaluate Reverse Polish Notation

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> sta;
        int ret= 0;
        for(string str:tokens ){
            if(str == "+" || str == "-" || str=="*" || str=="/"){
                int a = sta.top(); sta.pop();
                int b = sta.top(); sta.pop();
                if(str == "+") sta.push(b+a);
                else if(str =="-") sta.push(b-a);
                else if(str=="*") sta.push(b*a);
                else if(str=="/") sta.push(b/a);
                
            }
            else{
                sta.push(stoi(str));
            }
        }
        return sta.top();
    }
};

analysis

  • time complexity O(n)
  • space complexit O(n)