题目

binary-tree-postorder-traversal

2. 算法

• 逆波兰

* 栈

* 递归

3. 代码

* 栈

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        if (tokens.size() == 1) return atoi(tokens[0].c_str());
        stack<int> s;
        for (int i = 0; i < tokens.size(); ++i) {
            if (tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") 
　　　　　　　{
                s.push(atoi(tokens[i].c_str()));
            } else {
                int m = s.top();
                s.pop();
                int n = s.top();
                s.pop();
                if (tokens[i] == "+") s.push(n + m);
                if (tokens[i] == "-") s.push(n - m);
                if (tokens[i] == "*") s.push(n * m);
                if (tokens[i] == "/") s.push(n / m);
            }
        }
        return s.top();
    }
};

* 递归

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        int op = tokens.size() - 1;
        return helper(tokens, op);
    }
    int helper(vector<string>& tokens, int& op) {
        string s = tokens[op];
        if (s == "+" || s == "-" || s == "*" || s == "/") {
            int v2 = helper(tokens, --op);
            int v1 = helper(tokens, --op);
            if (s == "+") return v1 + v2;
            else if (s == "-") return v1 - v2;
            else if (s == "*") return v1 * v2;
            else return v1 / v2;
        } else {
            return stoi(s);
        }
    }
};