Introduction to prefix, infix and suffix expressions (code implementation of inverse Polish calculator)

1、 Prefix 、 Infix 、 Postfix expression

1.1、 Prefix expression ( Polish expression )

• Prefix expressions are also called Polish expressions , The operator of the prefix expression precedes the operands ,

• Illustrate with examples ：(3+4)×5-6 The corresponding prefix expression is 【-x+3456】

• Computer evaluation of prefix expressions

  • Scan expressions from right to left , When it comes to numbers , Push numbers onto the stack , When an operator is encountered , Pop up the two numbers at the top of the stack , Use operators to evaluate them （ Stack top element and secondary top element ), And stack the results ; Repeat until the left end of the expression , The final value is the result of the expression
  • for example : (3+4)×5-6 The corresponding prefix expression is -×+3456, The steps for evaluating prefix expressions are as follows :
    • Scan right to left , take 6、5、4、3 Push into the stack
    • encounter + Operator , So pop up 3 and 4(3 For the stack top element ,4 Is the secondary top element ), To calculate the 3+4 Value , have to 7, then 7 Push
    • Next is × Operator , So pop up 7 and 5, To calculate the 7×5=35, take 35 Push
    • And finally - Operator , To calculate the 35-6 Value , namely 29, The final result is

2.2、 Infix expression

• Infix expressions are common operational expressions , Such as (3+4)×5-6
• The evaluation of infix expressions is most familiar to us , But it's not easy to operate for computers ( The case we talked about earlier can see this problem ), therefore , In calculating the result , Infix expressions are often converted to other expressions for operation (— General to suffix expression .)

2.3、 Postfix expression ( Reverse Polish notation )

• Suffix expression is also called inverse Polish expression , Similar to prefix expressions , Just the operator after the operand

• Illustrate with examples ：(3+4)×5-6 The corresponding suffix expression is 34+5×6-

• Computer evaluation of suffix expressions

  • Scan expressions from left to right , When it comes to numbers , Push numbers onto the stack , When an operator is encountered , Pop up the two numbers at the top of the stack , Use operators to evaluate them ( Secondary top element and stack top element ), And stack the results ; Repeat until the right end of the expression , The final value is the result of the expression
  • for example ：(3+4)×5-6 The corresponding suffix expression is 34+5×6-, The evaluation steps for the suffix expression are as follows :
    • Scan from left to right , take 3 and 4 Push into the stack
    • encounter + Operator , So pop up 4 and 3(4 For the stack top element ,3 Is the secondary top element ）, To calculate the 3+4 Value , have to 7, then 7 Push
    • take 5 Push
    • Next is × Operator , So pop up 5 and 7, To calculate the 7×5=35, take 35 Push
    • take 6 Push
    • And finally - Operator , To calculate the 35-6 Value , namely 29, The final result is

2、 Reverse Polish calculator

• Support parentheses and multi bit integers , The calculator is simplified here , Only the addition, subtraction, multiplication and division of integers are supported .

3.1、 Infix expression to suffix expression

• Suffix expression is suitable for computer operation . But it's not easy for people to write , Especially when the expression is very long , So in development , You need to convert infix expression to suffix expression .

• The specific steps are as follows :

  • 1、 Initialize two stacks ： Operator stack s1 And a stack for storing intermediate results s2;
  • 2、 Scan infix expressions from left to right ;
  • 3、 When it comes to operands , Press it down s2;
  • 4.、 When an operator is encountered , Compare it with s1 The priority of the top of stack operator :
    • (1) If s1 It's empty , Or stack top operator is left bracket “(”, This operator will be put on the stack directly ;
    • (2) otherwise , If the priority is higher than the top of the stack operator , Also push operators into s1;
    • (3) otherwise , take s1 The operator at the top of the stack pops up and pushes into s2 in , Turn again (4-1) And s1 New stack top operation in
      Comparison of symbols ;
  • 5、 When brackets are encountered :
    • (1) If it's left parenthesis “(”, Press in directly s1
    • (2) If it's right bracket “)", Then it pops up in turn s1 The operator at the top of the stack , And press in s2, Until we meet the left bracket , This pair of parentheses is discarded
  • 6、 Repeat step 2 to 5, Up to the far right of the expression
  • 7、 take s1 The rest of the operators in the pop-up and press in s2
  • 8、 Pop up one by one s2 And output , The reverse order of the result is the suffix expression corresponding to the infix expression

3.2、 Computer evaluation of suffix expressions

• Scan expressions from left to right , When it comes to numbers , Push numbers onto the stack , When an operator is encountered , Pop up the two numbers at the top of the stack , Use operators to evaluate them ( Secondary top element and stack top element ), And stack the results ; Repeat until the right end of the expression , The final value is the result of the expression
• for example : (3+4)×5-6 The corresponding suffix expression is 34+5×6-, The evaluation steps for the suffix expression are as follows :
  • 1) Scan from left to right , take 3 and 4 Push into the stack ;
  • 2) encounter + Operator , So pop up 4 and 3(4 For the stack top element ,3 Is the secondary top element ), To calculate the 3+4 Value , have to 7, then 7 Push ;
  • 3) take 5 Push ;
  • 4) Next is × Operator , So pop up 5 and 7, To calculate the 7×5=35, take 35 Push ;5) take 6 Push ;
  • 6) And finally - Operator , To calculate the 35-6 Value , namely 29, The final result is

3.3、 Reverse Polish calculator _ Code implementation

public class InfixToSuffix {
    
   public static void main(String[] args) {
    
       //（ One ） Complete the function of converting infix expression to suffix expression 
       /*  explain ： 1. 1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 - 2.  Because directly to str To operate , inconvenient , So first we will str Convert to the corresponding of infix expression List  namely "1+((2+3)*4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] 3. Corresponding to the infix expression List =>  The suffix expression corresponds to List  namely ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] => Arraylist [1,2,3,+,4,*,+,5,-] */
       String expression = "1+((2+3)*4)-5";

       List<String> infixExpressionList = toInfixExpressionList(expression);
       System.out.println(" Infix expression corresponds to List=" + infixExpressionList);//ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]

       List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
       System.out.println(" The suffix expression corresponds to List=" + suffixExpressionList);// The suffix expression corresponds to List=[1, 2, 3, +, 4, *, +, 5, -]
       
       //（ Two ） Computer evaluation method for completing suffix expression 
       int calculate = calculate(suffixExpressionList);
       System.out.printf("expression=%d", calculate);
   }

   // Method ： The infix expression str Convert to corresponding List（str==>list)
   //s=1+((2+3)x4)-5
   public static List<String> toInfixExpressionList(String s) {
    
       // Define a List Store the content corresponding to infix expression 
       List<String> ls = new ArrayList<String>();
       int i = 0; // This is a pointer , Used to traverse infix expression string 
       String str; // Splicing of multi bit numbers 
       char c; // Each traversal of a character , Put it in c
       do {
    
           // If c It's a non number , Need to join in ls
           if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
    
               ls.add("" + c);
               i++; //i Need to move back 
           } else {
     // If it's a number , You need to consider multiple numbers 
               str = ""; // First the str Into a ""
               while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
    
                   str += c; // Splicing 
                   i++;
               }
               ls.add(str);
           }
       } while (i < s.length());
       return ls;
   }

   // Method ： Corresponding to the infix expression List =>  The suffix expression corresponds to List
   //ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] => Arraylist [1,2,3,+,4,*,+,5,-]
   public static List<String> parseSuffixExpressionList(List<String> ls) {
    
       // Define two stacks 
       Stack<String> s1 = new Stack<String>(); // Symbol stack 
       // explain ： because s2 This stack , Throughout the conversion process , No, pop operation , And then you need to output in reverse order , So it's troublesome 
       // Not here Stack<String>,  Use it directly List<String> s2( Sequential output )
       //Stack<String> s2 = new Stack<String>(); // A stack that stores intermediate results s2
       List<String> s2 = new ArrayList<>(); // Store intermediate results List s2

       // Traverse ls
       for (String item : ls) {
    
           // If it's a number , Join in s2
           if (item.matches("\\d+")) {
    
               s2.add(item);
           } else if (item.equals("(")) {
    
               s1.push(item);
           } else if (item.equals(")")) {
    
               // If it's right bracket “)", Then it pops up in turn s1 The operator at the top of the stack , And press in s2, Until we meet the left bracket , This will be displayed — Discard the parentheses 
               //peek() Look at the top of the stack elements 
               while (!s1.peek().equals("(")) {
    
                   s2.add(s1.pop());
               }
               s1.pop(); // take  (  eject s1 Stack , Eliminate parentheses 
           } else {
    
               // When item The priority of is less than or equal to s1 Top of stack operators , take s1 The operator at the top of the stack pops up and adds to s2 in , Turn again (4-1) And s1 Compared with the new stack top operators in ;
               while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
    
                   s2.add(s1.pop());
               }
               // still need sth. item Pressure into the stack 
               s1.push(item);
           }
       }
       // take s1 The remaining operators in pop-up and add s2
       while (s1.size() != 0) {
    
           s2.add(s1.pop());
       }

       return s2; // Note that because it is stored in List, Therefore, the sequential output is the corresponding suffix expression list
   }

   // Complete the operation of the inverse Polish expression 
   /* 1. Scan from left to right , take 3 and 4 Push into the stack  2. encounter + Operator , So pop up 4 and 3（4 For the stack top element ,3 Sub vertex element ）, To calculate the 3+4 Value , have to 7, then 7 Push  3. take 5 Push  4. Next is x Operator , So pop up 5 and 7, To calculate the 7x5=35, take 35 Push  5. take 6 Push  6. And finally - Operator , To calculate the 35-6 Value , namely 29, The final result is  */
   public static int calculate(List<String> ls){
    
       // Create a stack , Just one stack 
       Stack<String> stack = new Stack<>();
       // Traverse ls
       for (String item : ls) {
    
           // Here we use regular expressions to take out numbers 
           /* \d The matching character type is number  + The number of matching characters is more than one  \d It's matching a number ,\d+ Is the match 1 One or more numbers , One more ahead \ To escape  \\d+(\\.\\d+)? Match decimals  */
           if(item.matches("\\d+")){
     // Match the number of multiple bits 
               // Push 
               stack.push(item);
           }else{
    
               // If it's an operator ,pop Two number operations , Go back to the stack 
               int num2 = Integer.parseInt(stack.pop());
               int num1 = Integer.parseInt(stack.pop());
               int res = 0 ; // Store the calculation results 
               if(item.equals("+")){
    
                   res = num1 + num2;
               }else if(item.equals("-")){
    
                   res = num1 - num2; // Number of pop ups after - The number that pops up first 
               }else if(item.equals("*")){
    
                   res = num1 * num2;
               }else if(item.equals("/")){
    
                   res = num1 / num2;
               }else {
    
                   throw new RuntimeException(" Operator error ");
               }
               // hold res Push 
               stack.push(res + "");
           }
       }
       // Finally stay in stack The data in is the result of the operation 
       return Integer.parseInt(stack.pop());
   }
}

// Write a class  Operation  You can return the priority corresponding to an operator 
class Operation {
    
   private static int ADD = 1;
   private static int SUB = 1;
   private static int MUL = 2;
   private static int DIV = 2;

   // Write a method , Returns the priority number corresponding to the operator 
   public static int getValue(String operation) {
    
       int result = 0;
       switch (operation) {
    
           case "+":
               result = ADD;
               break;
           case "-":
               result = SUB;
               break;
           case "*":
               result = MUL;
               break;
           case "/":
               result = DIV;
               break;
           default:
               System.out.println(" The operator does not exist ");
               break;
       }
       return result;
   }
}