You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

  • The valid operators are '+', '-', '*', and '/'.
  • Each operand may be an integer or another expression.
  • The division between two integers always truncates toward zero.
  • There will not be any division by zero.
  • The input represents a valid arithmetic expression in a reverse polish notation.
  • The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

Input: tokens = ["2","1","+","3","*"]

Output: 9

Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]

Output: 6

Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["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

Constraints:

  • 1 <= tokens.length <= 104
  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

题目分析

Stack

代码实现

class Solution {
public:
    stack <int> st;
    unordered_map <string, bool> hx = {{"+", 1}, {"-", 1}, {"*", 1}, {"/", 1}};
    void calc(char op) {
        int b = st.top(); st.pop();
        int a = st.top(); st.pop();
        int c;
        switch(op) {
            case '+':
                c = a + b;
                break;
            case '-':
                c = a - b;
                break;
            case '*':
                c = a * b;
                break;
            case '/':
                c = a / b;
                break;
        }
        st.push(c);
    }
    int evalRPN(vector<string>& tokens) {
        for(auto& s : tokens) {
            if(hx[s]) calc(*s.begin());
            else st.push(stoi(s.c_str()));
        }
        return st.top();
    }
};
分类: Stack

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status