Expression, conversion, and calculation, describe -Part2 with C language (all you should know about expressions)
Now we enter the topic of programming. How to convert expressions from one form into another form? There are two ways to complete this conversion. The first is that the stack is completed and the other is to use an expression tree.
Because there are three representations, there can be six conversions, that is, there is a prefix-> prefix, prefix-> suffix, prefix->fix, prefix-> suffix, suffix -> prefix, suffix -> These conversions. For the first two translations We prepare the stack to complete, the remaining four types of binary expression trees are completed.
In order to convert the expression from the prefix to the prefix, we will use the stack. For readers who don't know what stack, let's take a brief introduction to the stack. Stack is a special data structure, and the order in the stack is removed from the order in which they enter the stack. The stack follows the preceding (LIFO) mode. The addition of elements in the stack is called a stack (PUSH), and the element is removed from the stack is referred to as a stack (POP).
Use stack to convert expressions into a suffix form
In order to convert expressions into a suffix form from a prefix, we will use the stack.
Algorithm 1) Check the next element of the input. 2) If it is an operand, output. 3) If it is a blockbus, it is stack it. 4) If it is an operator, i) If the stack is empty, the operator is plagued. II) If the top of the stack is open, this operator is pressed. III) If this operator is highly prioritized than the top operator priority, this operator is pressed into the stack. IV) Otherwise, the top operator is in the stack and outputs, repeats step 4.5), if it is a closed bracing, the operator is out of the stack out of the stack and output until the parentheses are encountered. Stack out of the stack and discard it. 6) If the input has not yet been completed, the jump to step 1.7) If the input is completed, all the remaining operations in the stack strips and output them.
Example
Suppose we want to convert expressions 2 * 3 / (2-1) 5 * (4-1) into a suffix: the reverse order of the original expression is 1-4 (* 5 ) 1-2 (/ 3 *2.
Current scan character
Stack characters in the stack (the top of the stack)
Suffix expression
2
EMPTY
2
*
*
2
3
*
twenty three
/
/
twenty three*
(
/ (
twenty three*
2
/ (
23 * 2
-
/ (-
23 * 2
1
/ (-
23 * 21
)
/
23 * 21-
23 * 21- /
5
23 * 21- / 5
*
*
23 * 21- / 5
(
* (
23 * 21- / 5
4
* (
23 * 21- / 54
-
* (-
23 * 21- / 54
1
* (-
23 * 21- / 541
)
*
23 * 21- / 541-
EMPTY
23 * 21- / 541 - *
Therefore, the resulting suffix expression is 23 * 21- / 541 - * .
Use the stack to convert expressions into prefix forms
The above algorithm has certain skills, we first write an inverse order of the input expression, so A B * c becomes C * B A, and then conversion. This is a benefit that only requires some small modifications to the algorithm, which can be applied to the transformation of the prefix form. Algorithm 1) See the inversion of the input string. 2) Check the next element of the input. 3) If it is an operand, it is added to the output string. 4) If it is closed, it is stack it. 5) If it is an operator, then i), if the stack is empty, this operator is in the stack. Ii) If the top of the stack is closed, this operator is in the stack. III) If its priority is higher than or equal to the top operator, this operator is in the stack. Iv) Otherwise, the top operator is operator out of the stack and added to the output string, repeat step 5.6), and the operator in the stack out of the stack out of the stack and output until it is closed. Close the number out of the stack and discard it. 7) If the input has not yet been completed, the jump to step 2.8) If the input is completed, all the remaining operations remaining in the stack and add it to the output string. 9) Inverse order of the output string. Example
Suppose we want to convert expressions 2 * 3 / (2-1) 5 * (4-1) to prefix form: the reverse order of the original expression is 1-4 (* 5 ) 1-2 (/ 3 * 2
Current scan character
Stack characters in the stack (the top of the stack)
Prefix expression (from right to left)
)
)
1
)
1
-
)
1
4
)
14
(
EMPTY
14-
*
*
14-
5
*
14-5
14-5 *
)
)
14-5 *
1
)
14-5 * 1
-
) -
14-5 * 1
2
) -
14-5 * 12
(
14-5 * 12-
/
/
14-5 * 12-
3
/
14-5 * 12-3
*
/ *
14-5 * 12-3
2
/ *
14-5 * 12-32
EMPTY
14-5 * 12-32 * /
The reverse order of the output string is / * 23-21 * 5-41, so the final resulting prefix expression is / * 23-21 * 5-41. The above algorithm reference program # 1.
