首页 > 代码库 > Evaluate Reverse Polish Notation

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

说明:使用一个数字栈即可。(也可用数组链表模拟栈)

inline int newPop(stack<int> &digits) {    int v = digits.top();    digits.pop();    return v;}class Solution {public:    int evalRPN(vector<string> &tokens) {        stack<int> digits;        for(size_t id = 0; id < tokens.size(); ++id) {            if((tokens[id][0] == ‘-‘ && tokens[id].size() > 1 ) || 				(tokens[id][0] >= ‘0‘ && tokens[id][0] <= ‘9‘)) digits.push(atoi(tokens[id].c_str()));            else            {                int v;                switch(tokens[id][0]){                    case ‘+‘: {                        digits.push(newPop(digits)+newPop(digits));                        break;                    }                     case ‘-‘: {                        v = newPop(digits);                        digits.push(newPop(digits)-v);                        break;                    }                     case ‘*‘: {                        digits.push(newPop(digits)*newPop(digits));                        break;                    }                     case ‘/‘: {                        v = newPop(digits);                        digits.push(newPop(digits)/v);                        break;                    }                 }            }        }        return digits.top();    }};