Reverse Polish notation

The inverse Polish expression of stack application

What is the inverse Polish expression ？？--> Source force buckle 150. Evaluate the inverse Polish expression

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

That is to say, we usually write correctly Addition, subtraction, multiplication and division of numbers , It's all like this .. For example ： ( 1 + 2 ) * ( 3 + 4 )--> Infix expression , And we can make the computer understand ？？-> This introduces today's inverse Polish expression, that is, the suffix expression , Let's turn infix expression into suffix expression .

for example ：1+2*3+(4*2+5)*6

• Add curly braces to all operations
• Move the operator outside the corresponding bracket
• Remove all parentheses

Well, we get a suffix expression --> That is, the calculation that the computer can read

How does the computer calculate the result through such a suffix expression ？？？

That is our magical data structure --> Stack

• When encountering numbers, it will be added to the stack
• When you encounter an operator, you will get two numbers
• The first output is placed on the right side of the operator , The second time out is to the left of the release operator
• After the calculation, continue to put it on the stack
• The final stack top element is the result of the final expression calculation

Code implementation ：

class Solution {
    public int evalRPN(String[] tokens) {
        // Ideas ： When it comes to numbers, put them on the stack , If you encounter a number symbol, you will give two numbers to calculate 
        // Continue to stack the calculation results , Continue to traverse the end of the string 
        Stack<Integer> stack = new Stack<>();
        for(int i =0;i<tokens.length;++i){
            String str = tokens[i];
            if(!isNumCharacter(str)){// Judge whether it is a symbol 
               // If it's a number, put it on the stack 
               int num = Integer.parseInt(str);
               stack.push(num);
            }else{
                // If it's a character, pop the stack , Pop up two numbers 
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(str){
                    case "+":
                         stack.push(num1+num2);
                         break;
                    case "-":
                         stack.push(num1-num2);
                         break;
                    case "*":
                         stack.push(num1*num2);
                         break;
                    case "/":
                         stack.push(num1/num2);
                         break;
                }
            }
        }
        return stack.peek();
    }

  // Used to determine whether this string is a character 
    public boolean isNumCharacter(String s){
        if(s.equals("+")||s.equals("*")||
        s.equals("-")||s.equals("/")){
            return true;
        }
        return false;
    }
}