LeetCode_ Stack_ Medium_ 150. evaluation of inverse Polish expression

1. subject

According to the 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 .

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

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/evaluate-reverse-polish-notation

2. Ideas

（1） Stack
This problem directly gives the inverse Polish expression , Just follow the steps to calculate the inverse Polish expression and write the code , In this process, we need to use the data structure of stack .
① Define a stack stack , Used to store intermediate calculation results , When there is only one element left in the stack , Then this value is the final answer ;
② To traverse the tokens, For each token, Make the following judgment ：
1） If at present token It's the operator , namely +、-、*、/ One of the （ Set to op）, Then take out the two elements closest to the top of the stack （ Set as num1 and num2）, And will num2 op num1 Stack the results of ;
2） If the current tag is an integer , Then stack it ;
③ tokens After the traversal is over , Just return the top element of the stack .

3. Code implementation （Java）

// Ideas 1———— Stack 
class Solution {
    
    public int evalRPN(String[] tokens) {
    
        Stack<Integer> stack = new Stack<>();
        for (String str : tokens) {
    
            if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
    
                /*  Currently marked as operator , Let the two elements closest to the top of the stack be  num1  and  num2  take  num2 op num1  Stack the results of  */
                int num1 = stack.pop();
                int num2 = stack.pop();
                int tmpRes;
                if (str.equals("+")) {
    
                    tmpRes = num2 + num1;
                } else if (str.equals("-")) {
    
                    tmpRes = num2 - num1;
                } else if (str.equals("*")) {
    
                    tmpRes = num2 * num1;
                } else {
    
                    tmpRes = num2 / num1;
                }
                stack.push(tmpRes);
            } else {
    
                // Currently marked as an integer , Stack it 
                stack.push(Integer.parseInt(str));
            }
        }
        return stack.pop();
    } 
}