Monday, June 1, 2015

[LintCode] 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.
Example

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
class Solution {
public:
    /**
     * @param tokens The Reverse Polish Notation
     * @return the value
     */
    int evalRPN(vector<string>& tokens) {
        // Write your code here
        int len = tokens.size();
        if(len == 0) return 0;
        stack<int> s;
        int start = 0;
        while(start<len){
            
            if(tokens[start].length() == 1 
                && !isalnum(tokens[start][0])) {
                
                int a = s.top();
                s.pop();
                int b = s.top();
                s.pop();
                if(tokens[start][0] == '+') s.push(a+b);
                else if(tokens[start][0] == '-') s.push(b-a);
                else if(tokens[start][0] == '*') s.push(a*b);
                else if(tokens[start][0] == '/') s.push(b/a);
            }
            else {
                s.push(stoi(tokens[start]));
            }
            start++;
        }
        
        return s.top();
    }
};