150 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

• Algorithm: https://www.wikiwand.com/en/Reverse_Polish_notation

  • Explained perfectly

bool is_number(string num) {
    int count = 0;
    if (num.at(count) == '-' && num.length() > 1) count++;
    while (count < num.length() && isdigit(num.at(count)) ) 
        ++count;
    return count == num.length();
}

bool is_negative(string num) {
    return num.at(0) == '-';
}

int operate(string operatr, int one, int two) {
    if (operatr == "+") return one + two;
    else if (operatr == "-") return one - two;
    else if (operatr == "*") return one * two;
    else if (operatr == "/" && two != 0) return one / two;
    return 0;
}

int evalRPN(vector<string>& tokens) {
    unordered_set<string> operators = { "+" , "-", "*", "/" };
    stack<int> s;

    for (int i = 0; i < tokens.size(); i++) {
        if (is_number(tokens.at(i))) {
            s.push(atoi((tokens.at(i).c_str())));
        }
        else if (operators.find(tokens.at(i)) != operators.end()) {
            if (s.empty()) return 0;
            int num1 = s.top(); s.pop();
            if (s.empty()) return 0;
            int num2 = s.top(); s.pop();
            s.push( operate(tokens.at(i), num2, num1) );
        }
    }

    if (s.empty()) return 0;
    int sol = s.top();
    s.pop();
    if (s.empty()) return sol;
    // invalid operator syntax
    else return 0;
}


int main() {
    vector<string> tokens = { "4", "-2", "/", "2", "-3", "-", "-" };
    cout << evalRPN(tokens) << endl;

    tokens = { "2", "1", "+", "3", "*" };
    cout << evalRPN(tokens) << endl;

    tokens = { "4", "13", "5", "/", "+" };
    cout << evalRPN(tokens) << endl;

    tokens = { "4", "3", "-" };
    cout << evalRPN(tokens) << endl;

    tokens = { "-78","-33","196","+","-19","-","115","+","-","-99","/","-18","8","*","-86","-","-","16","/","26","-14","-","-","47","-","101","-","163","*","143","-","0","-","171","+","120","*","-60","+","156","/","173","/","-24","11","+","21","/","*","44","*","180","70","-40","-","*","86","132","-84","+","*","-","38","/","/","21","28","/","+","83","/","-31","156","-","+","28","/","95","-","120","+","8","*","90","-","-94","*","-73","/","-62","/","93","*","196","-","-59","+","187","-","143","/","-79","-89","+","-" };
    cout << evalRPN(tokens) << endl;
}