Application of stack – postfix expression

The stack is not new, and one of its applications is postfix expressions

Origin of postfix expressions

Ordinary mathematical calculations such as 7*8,3+4, etc. can be easily written out through the program to get the result, but for some complex formulas :(3+4) × 5-6, this kind of calculation is more difficult to solve. We call the above standard four operation expressions, namely (3+4)×5-6, infix expressions. Because all the symbols are in the middle of two numbers. Postfix expressions place operators after operands, as in

3, 4 plus 5 times 6 minusCopy the code

You can see that there are no parentheses in the postfix expression, just the order of the computation, which happens to be the machine’s favorite way.

The calculation process of postfix expression

Take the book as an example to calculate: 9+(3-1)×3+10÷2 to see how the stack is calculated

Let’s start with the rules that the machine uses to evaluate postfix expressions:

• Iterate over each number and symbol of the expression from left to right, pushing if it is a number
• When the symbol is encountered, the two numbers at the top and the next top of the stack are removed and computed
• The result of the operation is pushed onto the stack until the final result is obtained

Detailed steps:

1. Initialize an empty stack. This stack is used to handle the number in and out.

2. The first three postfix expressions are all numbers, so 9, 3, and 1 are pushed.

3. This is followed by a minus sign “-“, so 1 is removed from the stack as the subtraction, 3 is removed from the stack as the minuend, and 3-1 is computed to get 2, which is then pushed onto the stack.

4. Then the number 3 is pushed.

5. This is followed by the multiplication “*”, which means that 3 and 2 are pushed off the stack, and 2 is multiplied by 3 to get 6, which is pushed onto the stack.

6. And then we have the addition “+”, so we find the 6 and the 9, and we add the 9 to the 6, and we get 15, and we push 15.

7. Then the numbers 10 and 2 are stacked.

8. And then there’s the sign so the 2 at the top of the stack goes off the stack with 10, 10 goes off the stack with 2, you get 5, you push 5.

9. The last one is the sign “+”, so 15 and 5 go out and add them up, and you get 20

The results obtained are in agreement with the normal calculation results

Suffixes to suffixes

At this point, the core problem becomes how to transfer infix to suffix, and the transformation process is also completed by stack.

2. Operator 2.1: "(" directly onto the stack 2.2:") "pushes the elements of the symbol stack one by one and prints them until" (", "(" only out of the stack, no output 2.3: For other symbols, each element in the symbol stack is pushed off the stack and printed until a symbol with lower precedence than the current symbol or "(" is encountered. Pushes the current symbol onto the stack. 3. After scanning, output the remaining symbols on the stackCopy the code

Let’s look at the process in detail:

1. Initializes the empty stack, used for symbols in and out of the stack.

2. The first character is the number 9, which outputs 9, followed by the symbol “+”, which is pushed.

3. The third character is “(“, which is still a symbol, because it is only an open parenthesis and is not paired yet, so it is pushed.

4. The fourth character is the number 3, the output, the total expression is 9, 3, followed by the “-” push.

5. Next is the number 1, the output, the total expression is 9, 3, 1, followed by the symbol “) “, at this point, we need to match the previous “(“, so the top of the stack, and output, until” (” out of the stack. There is only “-” above the left parenthesis, so “-” is printed. The total output expression is 9, 3, 1 –

6. And then the number 3, the output, the total expression is 9, 3, 1, minus 3. This is followed by the symbol “”, because at this time the top of the stack symbol is” + “, the priority is lower than “”, so no output, push.

7. This is followed by the symbol “+”, in which the top element of the stack has a higher priority than the “+”, so the elements in the stack are removed from the stack and printed (there is no lower priority than the “+” sign, so they are all removed from the stack), and the total output expression is 9, 3, 1-3 * +. The current symbol “+” is then pushed onto the stack. That is, the “+” at the bottom of the stack in the first six graphs refers to the “+” after the initial 9 in the infix expression, while the “+” at the bottom (and top) of the stack in the figure below refers to the last “+” in the “9+(3-1)*3+”.

8. Following the number 10, the output, the total expression becomes 9, 3, 1, minus 3 times plus 10.

9. The last number, 2, is output, and the total expression is 9, 3, 1, minus 3 times plus 10, 2
10. Since we are at the end, all symbols on the stack are removed from the stack and printed. The final output suffix expression is 9 3 1-3*+ 10 2/+

Program implementation

public class Suffix {

	public static void main(String[] args) {
		computer("9 + (3, 1) * 3 + 10/2"); } public static void computer(String input) { List<String> cutList = cutInput(input); List<String> afterList = getAfterList(cutList); System.out.println(afterList); Private static int CAL (int a, int b, char flag) {int result = 0; private static int CAL (int a, int b, char flag) {int result = 0; switch (flag) {case '+': {
			result = a + b;
			break;
		}
		case The '-': {
			result = a - b;
			break;
		}
		case The '*': {
			result = a * b;
			break;
		}
		case '/': {
			result = a / b;
			break;
		}
		default: {
			break; }}returnresult; Private static List<String> getAfterList(List<String> cutList) {List<String> output = new ArrayList<>(); Stack<Character> stack = new Stack<>();for (String ele : cutList) {
			char flag = ele.charAt(0);
			if (isFlag(ele.charAt(0)) || (flag == '(') || (flag == ') ')) {// the operator is pushedif (stack.isEmpty()) {
					stack.push(flag);
				} else{// If the unpushed operator is larger than the top of the stack, it is pushed directly; Otherwise, the stack is pushed until the stack is empty or the unpushed operator is smaller than the top of the stackif (flag == '(') {
						stack.push(flag);
					} else if (flag == ') ') {
						while(stack.peek() ! ='(') {
							output.add(String.valueOf(stack.pop()));
						}
						stack.pop();
					} else if (isFlagSmaller(stack.peek(), flag)) {
						stack.push(flag);
					} else if (stack.peek() == '(') {
						stack.push(flag);
					} else {
						do {
							if (stack.peek() == '(') {
								break;
							}
							output.add(String.valueOf(stack.pop()));
						} while (!stack.isEmpty() && !isFlagSmaller(stack.peek(), flag));
						stack.push(flag);
					}
				}
			} else{// Add the number directly to the output output.add(ele); }}while(! stack.isEmpty()) {if((stack.peek() ! ='(') || (stack.peek() ! =') ')) { output.add(String.valueOf(stack.pop())); }}returnoutput; } /** * private static List<String> cutInput(String input) {List<String> cutList = new ArrayList<>();  boolean running =true;

		while ((input.length() > 0) && running) {
			char c = input.charAt(0);
			if (isFlag(c) || (c == '(') || (c == ') ')) {
				cutList.add(String.valueOf(c));
				input = input.substring(1);
			} else {
				for (int i = 0; i < input.length(); i++) {
					char tmpC = input.charAt(i);
					if (isFlag(tmpC) || (tmpC == '(') || (tmpC == ') ')) {
						cutList.add(input.substring(0, i));
						cutList.add(String.valueOf(tmpC));

						input = input.substring(i + 1);
						break;
					}

					if (i == input.length() - 1) {
						cutList.add(input);
						running = false; }}}}returncutList; Private static Boolean isFlag(char c) {private static Boolean isFlag(char c) {return (c == '+' || c == The '-' || c == The '*' || c == '/'); } private static Boolean isFlagSmaller(char a, char b) {Boolean flag =true;

		switch (a) {
		case '+':
		case The '-': {
			if ((b == '+') || (b == The '-')) {
				flag = false;
			}
			break;
		}

		case The '*':
		case '/': {
			flag = false;
		}
		case '(': {
			flag = false;
		}
		default: {
			break; }}returnflag; }}Copy the code