Expression, conversion and calculation,
C
Language Description - Part1
(All what you should know about expressions)
In this article, I will explain in detail an important programming concept, which is an expression, and its different representations such as prefix, suffix, prefix, how to convert a representation to another, And how to calculate the value of the algebraic expression.
Each principle is accompanied by an algorithm and an exemplary program written in C language to help novices understand these concepts more clearly.
We will use stacks and binary trees to convert expressions and calculate the value of the expression, so the reader is required to know these basic concepts before reading this article.
The subject coverage of this article is:
What is algebraic expression?
What is expression of expression, prefix, suffix representation?
Why do we need a different expression method for the same expression?
Why do we have to convert expressions from one form to another?
How do we convert expressions from a representation into another representation? (Algorithm, Program, Example)
Expression tree
How to calculate a value of an expression? (Algorithm, program)
Algebraic expression profile:
Algebraic expressions are legal strings that are connected by operands and operators. The operand is a quantity (unit of data), and mathematical operation runs on the basis of the operand. The operand can be a variable, such as X, Y, Z, or a constant, such as 5, 4, 0, 9, 1, etc. The operator is a symbol indicating the mathematical or logical operation of an operator. Everyone is familiar with the operators with , -,, *, /, ^ (used in this tutorial), etc. Depending on the definition of operands and operators, we can now write an example of an expression, such as x y * z. Note that the term "legal string" in the algebraic expression definition, in the example X Y * z mentioned earlier, operands x, y, x, and operators , * form a form of legitimate string . Another example XYZ *, this expression does not form a legitimate string in this expression; this expression is not a valid expression.
One algebraic expression has three representations:
Fox said: From our school era, we have been familiar with the representation of this operand, such as X Y, 6 * 3, etc. This method of writing expressions is called a prefix representation.
The prefix indicates that the prefix representation is also known as the Polish representation, which is a logical notation invented by the Poland mathematician Jan Lukasiewicz. As the name suggests, in the prefix representation, the operator is to put it in front of the operand, such as XY, * XYZ, etc.
The suffix indicates that the suffix representation is also referred to as the reverse polish representation. It differs from the prefix and prefix expression that in the suffix representation, the operator is placed after the number of operators, such as XY , XYZ *, etc.
Now, we will naturally think of a problem, we have already made a cute and simple prefix representation, why should these weird prefixes and suffix representations?
In fact, we are surprised that the infix is not as simple as it looks like it, especially when calculating the value of the infix expression. In order to calculate the value of a prefix expression we need to consider the priority and combination of the operator.
For example, the expression 3 5 * 4 is considered (3 5) * 4 calculation results 32, and it is considered 3 (5 * 4) to calculate 23. In order to solve this problem, you need to define the priority between operators. The operator priority specifies the order of calculation. The high priority operator is calculated first, and the priority low operator is calculated. The following table lists the priority of each operator in a decrement order.
Now, we already know the priority of each operator, we can determine that the value of the expression 3 5 * 4 is 23. But please wait, the problem is not completely solved, what should I do if I do 6/3 * 2? When this expression is regarded as (6/3) * 2, it is seen as 6 / (3 * 2), because the * and / priority are the same. To solve this conflict, we have to use the combination of operators. The combination of operators specifies the order between operators with priority. For an operator with left binding, the calculation order is from left to right, and the calculation of the right binding is calculated from right to left.
*, /, , - all have left bonding. Therefore, the above expression is finally calculated, not 1.
Note: We use the concept of combination just to solve conflicts between the same priority operators.
Since the use of a prefix representation, the priority and combination of the operator is considered, we convert to the prefix and suffix. The prefix and suffix indicate that the advantage of the infix indication is that there is no need to consider the priority and combination of the operator when calculating the expression value. For example, x / y * z is expressed in a prefix to become * / xyz, and use a suffix to become XY / Z *. The prefix and suffix indicate that the calculation of the expression value is much easier. (About this, we will discuss in detail later)
But these two expressions are not convenient for memory or not to write. For example, (x y) / z * a (prefix expression) and XY z / a * (suffix representation), which one is easier to remember?
So, in fact, we have to do is scanned by the user; convert it into a prefix or suffix form, then calculate its value without considering the priority of parentheses and operators.
