aboutsummaryrefslogtreecommitdiff
path: root/eval_reverse_polish_notation.cpp
blob: 4cd39b872bad3272ea266d93ab7d593bf5a19e4b (plain)
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
46
#include "leetcode.h"

class Solution {
public:
  int evalRPN(vector<string> &tokens) {
    unordered_map<string, function<int(int, int)>> umf = {
        {"+", [](long a, long b) { return a + b; }},
        {"-", [](long a, long b) { return a - b; }},
        {"*", [](long a, long b) { return a * b; }},
        {"/", [](long a, long b) { return a / b; }}};
    stack<long> stk;
    for (string &s : tokens) {
      if (!umf.count(s))
        stk.push(stoi(s));
      else {
        long op1 = stk.top();
        stk.pop();
        long op2 = stk.top();
        stk.pop();
        stk.push(umf[s](op2, op1));
      }
    }
    return static_cast<int>(stk.top());
  }
};

int main() {
  Solution obj;
  vector<string> tokens1 = {"2", "1", "+", "3", "*"};
  // output: 9
  // ((2 + 1) * 3)
  cout << obj.evalRPN(tokens1);
  vector<string> tokens2 = {"4", "13", "5", "/", "+"};
  // output: 6
  // (4 + (13 / 5))
  cout << obj.evalRPN(tokens2);
  vector<string> tokens3 = {"10", "6", "9",  "3", "+", "-11", "*",
                            "/",  "*", "17", "+", "5", "+"};
  // output: 22
  // ((10 * (6 / (12 * -11))) + 17) + 5
  // ((10 * (6 / -132)) + 17) + 5
  // ((10 * 0) + 17) + 5
  // (0 + 17) + 5
  // 17 + 5
  cout << obj.evalRPN(tokens3);
}