Problem description:

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.
Example 1:

Input: [“2”, “1”, “+”, “3”, ““]
Output: 9
Explanation: ((2 + 1) 3) = 9
Example 2:

Input: [“4”, “13”, “5”, “/“, “+”]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:

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

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        def digit(num):
            if num.startswith('-') and num[1:].isdigit():
                return True
            elif num.isdigit():
                return True
            return False
        stk = deque()
        # calculate when encounter sign
        for i in tokens:
            if digit(i):
                stk.append(int(i))
            else:
                num2 = stk.pop()
                num1 = stk.pop()
                if i == '+':
                    stk.append(num1+ num2)
                elif i == '-':
                    stk.append(num1- num2)
                elif i == '*':
                    stk.append(num1* num2)
                elif i == '/':
                    stk.append(int(num1/num2))
        return stk[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        string s = tokens.back(); //start from back, check if it's operand or operator
        tokens.pop_back();
        
        if(s != "+" && s != "-" && s != "*" && s != "/") 
            return stoi(s); //it's a number
        
        int r2 = evalRPN(tokens), r1 = evalRPN(tokens); //s is a operator, so we go deeper to find the operand of it.
        //notice that r2 is close to back, so need to call it first.
        //1, 2, /
        //(1/2)
        
        if(s == "+") return r1 + r2;
        if(s == "-") return r1 - r2;
        if(s == "*") return r1 * r2;
        if(s == "/") return r1 / r2;
    }
};