150. Evaluate Reverse Polish Notation.md

150. Evaluate Reverse Polish Notation

思路

当时学栈的时候应该有学过逆波兰表达式, 逆波兰表达式就是把操作数放前面，把操作符后置的一种写法. 由于题目说了给的表达式肯定是合法的, 所以我们可以很容易用栈解决: 从前往后遍历一遍表达式, 若是数字则进栈, 若是四则符号之一, 则pop出栈顶的两个元素进行相应运算, 并将运算结果压入栈中. 遍历完成后栈中只剩下一个元素即最终结果.

空间和时间复杂度都是O(n)

注意我们可以使用函数stoi()很方便将字符串转换成整数.

C++

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