Data structure and algorithm two :2) stack with application – inverse Polish expression

“This is the 14th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge.”

Follow me for more updates

Data structure and algorithm (I): time complexity and space complexity

Data structure and algorithm (2): stack

Data structure and algorithm (3): queue

Data structure and algorithm (4): single linked list

Data structure and algorithm (5): two-way linked list

Data structure and algorithm (6): hash table

Data Structures and algorithms (7): trees

Data Structure and algorithm (8): sorting algorithm

Data Structures and algorithms (9): classical algorithm interview questions

A preview

Last we introduced the data structure and algorithm two :1) stack this mainly introduces the application of inverse Polish expression, inverse Polish expression is the suffix expression

Infix expression is very intuitive for us (we usually contact is this), but the computer to handle more troublesome (parentheses, priority and so on), the prefix and postfix expression without parentheses (because the infix expression into the before/after the postfix expression brackets, still keep the correct calculation order), In addition, only one-way scanning (right to left for prefix expressions and left to right for postfix expressions) is required in the calculation, without considering the priority of operators.

Binary suffixed expression

Postfix expressions are also called inverse Polish expressions. The operator of postfix expressions comes after the operand.

For example, (3+4)x5-6 corresponds to 3 4 + 5 x 6 -; How do postfix expressions come from, and we’ll talk about how do you convert infix expressions to postfix expressions

Such as:

1. Evaluation of postfix expression:

1) Calculation idea

Take numbers from left to right until an operator is fetched. The two operands that are just fetched next to the operator are evaluated by the operator, and the result is backfilled to the operator. Repeat this step until there is only one string left and the remaining string is the result.

The calculation rules for prefix expressions are similar to those for postfix expressions, except that the scan direction is opposite. Preorder expressions go from right to left, and postorder expressions go from left to right.

2) Code ideas

① Calculation rules

The expression is scanned from left to right, and when it encounters a number, it pushes the number onto the stack. When it encounters an operator, it pops the top two numbers on the stack, evaluates them with the operator (the sub-top element and the top element), and pushes the result onto the stack. Repeat this process until you reach the right end of the expression, and the resulting value is the result of the expression

② Calculation process

Taking the postfix expression ‘3 4 + 5 x 6 -‘ as an example, the evaluation steps are as follows:

1. Scanning from left to right, push 3 and 4 onto the stack;
2. The + operator is encountered, so pop 4 and 3 (4 is the top element, 3 is the second top element), calculate the value of 3+4, get 7, and push 7.
3. Push 5;
4. Next comes the × operator, so pop 5 and 7, calculate 7×5=35, push 35;
5. Push 6;
6. Finally, there is the – operator, which computes the value 35-6, which is 29, to give the final result

Suffix expression evaluation code (first convert the string to an array)

/** 1) Scan from left to right, push 3 and 4 onto the stack; 2) The + operator is encountered, so pop 4 and 3 (4 is the top element, 3 is the second top element), calculate the value of 3+4, get 7, and push 7; 3) Push 5; 4) Next comes the × operator, so pop 5 and 7, calculate 7×5=35, push 35; 5) Push 6; 6) Finally comes the - operator, which calculates the value 35-6, which is 29, */ public static int calculate(List<String> ls) {Stack<String> Stack = new Stack<String>(); If (item.matches("\\d+")) {// Stack. Push (item); Int num2 = integer.parseint (stack.pop()); int num1 = Integer.parseInt(stack.pop()); int res = 0; if (item.equals("+")) { res = num1 + num2; } else if (item.equals("-")) { res = num1 - num2; } else if (item.equals("*")) { res = num1 * num2; } else if (item.equals("/")) { res = num1 / num2; } else {throw new RuntimeException(" operator error "); Stack. Push ("" + res); }} // Return integer.parseint (stack.pop()); }Copy the code

2. Change the infix expression to the postfix expression

steps

Step 1) Initialize two stacks: operator stack S1 and intermediate result stack S2; 2) Scan infix expressions from left to right; 3) When the operand is encountered, press it into S2; 4.1) If s1 is empty or the top stack operator is an open parenthesis ((), push the operator directly; 4.2) Otherwise, push the operator into S1 if its priority is higher than that of the top operator; 4.3) Otherwise (priority less than/equal to the top of the stack operator), pop the top of the stack operator in S1 and push it into S2, again going to (4.1) compare with the new top of the stack operator in S1. 5.1) If open parenthesis "(", press s1 directly 5.2) If close parenthesis") ", pop the operators at the top of s1 and press S2 until open parenthesis is encountered, at which point the parentheses are discarded 6) Repeat steps 2 through 5, Until the rightmost part of the expression 7) pops the remaining operators in S1 and pushes them into S2 8) pops the elements in S2 and prints them out, the reverse order of the result being the postfix expression corresponding to the infix expressionCopy the code

For example, the process of converting the infix expression “1 +((2+3)×4)-5 “into a postfix expression is as follows, so the result is “1 2 3 + 4 × + 5 -“.

The code is as follows:

/ / infix expression to the corresponding List to a postfix expression corresponding List / / the ArrayList [1, +, -, -, 2, +, 3), *, 4,), -, 5] = "ArrayList [1, 2, 3, 4 +, *, +, 5 -] public static A List < String > parseSuffixExpreesionList (a List < String > ls) {/ / define two Stack: symbol Stack and store the intermediate results 桟 Stack < String > s1 = new Stack < String > (); // Symbol stack // For s2, there is no pop operation during the conversion process, and we need to output in reverse order later, so it is troublesome. List<String> s2 //Stack<String> s2 = new Stack<String>(); S2 List<String> s2 = new ArrayList<String>(); Ls for(String item: ls) {if(item.matches("\\d+"))) {// match multiple digits s2.add(item); } else if (item.equals("(")) {s1.push(item); } else if (item.equals(")");} else if (item.equals(")"); s1.peek().equals("(")) { s2.add(s1.pop()); } s1.pop(); / /!!!!!! Else {// If the priority of item is less than or equal to the s1 top operator, pop the S1 top operator and add it to S2, Go to (4.1) again to compare with the new top of the stack operator in s1 // Note: there is a method to compare the priority of Operation.getValue() while(s1.size()! = 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item) ) { s2.add(s1.pop()); S1. push(item); While (s1.size()!); = 0) { s2.add(s1.pop()); } return s2; // Note that the output sequence is the List} corresponding to the suffix expression.Copy the code

3. The application of suffix expression – inverse Polish calculator complete code

For example, calculate 1+(2+3)×4)-5

/** Make an inverse Polish calculator: for example, calculate 1+((2+3)×4)-5. 1+((2+3)×4)-5 => Turn to 1 2 3 + 4 × + 5 -- Step 3: Evaluate the expression */ public static void main(String[] args) {String expression = "1 + (2 + 3) * 4) - 5"; // First step: convert the string of the infix expression to an array // Because it is inconvenient to operate on STR directly, List<String> infixExpressionList = toInfixExpressionList(expression); Println (" infixExpressionList =" + infixExpressionList); ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] ArrayList [1,+,(,(,2,+,3,),*,4,),-,5 parseSuffixExpreesionList(infixExpressionList); System.out.println(" suffixExpreesionList "+ suffixExpreesionList); Printf ("expression=%d", calculate(suffixExpreesionList)); //ArrayList [1,2,3,+,4,*,+,5, --]; }Copy the code

// s="1+((2+3)×4)-5"; // s="1+((2+3)×4)-5"; Public static List<String> toInfixExpressionList(String s) {public static List<String> toInfixExpressionList(String s) ArrayList<String>(); int i = 0; // This is a pointer to iterate over the infix expression String String STR; // Char c; / / each traversal to one character at a time, into the c do {/ / if c is a non-numeric, I need to join ls the if ((c = s.c harAt (I)) < 48 | | (c = s.c harAt (I)) > 57) {ls. Add (" "+ c); i++; } else {// if it is a number, it needs to consider multiple digits STR = ""; / / STR first into a "" '0' [48] - > '9' [57] while (I < s.l ength () && (c = s.c harAt (I)) > = 48 && (c = s.c harAt (I)) < = 57) {STR + = c; / / stitching i++; } ls.add(str); } }while(i < s.length()); return ls; / / return}Copy the code

/ / the second step: the infix expression corresponding List to a postfix expression corresponding List / / the ArrayList [1, +, -, -, 2, +, 3), *, 4,), -, 5] = "ArrayList [1, 2, 3, 4 +, *, +, 5 -] public Static a List < String > parseSuffixExpreesionList (a List < String > ls) {/ / define two Stack: symbol Stack and store the intermediate results 桟 Stack < String > s1 = new Stack<String>(); // Symbol stack // For s2, there is no pop operation during the conversion process, and we need to output in reverse order later, so it is troublesome. List<String> s2 //Stack<String> s2 = new Stack<String>(); S2 List<String> s2 = new ArrayList<String>(); Ls for(String item: ls) {if(item.matches("\\d+"))) {// match multiple digits s2.add(item); } else if (item.equals("(")) {s1.push(item); } else if (item.equals(")");} else if (item.equals(")"); s1.peek().equals("(")) { s2.add(s1.pop()); } s1.pop(); / /!!!!!! Else {// If the priority of item is less than or equal to the s1 top operator, pop the S1 top operator and add it to S2, Go to (4.1) again to compare with the new top of the stack operator in s1 // Note: there is a method to compare the priority of Operation.getValue() while(s1.size()! = 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item) ) { s2.add(s1.pop()); S1. push(item); While (s1.size()!); = 0) { s2.add(s1.pop()); } return s2; // Note that the output sequence is the List} corresponding to the suffix expression.Copy the code

// Step 3: Evaluate the inverse Polish expression /** 1) Scan from left to right, push 3 and 4 onto the stack; 2) The + operator is encountered, so pop 4 and 3 (4 is the top element, 3 is the second top element), calculate the value of 3+4, get 7, and push 7; 3) Push 5; 4) Next comes the × operator, so pop 5 and 7, calculate 7×5=35, push 35; 5) Push 6; 6) Finally comes the - operator, which calculates the value 35-6, which is 29, */ public static int calculate(List<String> ls) {Stack<String> Stack = new Stack<String>(); If (item.matches("\\d+")) {// Stack. Push (item); Int num2 = integer.parseint (stack.pop()); int num1 = Integer.parseInt(stack.pop()); int res = 0; if (item.equals("+")) { res = num1 + num2; } else if (item.equals("-")) { res = num1 - num2; } else if (item.equals("*")) { res = num1 * num2; } else if (item.equals("/")) { res = num1 / num2; } else {throw new RuntimeException(" operator error "); Stack. Push ("" + res); }} // Return integer.parseint (stack.pop()); }Copy the code

Class Operation {private static int ADD = 1; private static int SUB = 1; private static int MUL = 2; private static int DIV = 2; 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(" this operator does not exist "+ operation); break; } return result; }}Copy the code

3 pay attention to my

If you think I wrote a good, please point to follow me your support is my more the biggest motivation!