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

My codes:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//
//  main.cpp
//  02. Evaluate Reverse Polish Notation
//
//  Created by Yingbo Miao on 2014-06-21.
//  Copyright (c) 2014 Yingbo Miao. All rights reserved.
//
#include <iostream>
#include <sstream>
#include <list>
#include <vector>

using namespace std;
class Solution {
public:
    list<int> stack;
   
    int evalRPN(vector<string> &tokens) {
        int ret = 0;
        int a = 0;
        int b = 0;
        for (vector<string>::iterator itToken = tokens.begin(); itToken != tokens.end(); ++itToken) {
            string & token = *itToken;
            if (is_calculator(token)) {
                b = stack.back();
                stack.pop_back();
                a = stack.back();
                stack.pop_back();
                ret = calculate(a, b, token);
                stack.push_back(ret);
            } else {
                stack.push_back(string_to_int(token));
            }
        }
        return stack.back();
    }
   
    int calculate(int a, int b, const string& operator_str) {
        int res = 0;
        if (operator_str == "+") {
            res = a+b;
        } else if (operator_str == "-") {
            res = a-b;
        } else if (operator_str == "*") {
            res = a * b;
        } else {
            res = a/b;
        }
       
        return res;
    }
   
   
   
    int string_to_int(const string& s) {
        int ret = 0;
        istringstream iss(s);
        iss >> ret;
        return ret;
    }
   
    bool is_calculator(const string &token) const {
        return token == "+" || token == "-" || token == "*"  ||token == "/";
    }
};
int main(int argc, const char * argv[]) {
    Solution run = Solution();
    vector<string> tokens;
    // ["2", "1", "+", "3", "*"]
    tokens.push_back("2");
    tokens.push_back("1");
    tokens.push_back("+");
    tokens.push_back("3");
    tokens.push_back("*");
   
    int res = run.evalRPN(tokens);
    cout << res << endl;
   
    tokens.clear();
    //["4", "13", "5", "/", "+"]
    tokens.push_back("4");
    tokens.push_back("13");
    tokens.push_back("5");
    tokens.push_back("/");
    tokens.push_back("+");
   
    res = run.evalRPN(tokens);
    cout << res << endl;
}

Leave a Comment