There is a question in the written test. When I wrote an expression with a suffix representation, I was confused at the time. I have never heard of what a suffix expression is. Later I checked and found that it was a relatively special mathematical expression because I don’t use it much in daily life and don’t know much about it. There are three expressions: prefix expression, infix expression and suffix expression. Generally, infix is used, such as 1+1. The pre-suffix is to move the operator to the front and back. I will introduce these three expressions below.
1. Prefix notation
The prefix notation is also called Polish notation. Its operator is placed before the operand (example: + 1 2), and was introduced by Polish mathematician Jan Vukasevich in the 1920s to simplify propositional logic. Because we generally believe that operators are in the middle of operands, they are not used much in daily life, but they have a place in the field of computer science. General notation is very troublesome for computers to process. Each symbol must be considered for priority. There are also brackets that will disrupt priority, which will cause the computer to spend a lot of resources for parsing. The prefix notation has no concept of priority, and it is processed in order.
For example: The formula 9-2*3, the computer needs to analyze the priority first, multiply and subtract, find 2*3, and then perform the subtraction operation; the prefix representation is: - 9 * 2 3. The computer can read it in sequence, and the operator acts on the next operand. When subtracting, it means that 9 subtracts the subsequent number, and then 9 is multiplied, that is, let 9 subtract the result of multiplication. This is very simple for the computer, just do it in order.
Let's look at the prefix expression of a complex point:
- * / 15 - 7 + 1 1 3 + 2 + 1 1
- * / 15 - 7 2 3 + 2 + 1 1
- * / 15 5 3 + 2 + 1 1
- * 3 3 + 2 + 1 1
- 9 + 2 + 1 1
- 9 + 2 2
- 9 4
5
This is a prefix expression calculation process. It can be seen that each time you only need to calculate the first equation that satisfies the operator followed by two operands, until the end is the result.
2. Infix notation
This is our general notation. Its operator is placed in the middle of the operand (example: 1 + 2). As mentioned earlier, this method is not easy to be parsed by computers, but it conforms to people's common usage, and many programming languages use this method. In the infix notation, brackets are required, otherwise the operation order will be messed up. Because it is very commonly used, I won't talk much about it.
3. Suffix notation
The suffix notation is also called the inverse Polish notation. Its operator is placed after the operand (example: 1 2 +). Both it and the prefix notation are computer-friendly, but it is easy to parse with stacks, so it is used a lot in computers. His explanation process is generally: the operand is put into the stack; when an operator is encountered, the operand is put out of the stack, evaluated, and put the result into the stack; after one pass, the top of the stack is the value of the expression. Therefore, the evaluation of inverse Polish expressions is easy to implement using a stack structure, and can be evaluated quickly.
Note: Inverse Polish notation is not a simple inversion of Polish expressions. Because for the operator of commutational law, its operand writing is still in the conventional order. For example, the inverse Polish notation of "/6 3" is "6 3 /" instead of "3 6 /"; the digit writing of numbers is also in the conventional order.
In order to better understand the calculation process of prefix expressions, give an example: 5 1 2 + 4 * + 3 - The calculation process is as follows
Stack space //Explanation
5
5 1
5 1 2
5 3 //End +, 1 and 2 out of the stack, get 3, enter the stack
5 3 4
5 12 //When encounter *, 3 and 4 come out of the stack, get 12, enter the stack
17 //I encounter +, 5 and 12 to get 17 and enter the stack
17 3
14 //I encounter -, 17 and 3 come out of the stack, get 14, enter the stack
Finally, there is only one operand in the stack, and this is the calculation result. From this we can see that it is easy to parse suffix expressions using stack.
4. Transformation between notation
Here we introduce a simple method of converting pre-suffix expressions to the infix expression, such as this formula: a+b*c-(d+e).
1. Add brackets to all operation units according to the priority of the operator
The formula becomes: ((a+(b*c))-(d+e)).
2.1. Prefix expression, move the operator symbol to the corresponding brackets
The formula becomes: -( +(a *(bc)) +(de))
Remove brackets: -+a*bc+de
2.2. Suffix expression, move the operator symbol to the corresponding brackets
The formula becomes: ((a(bc)* )+ (de)+ )-
Remove brackets:abc*+de-