Conversion of Infix Expressions to Prefix and Postfix
One technique that we will consider now uses the notion of a
fully parenthesized expression.
We simply add parentheses around each operation to show the exact order of
all operations.
So, A + B * C can be written as (A + (B * C)) to show
explicitly that the multiplication has precedence over the addition. On
closer observation, however, you can see that each parenthesis pair also
denotes the beginning and the end of an operand pair with the corresponding
operator in the middle.
Look at the right parenthesis in the subexpression (B * C)
above. If we were to move the multiplication symbol to that position and
remove the matching left parenthesis, giving us B C *, we would in effect
have converted the subexpression to postfix notation. If the addition
operator were also moved to its corresponding right parenthesis position
and the matching left parenthesis were removed, the complete postfix
expression would result (see below).
If we do the same thing but instead of moving the symbol to
the position of the right parenthesis, we move it to the left, we get
prefix notation (see below). The
position of the parenthesis pair is actually a clue to the final position
of the enclosed operator.
So in order to convert an expression, no matter how complex,
to either prefix or postfix notation, fully parenthesize the expression
using the order of operations. Then move the enclosed operator to the
position of either the left or the right parenthesis depending on whether
you want prefix or postfix notation.
Here is a more complex expression: (A + B) * C - (D - E) *
(F + G).
The figure below shows the conversion to postfix and
prefix notations.
Source:
http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html
|
