LeetCode Q150: 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

Solution:
Not hard, but need to careful about some corner cases, such as when token has only 1 elements and the order of operators when popped from stack.

	class Solution {
	public:
	int evalRPN(vector<string>& tokens) {
	if(tokens.size()==1)
	return stoi(tokens[0]);
	int res=0;
	stack<int> myStack;
	int p=0;
	while(!myStack.empty()||p!=tokens.size()){
	string s=tokens[p];
	if(s.compare("+")==0||s.compare("-")==0||s.compare("*")==0||s.compare("/")==0){
	int op0=myStack.top(); myStack.pop();
	int op1=myStack.top(); myStack.pop();
	int r=0;
	switch(s[0]){
	case '+': r=(op1)+(op0); break;
	case '-': r=(op1)-(op0); break;
	case '*': r=(op1)*(op0); break;
	case '/': r=(op1)/(op0); break;
	}
	if(p!=tokens.size()-1||!myStack.empty())
	myStack.push(r);
	res=r;
	}else{
	int i=stoi(s);
	myStack.push(i);
	}
	p++;
	}
	return res;
	}
	};

view raw Q150.cpp hosted with ❤ by GitHub