Stack and queue - 150. Inverse Polish expression evaluation

1 Title Description

according to Reverse Polish notation , Find the value of the expression .

Valid operators include +、-、*、/ . Each operand can be an integer , It can also be another inverse Polish expression .

Be careful The division between two integers retains only the integer part .

It can be guaranteed that the given inverse Polish expression is always valid . let me put it another way , The expression always yields a valid number and does not have a divisor of 0 The situation of .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/evaluate-reverse-polish-notation
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2 Title Example

Example 1：
Input ：tokens = [“2”,“1”,“+”,“3”,“*”]
Output ：9
explain ： This formula is transformed into a common infix arithmetic expression as ：((2 + 1) * 3) = 9

Example 2：
Input ：tokens = [“4”,“13”,“5”,“/”,“+”]
Output ：6
explain ： This formula is transformed into a common infix arithmetic expression as ：(4 + (13 / 5)) = 6

Example 3：
Input ：tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]
Output ：22
explain ： This formula is transformed into a common infix arithmetic expression as ：
((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

3 Topic tips

1 <= tokens.length <= 104
tokens[i] It's an operator （“+”、“-”、“*” or “/”）, Or in the range [-200, 200] An integer in

Reverse Polish notation ：

The inverse Polish expression is a suffix expression , The so-called suffix means that the operator is written after .

The usual formula is a infix expression , Such as ( 1 + 2 ) * ( 3 + 4 ) .
The inverse Polish expression of the formula is written as ( ( 1 2 + ) ( 3 4 + ) * ) .
The inverse Polish expression has two main advantages ：

There is no ambiguity in the expression after removing the brackets , Even if the above formula is written as 1 2 + 3 4 + * You can also calculate the correct result according to the order .
It is suitable for stack operation ： When it comes to numbers, it's on the stack ; When you encounter an operator, you take out two numbers at the top of the stack to calculate , And push the results into the stack

4 Ideas

The inverse Polish expression strictly follows 「 From left to right 」 Arithmetic . When evaluating the value of the inverse Polish expression , Use a stack to store operands , Traverse the inverse Polish expression from left to right , Do the following :
If an operand is encountered , Put the operands on the stack ;
If you encounter an operator , Then the two operands are out of the stack , The first out of the stack is the right operand , The last one out of the stack is the left operand , Use the operator to operate on two operands , Put the new operand obtained by the operation on the stack .
After traversing the entire inverse Polish expression , There is only one element in the stack , This element is the value of the inverse Polish expression .

Complexity analysis
· Time complexity :O(n), among n It's an array tokens The length of . You need to go through groups tokens— Time , Calculate the value of the inverse Polish expression .
· Spatial complexity :O(n), among n It's an array tokens The length of . Use the stack to store the number in the calculation process , The number of elements in the stack will not exceed the length of the inverse Polish expression .

5 My answer

class Solution {
    
    public int evalRPN(String[] tokens) {
    
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
    
            String token = tokens[i];
            if (isNumber(token)) {
    
                stack.push(Integer.parseInt(token));
            } else {
    
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
    
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }

    public boolean isNumber(String token) {
    
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}