c mathematical notation of postfix notation

In the written test there is such a question, write a postfix expression expression form, at that time confused, what is the postfix expression, still really have not heard. Later, I looked up a special mathematical expression, because I didn't know much about it in daily life. There are three kinds of expressions: prefix expressions, infix expressions, and postfix expressions. In general, 1 USES an infix, such as 1+1. The prefix and suffix move the operator to the front and the back. I will introduce these three expressions.

1. Prefix notation

The prefix notation, also known as the polish notation, whose operators precede operands (e.g., + 1, 2), was introduced in the 1920s by the polish mathematician jan vucasevich to simplify propositional logic. Because we tend to think of operators as being in the middle of operands, we don't use them much in everyday life, but they have a place in computer science. The 1-like notation is cumbersome for a computer to process, where each symbol has to be prioritized, and the existence of parentheses, which can mess up the priority, can cost the computer a lot of resources to parse. The prefix notation has no concept of precedence, it is processed in order.
For example, in the formula of 9 minus 2 by 3, the computer needs to analyze the priority first, multiply and then subtract, find 2 by 3, and then subtract; The operator ACTS on the last operand, and when you encounter a minus, you subtract the last operand from 9, and then you multiply by 9, that is to say, you subtract the product from 9, which is very easy for a computer, just do it in order.
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

So this is the calculation of one prefix expression, and you can see that you only need to evaluate the first expression that satisfies the operator followed by two operands at a time, until you get to the end result.

2. Infix notation

This is our 1-like notation, with its operator in the middle of the operand (e.g., 1 + 2). As mentioned earlier, this method is not easily parsed by computers, but it fits the general usage of people and is used in many programming languages. Parentheses are required in infix notation, otherwise the order of operations will be out of order. I'm not going to talk about it because it's so common.

3. Suffix notation

The postfix notation, also known as the reverse polish notation, has operators that follow operands (e.g., 1, 2, +). It and the prefix notation are both computer friendly, but it is easy to parse with the stack, so it is used a lot in computers. His explanation of process 1 is: operand push; When an operator is encountered, the operand is pushed out of the stack, evaluated, and the result pushed. After 1 pass, the top of the stack is the value of the expression. Therefore, the evaluation of the inverse polish expression is easy to implement using the stack structure, and can be evaluated quickly.
Note: the inverse polish notation is not a simple reversal of the polish expression. Because for operators that do not satisfy the commutative law, the operands are still written in the normal order, for example, the reverse polish notation of "/ 6 3" is "6 3 /" instead of "3 6 /"; Numbers are written in a regular order.
In order to better understand the calculation process of prefix expression, for example: 5, 1, 2 + 4 * + 3 -, the calculation process is as follows

 Stack space      // explain 
5
5 1
5 1 2
5 3       // encounter + . 1 and 2 Out of the stack, too 3 , into the stack 
5 3 4
5 12      // encounter * . 3 and 4 Out of the stack, too 12 , into the stack 
17        // encounter + . 5 and 12 Out of the stack, too 17 , into the stack 
17 3
14        // encounter - . 17 and 3 Out of the stack, too 14 , into the stack 

You end up with only one operand on the stack, and that's what you get. From this we can see that it is easy to parse postfix expressions with a stack.

4. Conversion between representations

Here is a simple way to convert an infix expression into a prefix expression, such as this: a+b*c-(d+e).
1. Bracket all units of operation according to their precedence
It becomes :(a+(b*c))-(d+e)).
2.1. Prefix expression, move the operation symbol before the corresponding parentheses
So this becomes -(+(a *(bc)) +(de)).
Remove the parentheses: -+a*bc+de
2.2. Postfix expression, move the operation symbol behind the corresponding parentheses
It becomes :(a(bc)*)+ (de)+)-
Remove the parentheses: abc*+de+-