The Push Button

To insert a data item on the stack, use the button labeled Push. The item can be any text string, and you simply type it in the text entry box next to Push. The tool limits the number of characters in the string, so they fit in the array cells.

To the left of the stack is a reddish-brown arrow labeled “__top.” This is part of the data structure, an attribute that tracks the last item inserted. Initially, nothing has been inserted, so it points below the first array cell, the one labeled with a small 0. When you push an item, it moves up to cell 0, and the item is inserted in that cell. Notice that the top arrow is incremented before the item is inserted. That’s important because copying the data before incrementing could either cause an error by writing outside of the array bounds or overwriting the last element in the array when there are multiple items.

Try pushing several items on the stack. The tool notes the last operation you chose when typing an argument, so if you press Return or Enter while typing the next one, it will run the push operation again. If the stack is full and you try to push another item, you’ll get the Error! Stack is already full message. (Theoretically, an ADT stack doesn’t become full, but any practical implementation does.)

The New Button

As with all data structures, you create (and remove) stacks as needed for an algorithm. Because this implementation is based on an array, it needs to know how big the array should be. The Stack Visualization tool starts off with eight cells allocated and none of them filled. To make a new, empty stack, type the number of cells it should have in the text entry box and then select New. The tool adjusts the height of the cells to fit them within the display window. If you ask for a size that won’t fit, you’ll get an error message.

The Pop Button

To remove a data item from the top of the stack, use the Pop button. The value popped is moved to the right as it is being copied to a variable named top. It is stored there temporarily as the pop() method finishes its work.

Again, notice the steps involved. First, the item is copied from the cell pointed to by __top. Then the cell is cleared, and then __top is decremented to point to the highest occupied cell. The order of copying and changing the index pointer is the reverse of the sequence used in the push operation.

The tool’s Pop operation shows the item actually being removed from the array and the cell becoming empty. This is not strictly necessary because the value could be left in the array and simply ignored. In programming languages like Python, however, references to items left in an array like this can consume memory. It’s important to remove those references so that the memory can be reclaimed and reused. We show this in detail when looking at the code. Note that you still have a reference to the item in the top variable so that it won’t be lost.

After the topmost item is removed, the __top index decrements to the next lower cell. After you pop the last item off the stack, it points to −1, below the lowest cell. This position indicates that the stack is empty. If the stack is empty and you try to pop an item, you’ll get the Error! Stack is empty message.

The Peek Button

Push and pop are the two primary stack operations. It’s sometimes useful, however, to be able to read the value from the top of the stack without removing it. The peek operation does this. By selecting the Peek button a few times, you see the value of the item at the __top index copied to the output box on the right, but the item is not removed from the stack, which remains unchanged.

Notice that you can peek only at the top item. By design, all the other items are invisible to the stack user. If the stack is empty in the visualization tool when you select Peek, the output box is not created. We show how to implement the empty test later in the code.

Stack Size

Stacks come in all sizes and are typically capped in size so that they can be allocated in a single block of memory. The application allocates some initial size based on the maximum number of items expected to be stacked. If the application tries to push items beyond what the stack can hold, then either the stack needs to increase in size, or an exception must occur. The visualization tool limits the size to what fits conveniently on the screen, but stacks in many applications can have thousands or millions of cells.

Error Handling

There are different philosophies about how to handle stack errors. What should happen if you try to push an item onto a stack that’s already full or pop an item from a stack that’s empty?

In this implementation, the responsibility for avoiding or handling such errors has been left up to the program using the class. That program should always check to be sure the stack is not full before inserting an item, as in

Click here to view code image

if not stack.isFull():
   stack.push(item)
else:
   print("Can't insert, stack is full")

The client program in Listing 4-2 checks for an empty stack before it calls pop(). It does not, however, check for a full stack before calling push(). Alternatively, many stack classes check for these conditions internally, in the push() and pop() methods. Typically, a stack class that discovers such conditions either throws an exception, which can then be caught and processed by the program using the class, or takes some predefined action, such as returning None. By providing both the ability for users to query the internal state and the possibility of raising exceptions when constraints are violated, the data structure enables both proactive and reactive approaches.

Opening Delimiters on the Stack

This delimiter-matching program works by reading characters from the string one at a time and placing opening delimiters, when it finds them, on a stack. When it reads a closing delimiter from the input, it pops the opening delimiter from the top of the stack and attempts to match it with the closing delimiter. If they’re not the same type (there’s an opening brace but a closing parenthesis, for example), an error occurs. Also, if there is no opening delimiter on the stack to match a closing one, or if a delimiter has not been matched, an error occurs. It discovers unmatched delimiters because they remain on the stack after all the characters in the string have been read.

Let’s see what happens on the stack for a typical correct string:

a{b(c[d]e)f}

Table 4-1 shows how the stack looks as each character is read from this string. The entries in the second column show the stack contents, reading from the bottom of the stack on the left to the top on the right.

As the string is read, each opening delimiter is placed on the stack. Each closing delimiter read from the input is matched with the opening delimiter popped from the top of the stack. If they form a pair, all is well. Nondelimiter characters are not inserted on the stack; they’re ignored.

This approach works because pairs of delimiters that are opened last should be closed first. This matches the last-in, first-out property of the stack.

Python Code for DelimiterChecker.py

Listing 4-4 shows the code for the parsing program, DelimiterChecker.py. Like ReverseWord.py, the program accepts an expression after prompting the user using input() and prints out any errors found or a message saying the delimiters are balanced.

LISTING 4-4 The DelimiterChecker.py Program

Click here to view code image

# A program to check that delimiters are balanced in an expression

from SimpleStack import *
 
stack = Stack(100)          # Create a stack to hold delimiter tokens
 
expr = input("Expression to check: ")
 
errors = 0                  # Assume no errors in expression
 
for pos, letter in enumerate(expr): # Loop over letters in expression
   if letter in "{[(":      # Look for starting delimiter
      if stack.isFull():    # A full stack means we can't continue
         raise Exception('Stack overflow on expression')
      else:
         stack.push(letter) # Put left delimiter on stack
 
   elif letter in "}])":    # Look for closing delimiter
      if stack.isEmpty():   # If stack is empty, no left delimiter
         print("Error:", letter, "at position", pos,
               "has no matching left delimiter")
         errors += 1
      else:
         left = stack.pop() # Get left delimiter from stack
         if not (left == "{" and letter == "}" or  # Do delimiters
                 left == "[" and letter == "]" or  # match?
                 left == "(" and letter == ")"):
            print("Error:", letter, "at position", pos,
                  "does not match left delimiter", left)
            errors += 1
 
# After going through entire expression, check if stack empty
if stack.isEmpty() and errors == 0:
   print("Delimiters balance in expression", expr)
 
elif not stack.isEmpty():   # Any delimiters on stack weren't matched
   print("Expression missing right delimiters for", stack)

The program doesn’t define any functions; it processes one expression from the user and exits. It creates a Stack object to hold the delimiters as they are found. The errors variable is used to track the number of errors found in parsing the expression. It loops over the characters in the expression using Python’s enumerate() sequencer, which gets both the index and the value of the string at that index. As it finds starting (or left) delimiters, it pushes them on the stack, avoiding overflowing the stack. When it finds ending (or closing or right) delimiters, it checks whether there is a matching delimiter on the top of the stack. If not, it prints the error and continues. Some sample outputs are

Click here to view code image

$ python3 DelimiterChecker.py
Expression to check: a()
Delimiters balance in expression a()
$ python3 DelimiterChecker.py
Expression to check: a( b[4]d )
Delimiters balance in expression a( b[4]d )
$ python3 DelimiterChecker.py
Expression to check: a( b]4[d )
Error: ] at position 4 does not match left delimiter (
Error: ) at position 9 does not match left delimiter [
$ python3 DelimiterChecker.py
Expression to check: {{a( b]4[d )
Error: ] at position 6 does not match left delimiter (
Error: ) at position 11 does not match left delimiter [
Expression missing right delimiters for [{, {]

The messages printed by DelimiterChecker.py show the position and value of significant characters (delimiters) in the expression. After processing all the characters, any remaining delimiters on the stack are unmatched. The program prints an error for that using the Stack's string conversion method, which surrounds the list in square brackets, possibly leading to some confusion with the input string delimiters.

The Stack as a Conceptual Aid

Notice how convenient the stack is in the DelimiterChecker.py program. You could have set up an array to do what the stack does, but you would have had to worry about keeping track of an index to the most recently added character, as well as other bookkeeping tasks. The stack is conceptually easier to use. By providing limited access to its contents, using the push() and pop() methods, the stack has made the delimiter-checking program easier to understand and less error prone. (As carpenters will tell you, it’s safer and faster to use the right tool for the job.)

The Insert Button

After typing some text in the text entry box, select the Insert button. The tool responds by incrementing the _rear index and copying the value to cell 1. As with the stack, you can insert string values of limited length. Typing another string followed by pressing Return advances _rear to cell 2 and copies the value into it.

The Remove Button

When the queue has one or more items in it, selecting the Remove button copies the item at the _front cell to a variable named front. The _front cell is cleared and the index advances by one. The front variable holds the value returned by the operation.

Note that the _front and _rear indices can appear in any order. In the initial, empty queue, _rear was one less than _front. When the first item was inserted, both _rear and_front pointed to the same cell. Additional inserts advance _rear past _front. The remove operations advance _front past _rear.

Keep inserting values until all the cells are filled. Note how the _rear index wraps around from 9 to 0. When all the cells are filled, _rear is one less than _front. That’s the same relationship as when the queue was empty, but now the _nItems counter is 10, not 0.

The Peek Button

The peek operation returns the value of the item at the front of the queue without removing the item. (Like insert and remove, peek, when applied to a queue, is also called by a variety of other names.) If you select the Peek button, you see the value at _front copied to an output box. The queue remains unchanged.

Some queue implementations have a rearPeek() and a frontPeek() method, but usually you want to know what you’re about to remove, not what you just inserted.

The New Button

If you want to start with an empty queue, you can use the New button to create one. Because it’s based on an array, the size of the array is the argument that’s required. The Queue Visualization tool lets you choose a range of queue sizes up to a limit that allows for values to be easily displayed. The animation shows the steps taken in the call to the object constructor.

Empty and Full

If you try to remove an item when there are no items in the queue, you’ll get the Queue is empty! message. You’ll also see that the code is highlighted in a different color because this operation has raised an exception. Similarly, if you try to insert an item when all the cells are already occupied, you’ll get the Queue is full! message from a Queue overflow exception. These operations are shown in detail in the next section.

The Insert Button

Try inserting an item by typing a number in the text entry box and selecting Insert. You use numbers for the item key because priorities are often numeric, and this approach makes it easy to draw the height of the item as proportional to the key. The first item is inserted in the leftmost cell, and the nItems index is advanced to 1.

Now try inserting another item. Because the priority queue must keep the items ordered, it behaves like the OrderedArray you saw in Chapter 2. If the item you insert has a lower key than the first, it will go to the right. If you insert a higher key, the items with lower keys will be shifted to the right to make room for the new item. The new item’s key is compared with each item in the priority queue, starting with the one on the right. Items are shifted right until a cell becomes available where the new item can be inserted while preserving the key order.

Notice that there’s no wraparound in this implementation of the priority queue. Insertion is slow out of necessity because the proper in-order position must be found, but deletion is fast. A wraparound implementation wouldn’t improve the situation. Because there’s no wraparound, all the items are in the leftmost, lower index, cells of the array. There’s no need for two indices; all that’s needed is an nItems index.

Try inserting the same key multiple times and observe the behavior. The visualization tool gives the new item a different color to make it easier to distinguish them. You can think of the colors as different data associated with the numeric keys. Where does it insert the new key? It always goes to the left of the other equal-valued keys. Putting it to the left preserves the FIFO queue order of those items.

The Remove Button

When you use the Remove button, the item to be removed is always at the right of the array, in the cell to the left of the nItems index, so removal is quick and easy. The item is copied to a front variable, and the nItems index is decremented, just like in a stack. No shifting or comparisons are necessary.

The Peek Button

You can peek at the minimum item (find its value without removing it) with the Peek button. The value is copied to an output box like the stack and queue.

The New Button

You can create a new, empty, priority queue with the New button. Like the other data structures, the size of the underlying array is the required argument and is limited to what fits easily on the display. The visualization tool animates the steps of recording the size, allocating the array, and setting the nItems index to 0. There’s also a __pri attribute that we discuss later with the code.

Implementation Possibilities

The visualization program uses a particular implementation of priority queue that uses a single array for all the queued items. There are other possibilities, such as using separate queues for each priority or using a heap instead of an array (as discussed in Chapter 13, “Heaps”). Each one of these choices has different advantages.

The single array implementation has the advantage of simplicity at the cost of slowing down the insert or remove time. If you keep the array of items sorted by priority and arrival order, then time is needed to move items in the array during insertions to preserve that order. If you leave the array of items unsorted (but maintain the arrival order), then insertion can still be fast, but removal is slow as you search for the highest-priority item to remove. After you remove an item from the unsorted list, you must shift items within the array to close the gap created by the removal. The movement of items in the array is expected to move half of the items, on average. That happens for either insertion or deletion, depending on whether you keep the array contents sorted. Knowing the number of moves means that either insertion or removal will be an O(N) operation. We examine a specific implementation to see how that works out.

How Humans Evaluate Infix

How do you translate infix to postfix? Let’s examine a slightly easier question first: How does a human evaluate a normal infix expression? Although, as we stated earlier, such evaluation is difficult for a computer, we humans do it fairly easily because of countless hours looking at similar expressions in math class. It’s not hard to find the answer to 3+ 4+5, or 3×(4+5). By analyzing how you evaluate this expression, you can achieve some insight into the translation of such expressions into postfix.

Roughly speaking, when you “solve” an arithmetic expression, you follow rules something like this:

1. You read from left to right. (At least, we assume this is true. Sometimes people skip ahead, but for purposes of this discussion, you should assume you must read methodically, starting at the left.)

2. When you’ve read enough to evaluate two operands and an operator, you do the calculation and substitute the answer for these two operands and operator. (You may also need to solve other pending operations on the left, as we see later.)

3. You continue this process—going from left to right and evaluating when possible—until the end of the expression.

Table 4-3, Table 4-4, and Table 4-5 show three examples of how simple infix expressions are evaluated. Later, Tables 4-6, 4-7, and 4-8 show how closely these evaluations mirror the process of translating infix to postfix.

To evaluate 3+4−5, you would carry out the steps shown in Table 4-3.

You can’t evaluate the 3+4 until you see whether an operator follows the 4 and what operator it is. If it’s × or /, you need to wait before applying the + sign until you’ve evaluated the × or /. In this example, however, the operator following the 4 is a −, which has the same precedence (priority among operators) as a +, so when you see the −, you know you can evaluate 3+4, which is 7. The 7 then replaces the 3+4. You can evaluate the 7−5 when you arrive at the end of the expression, knowing that there are no more operators.

Because of precedence relationships, evaluating 3+4×5 is a bit more complicated, as shown in Table 4-4.

Here, you can’t add the 3 until you know the result of 4×5. Why not? Because multiplication has a higher precedence than addition. In fact, both × and / have a higher precedence than + and −, so all multiplications and divisions must be carried out before any additions or subtractions (unless parentheses dictate otherwise; see the next example).

Often, you can evaluate as you go from left to right, as in the preceding example. You need to be sure, when you come to an operand-operator-operand combination such as A+B, however, that the operator on the right side of the B isn’t one with a higher precedence than the +. If it does have a higher precedence, as in this example, you can’t do the addition yet. After you’ve read the 5 and found nothing after it, however, you know the multiplication can be carried out. Note that because multiplication has the highest priority among the four operators in this sample language, it doesn’t matter whether a × or / follows the 5, and the multiplication could proceed without looking at the next input. You can’t do the addition, however, until you’ve found out what’s beyond the 5. When you find there’s nothing more to read, you can go ahead and perform any remaining operations, knowing the highest precedence operators are on the right.

Parentheses are used to override the normal precedence of operators. Table 4-5 shows how you would evaluate 3×(4+5). Without the parentheses, you would do the multiplication first; with them, you do the addition first.

Here, you can’t evaluate anything until you’ve reached the closing parenthesis. Multiplication has a higher or equal precedence compared to the other operators, so ordinarily you could carry out 3×4 as soon as you see the 4. Parentheses, however, have an even higher precedence than × and /. Accordingly, you must evaluate anything in parentheses before using the result as an operand in any other calculation. The closing parenthesis tells you that you can go ahead and do the addition. You find that 4+5 is 9 and substitute it. Finding that there are no more higher-precedence operators afterward, you can evaluate 3×9 to obtain 27.

As you’ve seen in evaluating an infix arithmetic expression, you go both forward and backward through the expression. You go forward (left to right) reading operands and operators. When you have enough information to apply an operator, you go backward, recalling two operands and an operator and carrying out the arithmetic.

Sometimes, you must defer applying operators if they’re followed by higher-precedence operators or by parentheses. When this happens, you must apply the later, higher-precedence, operator first; then go backward (to the left) and apply earlier operators.

You could write an algorithm to carry out this kind of evaluation directly. As we noted, however, it’s easier to translate into postfix notation first.

How Humans Translate Infix to Postfix

To translate infix to postfix notation, you follow a similar set of rules to those for evaluating infix. There are, however, a few small changes. You don’t do any arithmetic. The idea is not to evaluate the infix expression, but to rearrange the operators and operands into a different format: postfix notation. The resulting postfix expression will be evaluated later.

As before, you read the infix from left to right, looking at each character in turn. As you go along, you copy these operands and operators to the postfix output string. The trick is knowing when to copy what.

If the character in the infix string is an operand, you copy it immediately to the postfix string. That is, if you see an A in the infix, you write an A to the postfix. There’s never any delay: you copy the operands as you get to them, no matter how long you must wait to copy their associated operators.

Knowing when to copy an operator is more complicated, but it’s the same as the rule for evaluating infix expressions. Whenever you could have used the operator to evaluate part of the infix expression (if you were evaluating instead of translating to postfix), you instead copy it to the postfix string.

Table 4-6 shows how A+B−C is translated into postfix notation.

Notice the similarity of this table to Table 4-3, which showed the evaluation of the infix expression 3+4−5. At each point where you would have done an evaluation in the earlier table, you instead simply write an operator to the postfix output.

Table 4-7 shows the translation of A+B×C to postfix. This translation parallels that of Table 4-4, which covered the evaluation of 3+4×5.

As the final example, Table 4-8 shows how A×(B+C) is translated to postfix. This process is similar to evaluating 3×(4+5) in Table 4-5. You can’t write any postfix operators until you see the closing parenthesis in the input.

As in the numerical evaluation process, you go both forward and backward through the infix expression to complete the translation to postfix. You can’t write an operator to the output (postfix) string if it’s followed by a higher-precedence operator or a left parenthesis. If it is, the higher-precedence operator or the operator in parentheses must be written to the postfix before the lower-priority operator.

Saving Operators on a Stack

You’ll notice in both Table 4-7 and Table 4-8 that the order of the operators is reversed going from infix to postfix. Because the first operator can’t be copied to the output until the second one has been copied, the operators were output to the postfix string in the opposite order they were read from the infix string. That suggests a stack might be useful for handling the operators. A longer example helps illustrate how that could work. Table 4-9 shows the translation to postfix of the infix expression A+B×(C−D).

Here you see the order of the operands is +×− in the original infix expression, but the reverse order, −×+, in the final postfix expression. This happens because × has higher precedence than +, and −, because it’s in parentheses, has higher precedence than ×. We need to track operators with lower precedence on the stack to be able to process them later. The last column in Table 4-9 shows the stack contents at various stages in the translation process.

Popping items from the stack allows you to, in a sense, go backward (right to left) through the input string. You’re not really examining the entire input string, only the operators and parentheses. They were pushed on the stack when reading the input, so now you can recall them in reverse order by popping them off the stack.

The operands (A, B, and so on) appear in the same order in infix and postfix, so you can write each one to the output as soon as you encounter it; they don’t need to be stored on a stack or reversed. Changing their order would also cause issues with operators that lack the commutative property like subtraction and division; A − B ≠ B − A.

Translation Rules

Let’s make the rules for infix-to-postfix translation more explicit. You read items from the infix input string and take the actions shown in Table 4-10. These actions are described in pseudocode, a blend of programming syntax and English.

In this table, the < and >= symbols are applied to the operator precedence, not numerical values. The inputOp operator has just been read from the infix input, while the top operator is popped off the stack. We use prec(inputOp) and prec(top) to mean the operator precedence of inputOp and top, respectively.

Convincing yourself that these rules work may take some effort. Tables 4-11, 4-12, and 4-13 show how the rules apply to the three sample infix expressions, similar to Tables 4-6, 4-7, and 4-8, except that the relevant rules for each step have been added. Try creating similar tables by starting with other simple infix expressions and using the rules to translate some of them to postfix.

Python Code to Convert Infix to Postfix

Listing 4-9 shows the beginning of the PostfixTranslate.py program, which uses the rules from Table 4-10 to translate an infix expression to a postfix expression. This is a long program file, so we show it in two parts. The first part provides the processing of the input string, finding the individual tokens in the expression and determining the precedence of operators.

LISTING 4-9 Processing Tokens in PostfixTranslate.py

Click here to view code image

from SimpleStack import Stack
from Queue import Queue
 
# Define operators and their precedence
# We group single character operators of equal precedence in strings
# Lowest precedence is on the left; highest on the right
# Parentheses are treated as high precedence operators
operators = ["|", "&", "+-", "*/%", "^", "()"]
def precedence(operator): # Get the precedence of an operator
   for p, ops in enumerate(operators):  # Loop through operators
      if operator in ops:               # If found,
         return p + 1                   # return precedence (low = 1)
      # else not an operator, return None
 
def delimiter(character):               # Determine if character is delimiter
   return precedence(character) == len(operators)
 
def nextToken(s):                       # Parse next token from input string
   token = ""                           # Token is operator or operand
   s = s.strip()                        # Remove any leading & trailing space
   if len(s) > 0:                       # If not end of input
      if precedence(s[0]):              # Check if first char. is operator
         token = s[0]                   # Token is a single char. operator
         s = s[1:]
      else:                             # its an operand, so take characters up
         while len(s) > 0 and not (     # to next operator or space
                precedence(s[0]) or s[0].isspace()):
            token += s[0]
            s = s[1:]
   return token, s                      # Return the token, and remaining input string

After importing the previous definitions of stacks and queues, the first statement of PostfixTranslate.py defines the operators that the program can process. We have expanded the number of operators that can be used. So far, we’ve only shown examples using the four most common operators, +−×/. This program adds several others available in Python. By putting these operator characters into an array of strings, we have grouped together operators with the same precedence and ordered the groups. Each array cell corresponds to a precedence level. You can look up the precedence of an operator by stepping through the array until you find the character in the string and returning the string’s position in the array. Note that we used the asterisk * for the multiplication symbol ×, to be consistent with Python and other programming languages.

The precedence() function does the lookup, returning a number for the precedence or None if the character is not an operator. The operators are all the single-character operators that Python allows. Parentheses are included in the array of operators for convenience. They act like operators when breaking an expression up into tokens. A separate delimiter() function tests whether its argument is one of these highest-precedence characters.

A function breaks the input string into tokens. A token is a substring that corresponds to exactly one operator, operand, or delimiter in the input expression.

The nextToken() function goes through the input string, skipping over any whitespace, and finding the first token at the beginning of the string. It returns that token along with the rest of the string after the token, which is used for the subsequent call to nextToken(). The function checks whether a character is an operator or a delimiter by checking whether the precedence function returns a number for it (or None for operands). All the operators and delimiters in this example are single characters.

For operands, this program allows multicharacter (multidigit) tokens. The while loop steps through the input string, s, checking whether the first character is an operator or whitespace. If it is not, the first character is added to the output token and removed from the input string. After the loop finds either an operator, delimiter, whitespace, or the end of the input string, the token is complete.

The PostfixTranslate() function appears in Listing 4-10 and does the main work by allocating a stack to hold the operators (and left parentheses) and a queue to hold the postfix output. As you saw with the InfixCalculator Visualization tool, the operators build up in the stack and are then popped and moved to the queue. The queue holds the output postfix string with each operand or operator in its own cell. That enables the program to add some whitespace between elements in the output to make it more legible, especially for operands with more than one digit or character.

PostfixTranslate() loops over the input expression/formula using a fencepost loop—a loop that performs some work on the initial item before entering the main loop body to perform work on all the remaining loop items. In this case, it extracts the first token and then loops until there are no more tokens in the input expression/formula.

After determining whether the current token is an operand, operator, or delimiter, the PostfixTranslate() function applies the rules in Table 4-10. The if delim … elif prec … else statement separates the processing of the three types. The Python statements are very close to the pseudocode used to describe the rules. This is the heart of the algorithm, so study it closely. The if delim: … block handles the parentheses, pushing open parentheses on the stack and then popping off operators between the opening and closing parentheses after they are found.

LISTING 4-10 The PostfixTranslate() Function

Click here to view code image

def PostfixTranslate(formula):       # Translate infix to Postfix
   postfix = Queue(100)              # Store postfix in queue temporarily
   s = Stack(100)                    # Parser stack for operators
 
   # For each token in the formula  (fencepost loop)
   token, formula = nextToken(formula)
   while token:
      prec = precedence(token)      # Is it an operator?
      delim = delimiter(token)      # Is it a delimiter?
      if delim:
         if token == '(':           # Open parenthesis
            s.push(token)           # Push parenthesis on stack
         else:                      # Closing parenthesis
            while not s.isEmpty():  # Pop items off stack
               top = s.pop()
               if top == '(':       # Until open paren found
                  break
               else:                # and put rest in output
                  postfix.insert(top)
 
      elif prec:                    # Input token is an operator
         while not s.isEmpty():     # Check top of stack
            top = s.pop()
            if (top == '(' or       # If open parenthesis, or a lower
                precedence(top) < prec): # precedence operator
                s.push(top)         # push it back on stack and
                break               # stop loop
            else:                   # Else top is higher precedence
                postfix.insert(top) # operator, so output it
         s.push(token)              # Push input token (op) on stack
 
      else:                         # Input token is an operand
         postfix.insert(token)      # and goes straight to output
 
      token, formula = nextToken(formula) # Fencepost loop
 
   while not s.isEmpty():           # At end of input, pop stack
      postfix.insert(s.pop())       # operators and move to output
 
   ans = ""
   while not postfix.isEmpty():     # Move postfix items to string
      if len(ans) > 0:
         ans += " "                 # Separate tokens with space
      ans += postfix.remove()
   return ans
 
if __name__ == '__main__':
   infix_expr = input("Infix expression to translate: ")
   print("The postfix representation of", infix_expr, "is:",
         PostfixTranslate(infix_expr))

In the elif prec: … block, new operators from the input string are processed. It uses a loop to walk back through the stack looking for open parentheses or lower-precedence operators. The code shows a bit of an optimization from the loop’s pseudocode for new operators:

While stack is not empty:

top = pop item from stack

If top is (, then push ( back on stack and break

Else if top is an operator:

If prec(top) >= prec(inputOp), output top

Else push top and break loop

The two highlighted phrases in the pseudocode perform the same operation because the open parenthesis is stored in the top variable. In the program, the two conditions are checked in the if (top == '(' or precedence(top) < prec): … statement. When top does not satisfy that condition, it must be an operator whose precedence is greater than or equal to that of the input operator in token. That’s the only condition where the top operator is output by inserting it into the postfix queue.

After all the tokens have been processed in the first while loop, any remaining operators on the stack are popped and output to the postfix queue, reversing their order. That work happens in the final while not s.isEmpty() loop.

At the end, the while not postfix.isEmpty() loop creates the ans string, by concatenating the operands and operators in the postfix output queue separated by spaces. The spaces don’t change the value of the expression but do make the string more readable.

After the function body of PostfixTranslate() is defined, the last section of the program is an if statement that is used to detect whether this file is being used as a program or as a module inside a bigger program. By testing whether the special variable, __name__, is set to the string ‘__main__’, the Python interpreter can determine whether this file is being loaded as the main file to be executed or as part of an import statement inside another file. When __name__ is ‘__main__’ it’s the main file to be executed, and this program prompts for an input infix expression to translate. It then prints that expression along with its postfix translation. The output looks like this:

Click here to view code image

$ python3 PostfixTranslate.py
Infix expression to translate: A+B-C
The postfix representation of A+B-C is: A B + C -
$ python3 PostfixTranslate.py
Infix expression to translate: A+B*C
The postfix representation of A+B*C is: A B C * +
$ python3 PostfixTranslate.py
Infix expression to translate: A*(B+C)
The postfix representation of A*(B+C) is: A B C + *
$ python3 PostfixTranslate.py
Infix expression to translate: A | B*C^D % E - F/G + H & J
The postfix representation of A | B*C^D % E - F/G + H & J is: A B C D ^ * E % F G /
- H + J & |

The last example uses all the operators the program knows about and shows how it interprets their precedence and ignores whitespace. The PostfixTranslate.py program doesn’t check the input for errors. If you type an incorrect infix expression, such as one with consecutive operators or unbalanced parentheses, the program will provide erroneous output.

Experiment with this program. Start with some simple infix expressions and see whether you can predict what the postfix will be. Then run the program to verify your answer. Pretty soon, “a postfix Jedi, you will become.” Note that you can also use the InfixCalculator tool to practice these transformations, but you won’t be able to use letters as variable names.

How Humans Evaluate Postfix

Figure 4-12 shows how a human can evaluate a postfix expression using visual inspection along with a pencil and paper. The postfix expression, 345+×612+/−, is shown in the gray rectangle. In this simplified example, operands can be only single-digit integers.

Start with the first operator on the left and draw an oval around it plus the two operands to its immediate left. This is marked as step ➊ in the figure. Then apply the operator to these two operands—performing the actual arithmetic—and write down the result inside the oval. In the figure, evaluating 4+5 gives 9, which will be used in step ➋.

Now go to the next operator to the right and draw an oval around it, the oval you already drew, and the operand to the left of that. Apply the operator to the previous oval and the new operand and write the result in the new oval, labeled ➋. Here 3×9 gives 27. Continue this process until all the operators have been applied: 1+2 evaluates to 3 in step ➌, and 6/3 is 2, in step ➍. The answer is the result in the largest oval at step ➎: 27−2 is 25.

Rules for Postfix Evaluation

How do you write a program to reproduce this evaluation process? As you can see, each time you come to an operator, you apply it to the last two operands you’ve seen. Remembering what the PostfixTranslate.py program does (Listing 4-10) suggests that it might be appropriate to store the operands on a stack. The approach for postfix evaluation, however, differs from the infix-to-postfix translation algorithm, where operators were stored on the stack. You can use the rules shown in Table 4-14 to evaluate postfix expressions.

When you’re done, pop the stack to obtain the answer. That’s all there is to it. This process is the computer equivalent of the human oval-drawing approach of Figure 4-12.

Python Code to Evaluate Postfix Expressions

In the infix-to-postfix translation, symbols (A, B, and so on) were allowed to stand for numbers. This approach worked because you weren’t performing arithmetic operations on the operands but merely rewriting them in a different format. Now say you want to evaluate a postfix expression, which means carrying out the arithmetic and obtaining an answer. The input must consist of actual numbers mixed with operators.

As shown in Listing 4-11, the PostfixEvaluate.py program imports the PostfixTranslate module and uses its functions to translate an infix expression to postfix before evaluating it. It makes use of the same nextToken() function from that module, but this time it’s applied to the translated postfix string. The fencepost loop goes through each of the tokens in the postfix string. For operators, the left and right operands are popped off the stack, the operation is performed, and the result is pushed back on the stack. For operands, the string version of the operand is converted to an integer and pushed on the stack.

LISTING 4-11 The PostfixEvaluate.py Program

Click here to view code image

from PostfixTranslate import *
from SimpleStack import *
 
def PostfixEvaluate(formula):          # Translate infix to Postfix and
                                       # evaluate the result
 
   postfix = PostfixTranslate(formula) # Postfix string
   s = Stack(100)                      # Operand stack
 
   token, postfix = nextToken(postfix)
   while token:
      prec = precedence(token)         # Is it an operator?
 
      if prec:                         # If input token is an operator
         right = s.pop()               # Get left and right operands
         left = s.pop()                # from stack
         if token == '|':              # Perform operation and push
            s.push(left | right)
         elif token == '&':
            s.push(left & right)
         elif token == '+':
            s.push(left + right)
         elif token == '-':
            s.push(left - right)
         elif token == '*':
            s.push(left * right)
         elif token == '/':
            s.push(left / right)
         elif token == '%':
            s.push(left % right)
         elif token == '^':
            s.push(left ^ right)
 
      else:                            # Else token is operand
         s.push(int(token))            # Convert to integer and push
 
      print('After processing', token, 'stack holds:', s)
 
      token, postfix = nextToken(postfix) # Fencepost loop
 
   print('Final result =', s.pop())    # At end of input, print result
 
if __name__ == '__main__':
   infix_expr = input("Infix expression to evaluate: ")
   print("The postfix representation of", infix_expr, "is",
         PostfixTranslate(infix_expr))
   PostfixEvaluate(infix_expr)

The PostfixEvaluate() method includes a print statement that shows the stack contents after each token is processed, plus a final print statement showing the answer. The “main” part of the program (when __name__ == '__main__') prompts the user for an infix expression, prints its postfix representation, and then evaluates it. Running the program produces a result like this:

Click here to view code image

$ python3 PostfixEvaluate.py
Infix expression to evaluate: 3*(4+5)-6/(1+2)
The postfix representation of 3*(4+5)-6/(1+2) is 3 4 5 + * 6 1 2 + / -
After processing 3 stack holds: [3]
After processing 4 stack holds: [3, 4]
After processing 5 stack holds: [3, 4, 5]
After processing + stack holds: [3, 9]
After processing * stack holds: [27]
After processing 6 stack holds: [27, 6]
After processing 1 stack holds: [27, 6, 1]
After processing 2 stack holds: [27, 6, 1, 2]
After processing + stack holds: [27, 6, 3]
After processing / stack holds: [27, 2.0]
After processing - stack holds: [25.0]
Final result = 25.0

Note this is the same calculation as shown in Figure 4-12, although the Python interpreter produced a floating-point number when it performed the division operation. The PostfixEvaluate.py program has not added any error checking on the input, so if you give it invalid expressions or expressions that contain names instead of numbers, the results will be wrong.

Experiment with the program and with the InfixCalculator tool. Try different expressions and check to see that they translate into postfix as you expect and verify the evaluation process. Use the animation controls to slow down or pause the calculator to see how the steps are carried out. Trying out different experiments can give you an understanding of the process faster than reading about it. One difference between the code and the InfixCalculator tool is that the tool creates floating-point numbers when division is used and pushes it on the stack. If that floating-point number creates an error, however, the tool will convert it to an integer and try again.