Rex Jaeschke is an independent computer consultant, author, and seminar leader. He participates in both ANSI and ISO C Standards meeting and is the editor of The Journal of C Translation, a quarterly publication aimed at implementors of C language translation tools. Readers are encouraged to submit column topics and suggestions to Rex at 2051 Swans Neck Way, Reston, VA 22091 or via UUCP at rex@aussie.com.
Stacks, Continued
Last month I talked about evaluating expressions. While a stack can be useful for this task, it does require that the expression be rearranged. For example, in programming languages we write arithmetic expressions using infix notation. That is, binary operators go between their operands as in (a + (b * c)).It would be very advantageous to be able to rewrite this expression in the order in which the operations are to be evaluated. You can do this by taking the precedence into account. This method, called postfix notation, completely removes the need for grouping parentheses. The previous expression written in postfix notation becomes a b c *+.
Now the multiplication applies to the two operands preceding it and the addition applies to that result and the operand preceding that, namely a. Expressions written in postfix notation lend themselves directly to being evaluated using a stack. For example, an H-P calculator requires you to enter expressions in postfix notation. This is often referred also as Reverse Polish Notation (RPN), since it is opposite to Polish (or prefix) notation. The trick then is to convert an infix expression to a postfix expression. Listing 1, Listing 2, and Listing 3 show much of the solution.
The main program prompts for and reads in an expression in infix notation, converts to the corresponding postfix notation, and prints the resulting string. It ignores white space in the input string. Figure 1 shows inputs and their results.
The real work is done by the function intopost shown in Listing 2. The stack manipulation functions are shown in Listing 3.
The conditional compilation code using TRACE is useful both in debugging and in demonstrating what is actually being pushed and popped along the way. Figure 2 shows an example.
This program goes a long way toward handling infix expressions but it clearly has some limitations. First, it handles only variable names, and then only those one character long. In reality it would need to handle constants as well and longer variable names. It would also have to maintain some kind of symbol table for each name encountered, along with type information since it can have mixed-mode arithmetic involving any arithmetic types of variables and constants. Also, the conversion function can only handle addition, subtraction, multiplication, and division. It is easy to add other operators but you would need to handle the precedence issue in a more general way. In intopost, precedence is hard-wired whereas some kind of table lookup would be more efficient as well as elegant.
Next month we'll look at stacks that handle different object types and stacks that share storage.