Tags


/*
https://oj.leetcode.com/problems/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.
*/

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        if(tokens.empty())
            return 0;
            
        stack<int> opnds;
        for(size_t i=0; i<tokens.size(); i++)
        {
            string& s = tokens[i];
            if(IsOpor(s))
            {
                if(opnds.size()<2)
                    throw -1;//bad expression
                int b = opnds.top();
                opnds.pop();
                int a = opnds.top();
                opnds.pop();
                opnds.push(calc(a, b, s[0]));
            }
            else
            {
                const char* sT = s.c_str();
                char* end;
                int v = strtol(sT, &end, 10);
                if(end==sT || *end!='\0' || errno==ERANGE)
                    throw -3;
                opnds.push(v);
            }
        }
        if(opnds.size() != 1)
            throw -4;
        return opnds.top();
    }
    
    bool IsOpor(const string& s)
    {
        return (s.size() == 1) && (s[0]=='+' || s[0]=='-' || s[0]=='*' || s[0]=='/');
    }
    
    int calc(int a, int b, const char& s)
    {
        int rt = 0;
        switch (s)
        {
            case '+':
                rt = a+b;
                break;
            case '-':
                rt = a-b;
                break;
            case '*':
                rt = a*b;
                break;
            case '/':
                rt = a/b;
                break;
            default:
                throw -2;//unknown operator
        }
        return rt;
    }
};

Advertisements