2.9. Infix, Prefix and Postfix Expressions — Resolução de Problemas Usando Python (2024)

2.9.1. Conversion of Infix Expressions to Prefix and Postfix¶

So far, we have used ad hoc methods to convert between infix expressionsand the equivalent prefix and postfix expression notations. As you mightexpect, there are algorithmic ways to perform the conversion that allowany expression of any complexity to be correctly transformed.

The first technique that we will consider uses the notion of a fullyparenthesized expression that was discussed earlier. Recall that A + B* C can be written as (A + (B * C)) to show explicitly that themultiplication has precedence over the addition. On closer observation,however, you can see that each parenthesis pair also denotes thebeginning and the end of an operand pair with the corresponding operatorin the middle.

Look at the right parenthesis in the subexpression (B * C) above. If wewere to move the multiplication symbol to that position and remove thematching left parenthesis, giving us B C *, we would in effect haveconverted the subexpression to postfix notation. If the additionoperator were also moved to its corresponding right parenthesis positionand the matching left parenthesis were removed, the complete postfixexpression would result (see Figure 6).

If we do the same thing but instead of moving the symbol to the positionof the right parenthesis, we move it to the left, we get prefix notation(see Figure 7). The position of the parenthesis pair isactually a clue to the final position of the enclosed operator.

So in order to convert an expression, no matter how complex, to eitherprefix or postfix notation, fully parenthesize the expression using theorder of operations. Then move the enclosed operator to the position ofeither the left or the right parenthesis depending on whether you wantprefix or postfix notation.

Here is a more complex expression: (A + B) * C - (D - E) * (F + G).Figure 8 shows the conversion to postfix and prefixnotations.

2.9.2. General Infix-to-Postfix Conversion¶

We need to develop an algorithm to convert any infix expression to apostfix expression. To do this we will look closer at the conversionprocess.

Consider once again the expression A + B * C. As shown above,A B C * + is the postfix equivalent. We have already noted that theoperands A, B, and C stay in their relative positions. It is only theoperators that change position. Let’s look again at the operators in theinfix expression. The first operator that appears from left to right is+. However, in the postfix expression, + is at the end since the nextoperator, *, has precedence over addition. The order of the operatorsin the original expression is reversed in the resulting postfixexpression.

As we process the expression, the operators have to be saved somewheresince their corresponding right operands are not seen yet. Also, theorder of these saved operators may need to be reversed due to theirprecedence. This is the case with the addition and the multiplication inthis example. Since the addition operator comes before themultiplication operator and has lower precedence, it needs to appearafter the multiplication operator is used. Because of this reversal oforder, it makes sense to consider using a stack to keep the operatorsuntil they are needed.

What about (A + B) * C? Recall that A B + C * is the postfixequivalent. Again, processing this infix expression from left to right,we see + first. In this case, when we see *, + has already been placedin the result expression because it has precedence over * by virtue ofthe parentheses. We can now start to see how the conversion algorithmwill work. When we see a left parenthesis, we will save it to denotethat another operator of high precedence will be coming. That operatorwill need to wait until the corresponding right parenthesis appears todenote its position (recall the fully parenthesized technique). Whenthat right parenthesis does appear, the operator can be popped from thestack.

As we scan the infix expression from left to right, we will use a stackto keep the operators. This will provide the reversal that we noted inthe first example. The top of the stack will always be the most recentlysaved operator. Whenever we read a new operator, we will need toconsider how that operator compares in precedence with the operators, ifany, already on the stack.

Assume the infix expression is a string of tokens delimited by spaces.The operator tokens are *, /, +, and -, along with the left and rightparentheses, ( and ). The operand tokens are the single-characteridentifiers A, B, C, and so on. The following steps will produce astring of tokens in postfix order.

1. Create an empty stack called opstack for keeping operators.Create an empty list for output.

2. Convert the input infix string to a list by using the string methodsplit.

3. Scan the token list from left to right.

   • If the token is an operand, append it to the end of the outputlist.

   • If the token is a left parenthesis, push it on the opstack.

   • If the token is a right parenthesis, pop the opstack until thecorresponding left parenthesis is removed. Append each operator tothe end of the output list.

   • If the token is an operator, *, /, +, or -, push it on theopstack. However, first remove any operators already on theopstack that have higher or equal precedence and append themto the output list.

4. When the input expression has been completely processed, check theopstack. Any operators still on the stack can be removed andappended to the end of the output list.

Figure 9 shows the conversion algorithm working on theexpression A * B + C * D. Note that the first * operator is removedupon seeing the + operator. Also, + stays on the stack when the second* occurs, since multiplication has precedence over addition. At the endof the infix expression the stack is popped twice, removing bothoperators and placing + as the last operator in the postfix expression.

In order to code the algorithm in Python, we will use a dictionarycalled prec to hold the precedence values for the operators. Thisdictionary will map each operator to an integer that can be comparedagainst the precedence levels of other operators (we have arbitrarilyused the integers 3, 2, and 1). The left parenthesis will receive thelowest value possible. This way any operator that is compared against itwill have higher precedence and will be placed on top of it.Line 15 defines the operands to be any upper-case character or digit.The complete conversion function isshown in ActiveCode 1.

A few more examples of execution in the Python shell are shown below.

>>> infixtopostfix("( A + B ) * ( C + D )")'A B + C D + *'>>> infixtopostfix("( A + B ) * C")'A B + C *'>>> infixtopostfix("A + B * C")'A B C * +'>>>

2.9.3. Postfix Evaluation¶

As a final stack example, we will consider the evaluation of anexpression that is already in postfix notation. In this case, a stack isagain the data structure of choice. However, as you scan the postfixexpression, it is the operands that must wait, not the operators as inthe conversion algorithm above. Another way to think about the solutionis that whenever an operator is seen on the input, the two most recentoperands will be used in the evaluation.

To see this in more detail, consider the postfix expression4 5 6 * +. As you scan the expression from left to right, you firstencounter the operands 4 and 5. At this point, you are still unsure whatto do with them until you see the next symbol. Placing each on the stackensures that they are available if an operator comes next.

In this case, the next symbol is another operand. So, as before, push itand check the next symbol. Now we see an operator, *. This means thatthe two most recent operands need to be used in a multiplicationoperation. By popping the stack twice, we can get the proper operandsand then perform the multiplication (in this case getting the result30).

We can now handle this result by placing it back on the stack so that itcan be used as an operand for the later operators in the expression.When the final operator is processed, there will be only one value lefton the stack. Pop and return it as the result of the expression.Figure 10 shows the stack contents as this entire exampleexpression is being processed.

Figure 11 shows a slightly more complex example, 7 8 + 3 2+ /. There are two things to note in this example. First, the stack sizegrows, shrinks, and then grows again as the subexpressions areevaluated. Second, the division operation needs to be handled carefully.Recall that the operands in the postfix expression are in their originalorder since postfix changes only the placement of operators. When theoperands for the division are popped from the stack, they are reversed.Since division is not a commutative operator, in other words\(15/5\) is not the same as \(5/15\), we must be sure thatthe order of the operands is not switched.

Assume the postfix expression is a string of tokens delimited by spaces.The operators are *, /, +, and - and the operands are assumed to besingle-digit integer values. The output will be an integer result.

1. Create an empty stack called operandStack.

2. Convert the string to a list by using the string method split.

3. Scan the token list from left to right.

   • If the token is an operand, convert it from a string to an integerand push the value onto the operandStack.

   • If the token is an operator, *, /, +, or -, it will need twooperands. Pop the operandStack twice. The first pop is thesecond operand and the second pop is the first operand. Performthe arithmetic operation. Push the result back on theoperandStack.

4. When the input expression has been completely processed, the resultis on the stack. Pop the operandStack and return the value.

The complete function for the evaluation of postfix expressions is shownin ActiveCode 2. To assist with the arithmetic, a helperfunction doMath is defined that will take two operands and anoperator and then perform the proper arithmetic operation.

It is important to note that in both the postfix conversion and thepostfix evaluation programs we assumed that there were no errors in theinput expression. Using these programs as a starting point, you caneasily see how error detection and reporting can be included. We leavethis as an exercise at the end of the chapter.

.. fillintheblank:: postfix1 .. blank:: pfblank1 :correct: \\b10\\s+3\\s+5\\s*\\*\\s*16\\s+4\\s*-\\s*/\\s*\\+ :feedback1: ('10.*3.*5.*16.*4', 'The numbers appear to be in the correct order check your operators') :feedback2: ('.*', 'Remember the numbers will be in the same order as the original equation') Without using the activecode infixToPostfix function, convert the following expression to postfix ``10 + 3 * 5 / (16 - 4)``

.. fillintheblank:: postfix2 .. blank:: pfblank2 :correct: \\b9\\b :feedback1: ('.*', "Remember to push each intermediate result back on the stack" ) What is the result of evaluating the following: ``17 10 + 3 * 9 / ==``

.. fillintheblank:: postfix3 .. blank:: pfblank3 :correct: 5\\s+3\\s+4\\s+2\\s*-\\s*\\^\\s*\\* :feedback1: ('.*', 'Hint: You only need to add one line to the function!!') Modify the infixToPostfix function so that it can convert the following expression: ``5 * 3 ^ (4 - 2)`` Paste the answer here: