Evaluate Reverse Polish Notation

LeetCode #150


Description:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Example:

Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Idea:

用stack,计算一次算一个结果,重新放入stack。每个operator都需要两个数。自己写bool isOperator(string s)来判断是不是operator。

Code:

class Solution {
public:
    int evalRPN(vector<string>& tokens) {

        stack<int> nums;
        for(const auto & token : tokens){
            if(!isOperator(token)){
                nums.push(atoi(token.c_str()));
            }
            else{
                int right=nums.top();
                nums.pop();
                int left=nums.top();
                nums.pop();
                if(token[0]=='+'){
                    nums.push(left+right);
                }
                else if(token[0]=='-'){
                    nums.push(left-right);
                }
                else if(token[0]=='*'){
                    nums.push(left*right);
                }
                else if(token[0]=='/'){
                    nums.push(left/right);
                }
            }
        }

        return nums.top();
    }
    bool isOperator(string s){
        if(s.size()==1 && string("+-*/").find(s)!=string::npos)
            return true;
        else
            return false;
    }
};

results matching ""

    No results matching ""