題目來源
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

計(jì)算逆波蘭表達(dá)式的值，這個感覺比較簡單，就是利用一個棧，把數(shù)字都進(jìn)棧，然后碰到一個符號就出棧兩個數(shù)字，把結(jié)果進(jìn)棧，直到表達(dá)式結(jié)束或?？?。
就是這么簡陋的寫法，不過至少能AC是不

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

有點(diǎn)長，寫的簡潔一點(diǎn)…

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        int n = tokens.size();
        stack<int> s;
        for (int i=0; i<n; i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int x1 = s.top();
                s.pop();
                int x2 = s.top();
                s.pop();
                if (tokens[i] == "+")
                    s.push(x1 + x2);
                else if (tokens[i] == "-")
                    s.push(x2 - x1);
                else if (tokens[i] == "*")
                    s.push(x1 * x2);
                else
                    s.push(x2 / x1);
            }
            else {
                int x = stoi(tokens[i]);
                s.push(x);
            }
        }
        return s.top();
    }
};

不過寫簡潔了，時間變長了一些，不過其實(shí)復(fù)雜度是一樣的是不。