DSA-Practice/DAY0088.cpp at main · Krrish-29/DSA-Practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 150. Evaluate Reverse Polish Notation
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        //time efficient but not memory efficient
        // stack<int>stack;
        // int size=tokens.size();
        // for(int i=0;i<size;i++){
        //     if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){
        //         int op2=stack.top();
        //         stack.pop();
        //         int op1=stack.top();
        //         stack.pop();
        //         if(tokens[i]=="+") stack.push(op1+op2);
        //         if(tokens[i]=="-") stack.push(op1-op2);
        //         if(tokens[i]=="*") stack.push(op1*op2);
        //         if(tokens[i]=="/") stack.push(op1/op2);
        //     }
        //     else{
        //         stack.push(stoi(tokens[i]));
        //     }
        // }
        // return stack.top();

        // memory efficient but not time efficient
        vector<int>stack;
        int size=tokens.size();
        for(int i=0;i<size;i++){
            if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){
                int op2=stack.back();
                stack.pop_back();
                int op1=stack.back();
                stack.pop_back();
                if(tokens[i]=="+") stack.push_back(op1+op2);
                if(tokens[i]=="-") stack.push_back(op1-op2);
                if(tokens[i]=="*") stack.push_back(op1*op2);
                if(tokens[i]=="/") stack.push_back(op1/op2);
            }
            else{
                stack.push_back(stoi(tokens[i]));
            }
        }
        return stack.front();
    }
};