题目描述

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

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

Note:

Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

样例

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

算法1

维护一个ans，把前面的数字全部压到栈里，每次用碰到的符号处理栈顶的两个数 如果是第一次计算就是第一个符号前的两个数字 如果不是就是上次计算的结果和一个没用过的数字计算 然后把ans压栈
ans压栈后有两种情况
1. 有新数字（x）入栈参与计算 即 ans +-/ x
2. 有连续的计算符号 ans作为括号内数值出栈 即 c +-/ (f(.) = ans)

（萌新不太确定复杂度 有错请指出）
时间复杂度 O(N) 每个元素 压栈弹栈和计算都是O(1)的操作 但是如果位数很多(平均m位) 算上stoi 应该会到0（m * N）
空间复杂度 O(N) 就栈里存int 和维护ans

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        int ans = stoi(tokens[0]);
        int n =0;
        unordered_set<string> sign{"+","-","*","/"};
        while(n < tokens.size()){
            if(sign.count(tokens[n])){
                int a = s.top();
                s.pop();
                    if(tokens[n] == "+") ans = s.top() + a, s.pop();
                    if(tokens[n] == "-") ans = s.top() - a, s.pop();
                    if(tokens[n] == "*") ans = s.top() * a, s.pop();
                    if(tokens[n] == "/") ans = s.top() / a, s.pop();
                    s.push(ans);
                n++;
            }
            else{
                s.push(stoi(tokens[n]));
                n++;
            }
        } 

        return ans;
    }
};