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.

http://www.lintcode.com/en/problem/evaluate-reverse-polish-notation/

Discussion

从左到右读输入，若是数字入栈；若是字符出栈两次得到两个操作数。
Example：计算出来的结果再入栈，注意先出来的数是第二个操作数，比如“3-4”对应的字符串是“3 4 -”，当都到“-”时先弹出4再弹出3.

对Polish Notation，是从右往左读，第一个出来的就是第一个操作数，第二个弹出来的就是第二个操作数。

Solution

class Solution {
public:
    /**
     * @param tokens The Reverse Polish Notation
     * @return the value
     */
    int evalRPN(vector<string>& tokens) {
        if(tokens.empty()) return 0;
        stack<int> operands;
        for(auto const& str : tokens) {
            if(str == "+") {
                if(operands.size() < 2) return 0; //error
                int a = operands.top();
                operands.pop();
                int b= operands.top();
                operands.pop();
                operands.emplace(b+a);
            } else if(str == "-") {
                if(operands.size() < 2) return 0; //error
                int a = operands.top();
                operands.pop();
                int b= operands.top();
                operands.pop();
                operands.emplace(b-a);
            } else if (str == "*") {
                if(operands.size() < 2) return 0; //error
                int a = operands.top();
                operands.pop();
                int b= operands.top();
                operands.pop();
                operands.emplace(b*a);
            } else if (str == "/") {
                if(operands.size() < 2) return 0; //error
                int a = operands.top();
                operands.pop();
                int b= operands.top();
                operands.pop();
                operands.emplace(b/a);
            } else {
                operands.emplace(stoi(str));
            }
        }
        if(operands.size() != 1) return 0;
        return operands.top();
    }
};

更简洁的写法：

class Solution {
public:
    /**
     * @param tokens The Reverse Polish Notation
     * @return the value
     */
    int evalRPN(vector<string>& tokens) {
        if(tokens.empty()) return 0;
        stack<int> operands;
        for(auto const& str : tokens) {
            if(!isOperator(str)) {
                operands.emplace(stoi(str));
            } else {
                if(operands.size() < 2) return 0; //error
                int a = operands.top();
                operands.pop();
                int b= operands.top();
                operands.pop();
                if(str == "+") {
                operands.emplace(b+a);
                } else if(str == "-") {
                    operands.emplace(b-a);
                } else if (str == "*") {
                    operands.emplace(b*a);
                } else if (str == "/") {
                    operands.emplace(b/a);
                } 
            }
        }
        if(operands.size() != 1) return 0;
        return operands.top();
    }
    bool isOperator(string op) {
        string str = "+-*/";
        return op.length()==1 && str.find(op) != string::npos;
    }
};

Follow up

如果题目给的不是string vector，而是要从一个长字符串中解析出需要的string呢？用istringstream，例如：

std::istringstream is(input); //用input string声明个istringstream
    string st0;
    while (is >> st0) {
        cout << st0 << endl;//逐次解析出来里面的string
    }

需要注意的是istringstream默认的是用空格作为分隔符的。若是comma，用while (getline(is, st0, ','))

Reference

1. Polish notation

2. Reverse Polish Notation