Previous Next |

We shall see a great many apps of stacks in the chapters that follow. As an introductory example, we now consider the use of stacks for evaluating arithmetic expressions. For example, suppose that we need to find the value of a simple arithmetic expression involving multiplication and addition of integers, such as

5 * ( ( (9 + 8) * (4 * 6) ) + 7)

The calculation involves saving intermediate results: For example, if we calculate `9 + 8` first, then we have to save the result `17` while, say, we compute `4 * 6`. A pushdown stack is the ideal mechanism for saving intermediate results in such a calculation.

We begin by considering a simpler problem, where the expression that we need to evaluate is in a form where each operator appears after its two arguments, rather than between them. As we shall see, any arithmetic expression can be arranged in this form, which is called postfix, by contrast with infix, the customary way of writing arithmetic expressions. The postfix representation of the expression in the previous paragraph is

5 9 8 + 4 6 * * 7 + *

The reverse of postfix is called prefix, or Polish notation (because it was invented by the Polish logician Lukasiewicz).

In infix, we need parentheses to distinguish, for example,

5 * ( ( ( 9 + 8 ) * ( 4 * 6 ) ) + 7 )

from

( ( 5 * 9 ) + 8 ) * ( ( 4 * 6 ) + 7 )

but parentheses are unnecessary in postfix (or prefix). To see why, we can consider the following process for converting a postfix expression to an infix expression: We replace all occurrences of two operands followed by an operator by their infix equivalent (with parentheses) to indicate that the result can be considered to be an operand. That is, we replace any occurrence of `a b *` and `a b +` by `(a * b)` and `(a + b)`, respectively. Then, we perform the same transformation on the resulting expression, continuing until all the operators have been processed. For our example, the transformation happens as follows:

5 9 8 + 4 6 * * 7 + * 5 ( 9 + 8 ) ( 4 * 6 ) * 7 + * 5 ( ( 9 + 8 ) * ( 4 * 6 ) ) 7 + * 5 ( ( ( 9 + 8 ) * ( 4 * 6 ) ) + 7 ) * ( 5 * ( ( ( 9 + 8 ) * ( 4 * 6 ) ) + 7 ) )

We can determine the operands associated with any operator in the postfix expression in this way, so no parentheses are necessary.

Alternatively, with the aid of a stack, we can actually perform the operations and evaluate any postfix expression, as illustrated in Screenshot. Moving from left to right, we interpret each operand as the command to "push the operand onto the stack," and each operator as the commands to "pop the two operands from the stack, perform the operation, and push the result." Program 4.5 is a Java implementation of this process.

This sequence shows the use of a stack to evaluate the postfix expression `5 9 8 + 4 6 * * 7 + *`. Proceeding from left to right through the expression, if we encounter a number, we push it on the stack; and if we encounter an operator, we push the result of applying the operator to the top two numbers on the stack.

Postfix notation and an associated pushdown stack give us a natural way to organize a series of computational procedures. Some calculators and some computing languages explicitly base their method of calculation on postfix and stack operationsâ€”every operation pops its arguments from the stack and returns its results to the stack.

This pushdown-stack client reads any postfix expression involving multiplication and addition of integers, then evaluates the expression (saving intermediate results on a stack) and prints the computed result. Operands are pushed onto the stack; operators are applied to the top two entries popped from the stack, with the result pushed back onto the stack.

The program assumes that the integers and operators are delimited by other characters of some kind (blanks, say), but does not check the legality of the input at all. The final `if` statement and the `while` loop perform a calculation similar to the Java `Integer.parseInt` method, which converts from string to integer representation.

class Postfix { public static void main(String[] args) { char[] a = args[0].toCharArray(); int N = a.length; intStack s = new intStack(N); for (int i = 0; i < N; i++) { if (a[i] == '+') s.push(s.pop() + s.pop()); if (a[i] == '*') s.push(s.pop() * s.pop()); if ((a[i] >= '0') && (a[i] <= '9')) s.push(0); while((a[i] >= '0') && (a[i] <= '9')) s.push(10*s.pop() + (a[i++]-'0')); } Out.println(s.pop() + ""); } }

One example of such a language is the PostScript language, which is used to print this tutorial. It is a complete coding language where programs are written in postfix and are interpreted with the aid of an internal stack, precisely as in Program 4.5. Although we cannot cover all the aspects of the language here (see reference section), it is sufficiently simple that we can study some actual programs to appreciate the utility of the postfix notation and the pushdown-stack abstraction. For example, the string

5 9 8 add 4 6 mul mul 7 add mul

is a PostScript program! Programs in PostScript consist of operators (such as `add` and `mul`) and operands (such as integers). As we did in Program 4.5 we interpret a program by reading it from left to right: If we encounter an operand, we push it onto the stack; if we encounter an operator, we pop its operands (if any) from the stack and push the result (if any). Thus, the execution of this program is fully described by Screenshot: The program leaves the value `2075` on the stack.

PostScript has a number of primitive operators that serve as instructions to an abstract plotting device; we can also define our own operators, or functions, which are like methods in Java. These functions are invoked with arguments on the stack in the same way as any other function. For example, the PostScript code

0 0 moveto 144 hill 0 72 moveto 72 hill stroke

corresponds to the sequence of actions "call `moveto` with arguments `0` and `0`, then call `hill` with argument `144`," and so forth. Some operators refer directly to the stack itself. For example the operator `dup` duplicates the entry at the top of the stack so, for example, the PostScript code

144 dup 0 rlineto 60 rotate dup 0 rlineto

corresponds to the sequence of actions "call `rlineto` with arguments `144` and `0`, then call `rotate` with argument `60`, then call `rlineto` with arguments `144` and `0`," and so forth. The PostScript program in Screenshot defines and uses the function `hill`. Functions in PostScript are like macros: The sequence `/hill { A } def` makes the name `hill` equivalent to the operator sequence inside the braces. Screenshot is an example of a PostScript program that defines a function and draws a simple diagram.

The diagram at the top was drawn by the PostScript program below it. The program is a postfix expression that uses the built-in functions `moveto`, `rlineto`, `rotate`, `stroke` and `dup` as well as the user-defined function `hill` (see text). The graphics commands are instructions to a plotting device: `moveto` instructs that device to go to the specified position on the page (coordinates are in points, which are 1/72 inch); `rlineto` instructs it to move to the specified position in coordinates relative to its current position, adding the line it makes to its current path; `rotate` instructs it to turn left the specified number of degrees; and `stroke` instructs it to draw the path that it has traced.

In the present context, our interest in PostScript is that this widely used coding language is based on the pushdown-stack abstraction. Indeed, many computers implement basic stack operations in hardware because they naturally implement a function-call mechanism: Save the current environment on entry to a procedure by pushing information onto a stack; restore the environment on exit by using information popped from the stack. As we see in , this connection between pushdown stacks and programs organized as functions that call functions is an essential paradigm of computation.

This program is another example of a pushdown-stack client. In this case, the stack contains characters. To convert `(A+B)` to the postfix form `A B +`, we ignore the left parenthesis, convert `A` to postfix, save the `+` on the stack, convert `B` to postfix, then, on encountering the right parenthesis, pop the stack and output the `+`.

class InfixToPostfix { public static void main(String[] args) { char[] a = args[0].toCharArray(); int N = a.length; charStack s = new charStack(N); for (int i = 0; i < N; i++) { if (a[i] == ')') Out.print(s.pop() + " "); if ((a[i] == '+') || (a[i] == '*')) s.push(a[i]); if ((a[i] >= '0') && (a[i] <= '9')) Out.print(a[i] + " "); } Out.println(""); } }

Returning to our original problem, we can also use a pushdown stack to convert fully parenthesized arithmetic expressions from infix to postfix, as illustrated in Screenshot. For this computation, we push the operators onto a stack and simply pass the operands through to the output. Then, each right parenthesis indicates that both arguments for the last operator have been output, so the operator itself can be popped and output. Note that arguments appear in the postfix expression in the same order as in the infix expression. It is also amusing to note that the left parentheses are not needed in the infix expression. The left parentheses would be required, however, if we could have operators that take differing numbers of operands (see Exercise 4.11). Program 4.6 is an implementation of this process that uses a stack of characters.

This sequence shows the use of a stack to convert the infix expression `(5 * ( ( (9 + 8) * (4 * 6) ) + 7) )` to its postfix form `5 9 8 + 4 6 * * 7 + *`. We proceed from left to right through the expression: If we encounter a number, we write it to the output; if we encounter a left parenthesis, we ignore it; if we encounter an operator, we push it on the stack; and if we encounter a right parenthesis, we write the operator at the top of the stack to the output.

In addition to providing two different examples of the use of the pushdown-stack abstraction, the entire algorithm that we have developed in this section for evaluating infix expressions is itself an exercise in abstraction. First, we convert the input to an intermediate representation (postfix). Second, we simulate the operation of an abstract stack-based machine to interpret and evaluate the expression. This same schema is followed by many modern programming-language translators, for efficiency and portability: The problem of compiling a Java program for a particular computer is broken into two tasks centered around an intermediate representation so that the problem of translating the program is separated from the problem of executing that program, just as we have done in this section. We shall see a related, but different, intermediate representation in .

This app also illustrates the value of ADTs and the need for generic implementations. Not only do we use two different stacks, but also one of the stacks holds items of type `char` (operators), whereas the other holds items of type `int` (operands). We might even combine both of the clients just considered into one program that would need both stacks (see Exercise 4.15). In , we consider the idea of using a single implementation for both stacks. While this approach is attractive, we should be aware that it might not always be desirable, because different implementations may have different performance characteristics; consequently, we might not wish to decide a priori that one implementation will serve both purposes. Indeed, our main focus is on the implementations and their performance, and we turn now to those topics for pushdown stacks.

4.8 Extend Programs 4.5 and 4.6 to include the

-(subtract) and/(divide) operations.4.9 Convert to postfix the expression

( 5 * ( ( 9 * 8 ) + ( 7 * ( 4 + 6 ) ) ) ).

4.10 Give, in the same manner as Screenshot, the contents of the stack as the following expression is evaluated by Program 4.5:

5 9 * 8 7 4 6 + * 2 1 3 * + * + *.

Extend your solution to Exercise 4.8 to include the unary operators

-(negation) and$(square root). Also, modify the abstract stack machine in Program 4.5 to use floating point. For example, given the expression(-(-1) + $((-1) * (-1)-(4 * (-1))))/2

your program should print the value 1.618034.

Write a PostScript program that draws this figure:

4.13 Prove by induction that Program 4.5 correctly evaluates any postfix expression.

Write a program that converts a postfix expression to infix, using a pushdown stack.

Combine Program 4.5 and Program 4.6 into a single class that uses two stacks (an

intStackand acharStack).4.16 Implement a compiler and interpreter for a coding language where each program consists of a single arithmetic expression preceded by a sequence of assignment statements with arithmetic expressions involving integers and variables named with single lower case characters. For example, given the input

(x = 1) (y = (x + 1)) (((x + y) * 3) + (4 * x))

your program should print the value 13.

Previous Next |