Leetcode skimming: stack and queue 05 (inverse Polish expression evaluation)

150. Evaluate the inverse Polish expression

Force button topic link

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 .

explain ：

Integer division keeps only the integer part .
Given an 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 : [“2”, “1”, “+”, “3”, " * "]
• Output : 9
• explain : This formula is transformed into a common infix arithmetic expression as ：((2 + 1) * 3) = 9

Example 2：

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

Example 3：

• Input : [“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    
  

Stack operation ： When it comes to numbers, put them on the stack , The first one out of the stack is addend 、 Subtract 、 Divisor 、 The multiplier ; The last one out of the stack is the addend 、 minuend 、 Divisor 、 Multiplier .
When it comes to numbers, it's on the stack 、 When encountering an operator, take out the two numbers at the top of the stack for calculation , Then push the result into the stack .

package com.programmercarl.stacks_queues;

import java.util.Stack;

/** * @ClassName EvalRPN * @Descriotion TODO * @Author nitaotao * @Date 2022/6/30 13:26 * @Version 1.0 **/
public class EvalRPN {
    
    public int evalRPN(String[] tokens) {
    
        Stack stack = new Stack();
        for (int i = 0; i < tokens.length; i++) {
    
            switch (tokens[i]) {
    
                case "+":
                    // Addition number 
                    Integer num1 = Integer.valueOf((String) stack.pop());
                    // Augend 
                    Integer num2 = Integer.valueOf((String) stack.pop());
                    stack.push(String.valueOf(num2 + num1));
                    break;
                case "-":
                    // Subtract 
                    Integer num3 = Integer.valueOf((String) stack.pop());
                    // minuend 
                    Integer num4 = Integer.valueOf((String) stack.pop());
                    stack.push(String.valueOf(num4 - num3));
                    break;
                case "*":
                    // The multiplier 
                    Integer num5 = Integer.valueOf((String) stack.pop());
                    // Multiplier 
                    Integer num6 = Integer.valueOf((String) stack.pop());
                    stack.push(String.valueOf(num6 * num5));
                    break;
                case "/":
                    // Divisor 
                    Integer num7 = Integer.valueOf((String) stack.pop());
                    // Divisor 
                    Integer num8 = Integer.valueOf((String) stack.pop());
                    stack.push(String.valueOf(num8 / num7));
                    break;
                default:
                    stack.push(tokens[i]);
            }
        }
        return Integer.valueOf((String) stack.pop());
    }
}

Again AC, comfortable .！