Shulou(Shulou.com)06/02 Report--

Editor to share with you the Java data structure and algorithm prefix, infix and suffix expression example analysis, I hope you will learn something after reading this article, let's discuss it together!

1. How to parse arithmetic expressions

How do I parse arithmetic expressions? Or, to put it another way, how do we evaluate an arithmetic expression:

①, evaluation 3-4-5

In this expression, we cannot directly calculate the value of 3x4 after seeing 3x4. We know that we can see the-sign after 4.Because the priority of the minus sign is the same as the previous plus sign, we can calculate the value of 3q4.If 4 is followed by * or /, then we can add only after multiplication and division, for example:

②, evaluation 3 / 4 / 5

You can't get the value of 3 to 4 first, because the level of * after 4 is higher than the previous +. Through the description of these two expressions, we can summarize several rules to follow when parsing expressions:

①, read the formula from left to right.

②, when you have read two operands and an operator that can calculate values, you can calculate and replace those operands and an operator with the result.

③, continue this process, from left to right, even if you can, until the end of the expression.

2. How does the computer parse the arithmetic expression

For the previous expression 3-4-5, we are capable of thinking and can calculate the result of the expression according to the position of the operator and the priority of the operator. But what about the computer?

The computer must read operands and operators forward (from left to right), and when it reads enough information to perform an operation, it finds two operands and an operator to perform the operation. sometimes if it is followed by a higher-level operator or parenthesis, you have to postpone the operation, parse to the later high-level operation, and then go back to the previous operation. We find that this process is extremely tedious, and the computer is a machine, which only knows high and low levels. If we want to complete the calculation of a simple expression, we may have to design a very complex logic circuit to control the calculation process, not to mention very complex arithmetic expressions, so it is unreasonable to parse arithmetic expressions in this way, so what method should we take?

Please first take a look at what is a prefix expression, an infix expression, and a suffix expression: these three expressions are actually three ways of writing arithmetic expressions, taking 3-4-5 as an example.

①, prefix expression: operators precede operands, such as +-543

②, infix expression: the operator is in the middle of the Operand, which is the easiest arithmetic expression for human beings to recognize.

③, suffix expression: the operator comes after the Operand, such as 3455-

The person we talked about above is how to parse the arithmetic expression, that is, to parse the infix expression, which is the easiest for people to recognize, but it is not easy for the computer to recognize the prefix expression and suffix expression. After converting the infix expression into a prefix expression or suffix expression, the computer can quickly calculate the value of the expression. So how do infix expressions translate into prefix expressions and suffix expressions, and how do computers parse prefix expressions and suffix expressions to get results?

3. Suffix expression

A suffix expression, which does not contain parentheses, the operator is placed after the two operands, and all calculations are performed strictly from left to right in the order in which the operator appears (regardless of the operator's precedence rules).

Because the operator of the suffix expression is after the two operands, the computer only needs to scan from left to right when parsing the suffix expression, that is, it only needs to scan forward instead of looking back. when you encounter an operator, put the operator in the middle of the first two operators (let's not consider the monomial operation similar to the multiplier here), all the way to the rightmost operator, then we get the result. Since suffix expressions are so good, here comes the problem:

①, how to convert an infix expression to a suffix expression?

For this problem, the rules for the transformation are as follows:

First, customize a stack package com.ys.poland;public class MyCharStack {private char [] array; private int maxSize; private int top; public MyCharStack (int size) {this.maxSize = size; array = new char [size]; top =-1;} / / press data public void push (char value) {if (top)

< maxSize-1){ array[++top] = value; } } //弹出栈顶数据 public char pop(){ return array[top--]; } //访问栈顶数据 public char peek(){ return array[top]; } //查看指定位置的元素 public char peekN(int n){ return array[n]; } //为了便于后面分解展示栈中的内容，我们增加了一个遍历栈的方法(实际上栈只能访问栈顶元素的) public void displayStack(){ System.out.print("Stack(bottom-->

Top): "); for (int I = 0; I < top+1; iTunes +) {System.out.print (peekN (I)); System.out.print ('');} System.out.println (");} / / determine whether the stack is empty public boolean isEmpty () {return (top = =-1) } / / determine whether the stack is full of public boolean isFull () {return (top = = maxSize-1);}} II. Convert the prefix expression to the suffix expression package com.ys.poland;public class InfixToSuffix {private MyCharStack S1 / define the operator stack private MyCharStack S2 / define the storage result stack private String input / / default construction method. The parameter is the infix expression public InfixToSuffix (String in) {input = in; S1 = new MyCharStack (input.length ()); S2 = new MyCharStack (input.length ());} / / the infix expression is converted to a suffix expression, the result is stored on the stack and returned, and the suffix expression public MyCharStack doTrans () {for (int j = 0) is displayed in reverse order. J < input.length (); jacks +) {System.out.print ("S1 stack elements are:"); s1.displayStack (); System.out.print ("S2 stack elements are:"); s2.displayStack (); char ch = input.charAt (j); System.out.println ("characters currently parsed:" + ch) Switch (ch) {case'+': case'-': gotOper (ch,1); break; case'*': case'/': gotOper (ch,2); break; case'(': s1.push (ch)) / / if the current character is'(', put it on the stack break; case')': gotParen (ch); break; default: / / 1. If the current parsed character is an Operand, press it directly into S2 / / 2, s2.push (ch) Break;} / / end switch} / / end for while (! s1.isEmpty ()) {s2.push (s1.pop ());} return S2;} public void gotOper (char opThis,int prec1) {while (! s1.isEmpty ()) {char opTop = s1.pop () If (opTop ='(') {/ / if the top of the stack is'(', press the operator directly into S1 s1.push (opTop); break;} else {int prec2; if (opTop = ='+'| | opTop = ='-') {prec2 = 1 } else {prec2 = 2;} if (prec2 < prec1) {/ / if the current operator has higher priority than the S1 stack top operator, press the operator into S1 s1.push (opTop); break } else {/ / if the current operator is the same as or less than the priority operator at the top of the stack, eject and press the operator at the top of S1 into S2 / and go to the while loop again to compare with the new top operator in S1 S2.push (opTop);} / / end while / / if S1 is empty, press the currently parsed operator directly into S1 s1.push (opThis) If the current character is')', discard the pair of parentheses if the top of the stack is'(', otherwise pop up the characters at the top of stack S1 and press them into S2 until you encounter'('public void gotParen (char ch) {while (! s1.isEmpty ()) {char chx = s1.pop (); if (chx = =' (') {break) } else {s2.push (chx);} III. Test @ Testpublic void testInfixToSuffix () {String input; System.out.println ("Enter infix:"); Scanner scanner = new Scanner (System.in); input = scanner.nextLine (); InfixToSuffix in = new InfixToSuffix (input); MyCharStack my = in.doTrans (); my.displayStack ();} IV. Result

V. Analysis

②, how does the computer realize the operation of suffix expression?

4. Prefix expression

A prefix expression, which does not contain parentheses, the operator is placed in front of the two operands, strictly from right to left (no longer considering the precedence rules of the operator), and all calculations are in the order in which the operator appears.

Note: suffix expressions are parsed from left to right, while prefix expressions are parsed from right to left.

①, how to convert an infix expression to a prefix expression?

②, how does the computer realize the operation of prefix expression?

After reading this article, I believe you have some understanding of "sample Analysis of prefixes, suffixes and suffixes expressions in Java data structures and algorithms". If you want to know more about it, please follow the industry information channel. Thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.