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 . 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." is a Java implementation of this process.

Screenshot Evaluation of a postfix expression

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.

Java graphics 04fig02

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.

Postfix-expression evaluation

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 . 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 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 : 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 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. is an example of a PostScript program that defines a function and draws a simple diagram.

Screenshot Sample PostScript program

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.

Java graphics 04fig03

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.

Infix-to-postfix conversion

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 . 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 ). is an implementation of this process that uses a stack of characters.

Screenshot Conversion of an infix expression to postfix

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.

Java graphics 04fig04

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 ). 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.

Exercises

Java graphics icon01 4.8 Extend Programs and to include the - (subtract) and / (divide) operations.

Java graphics icon01 4.9 Convert to postfix the expression 

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

Java graphics icon01 4.10 Give, in the same manner as , the contents of the stack as the following expression is evaluated by : 

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

Extend your solution to to include the unary operators - (negation) and $ (square root). Also, modify the abstract stack machine in 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:

Java graphics 04icon01

Java graphics roundbullet 4.13 Prove by induction that correctly evaluates any postfix expression.

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

ScreenshotCombine and into a single class that uses two stacks (an intStack and a charStack).

Java graphics roundbulletJava graphics roundbullet 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.