# 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
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;
}