Data Structures and Algorithms with C · Lecture Notes
Chapter 8: Stack and Queue Applications
A stack is a simple structure that returns the most recently pushed item first. This simplicity makes it indispensable in many corners of programming. These notes treat two classic applications of the stack in detail. The first is searching for a way out of a maze: every fork in the path is pushed onto the stack, and when a dead end is reached, the search returns to the last fork. The second is the evaluation of arithmetic expressions. A compiler first converts an expression such as a / b − c + d * e − a * c to postfix notation according to operator precedence, and then evaluates it in a single pass. Both jobs are done with a stack. The notes close with other applications, such as parenthesis checking, undo/redo, and non-recursive tree traversal, and with the difference a queue makes on the same problems. For every routine the C code, a line-by-line explanation, a code trace, and a complexity analysis are given.
Learning outcomes
- Coding backtracking
- Search a maze with a stack, return from a dead end to the last fork, and follow this process step by step.
- Constructing the worst case
- Design the input on which an algorithm does the most work and justify its cost with that input.
- Converting notations
- Convert between infix, prefix, and postfix notation by hand and with a stack.
- Evaluating a postfix expression
- Run the
evalroutine step by step with an operand stack, and get the order in which operands are popped right. - Coding precedence
- Write the routine that converts an infix expression to postfix using an
isp/icptable, and make the right decision on equal precedence. - Generalizing the stack
- Use the stack for parenthesis checking, for problems such as undo/redo, and for non-recursive traversal; use the queue for shortest-path search.
8.1The stack and backtracking
All the routines in these notes are built on a single structure, so let us first recall the stack briefly. A stack is a linear structure in which items are inserted at one end only and removed from the same end. This end is called the top. Insertion is called "putting on top" (push) and removal "taking from the top" (pop). The item pushed last comes out first. This rule is called last in, first out (LIFO).
A stack is an ordered collection of items in which insertion and removal take place only at the end called the top. In a stack implemented with an array, the items sit in cells stack[0], stack[1], …; the variable top holds the index of the topmost item. In an empty stack, top == -1. Pushing is done with stack[++top] = x and popping with x = stack[top--]; both take O(1) time.
In the array implementation there are two boundary cases. When the array is full, no new item can be pushed; this is called overflow. No item can be popped from an empty stack; this is called underflow. The short code in these notes does not write these checks in most places. For example, the eval routine assumes that the stack never runs empty on a well-formed expression. The push and pop functions used in the verification programs, on the other hand, check both cases. In a real program these checks must not be skipped.
The "last in, first out" behavior of the stack fits one kind of problem naturally. In any problem that proceeds by making a series of decisions, where a wrong decision sometimes has to be undone, the most recent decision is the first to be undone. For example, while moving through a maze, a direction is chosen at every fork. If the chosen path ends in a dead end, one returns to the nearest fork, that is, the one passed most recently, and tries another direction there. This method is called backtracking.
Backtracking is a search method that extends a partial solution step by step and, when it reaches a dead end, undoes the last choice and tries the next option. The choices are kept on a stack: a new choice is pushed, and a return is made by popping the top choice.
Backtracking can also be written recursively. In that case the programmer does not build the stack; every recursive call adds a frame to the call stack, and the return of the call performs the step back. The maze routine, however, builds the stack explicitly, as an array. In this way what is on the stack can be seen and traced at every moment. This is the best way to understand the role of the stack in backtracking.
8.2The maze problem
The maze problem is the classic example of backtracking with a stack. There is an entrance, an exit, and passages divided by walls between them. A path from the entrance to the exit is sought. The problem looks simple, but its details are instructive. How are the directions coded, how is entering the same cell twice prevented, and from where does the search continue after a return? The answers to these questions show how important the choice of data structure is.
8.2.1Representing the maze with a matrix
The maze is represented by a two-dimensional integer matrix. Each cell of the matrix is a square of the maze. The value 0 stands for an open path and the value 1 for a wall. Figure 8.1 shows the maze used in these notes. Gray squares are walls and white squares are open paths. The entrance is cell [1][1], marked with the letter S, and the exit is cell [6][6], marked with the letter X. The size of the maze is written m × p: m rows and p columns. Here the interior is 6 × 6.
[1][1], exit X = [6][6]. Row 0, row 7, column 0, and column 7 on the outer frame are walls throughout.The matrix in the figure is 8 × 8, although the maze itself is 6 × 6. The two extra rows and two extra columns are a deliberate trick. The border of the matrix is surrounded all the way around with 1, that is, with wall. The reason is this. Looking north from a cell on the edge, for example from [1][1], one goes to cell [0][1]. Without the frame this cell would lie outside the matrix: an invalid index such as [-1][0] would arise in a 6 × 6 array. C does not check array bounds. Reading outside an array is undefined behavior; the program either crashes or mistakes some random memory value for a wall or a path.
Without the frame, four conditions of the form "am I leaving the matrix?" would have to be checked at every step. The frame makes this check unnecessary. Every cell on the outer ring is a wall, and a wall is never entered. The algorithm therefore never steps out of the interior, and every neighbor index stays valid. Extra cells of this kind, which eliminate edge cases, are generally called sentinels. The cost is very small: a matrix of (m + 2)(p + 2) cells.
Freedom of movement is also part of the problem. In this maze, in addition to horizontal and vertical moves, diagonal moves are also allowed. From a cell one can go to its eight neighbors. Diagonal moves make it possible to get around the tight corners of the maze. For example, one can go from [2][1] to [3][2] only with a diagonal step, because [3][1] and [2][2] in between are walls.
The algorithm has two more needs. First, the same cell must not be entered a second time. Otherwise one could go back and forth between two cells forever. The visited cells are therefore marked in a separate mark matrix. Second, when a dead end is reached, one must return to the last fork. The most recently passed fork is the first place to return to; this is exactly the definition of a stack.
8.2.2Eight directions and the move table
The eight directions are numbered from 0 to 7. Direction 0 is north; the numbers increase clockwise. Direction 1 is northeast, 2 east, 3 southeast, 4 south, 5 southwest, 6 west, and 7 northwest. Figure 8.2 shows the eight neighbors of a cell and the index of each neighbor.
[i][j]. Direction 0 is north ([i−1][j]); the following directions clockwise are 1…7.Moving in a direction means adding a small number to the row index and to the column index. Going north decreases the row by one and leaves the column unchanged: (−1, 0). Going southeast increases both by one: (+1, +1). These eight pairs are collected in Table 8.1.
| dir | Name | move[dir].vert | move[dir].horiz |
|---|---|---|---|
| 0 | N (north) | −1 | 0 |
| 1 | NE (northeast) | −1 | 1 |
| 2 | E (east) | 0 | 1 |
| 3 | SE (southeast) | 1 | 1 |
| 4 | S (south) | 1 | 0 |
| 5 | SW (southwest) | 1 | −1 |
| 6 | W (west) | 0 | −1 |
| 7 | NW (northwest) | −1 | −1 |
This table is called a look-up table. It means reading a precomputed array instead of computing the value with conditions every time. Without the table, eight separate if statements would be written: "if the direction is 0, decrease the row by one; if it is 1, decrease the row and increase the column…" The table reduces these eight branches to a single line:
next_row = row + move[dir].vert;
next_col = col + move[dir].horiz;In this way the direction becomes an ordinary loop variable. To try all eight directions it is enough to increase dir from 0 to 7. Changing the order in which directions are tried also becomes easy: only the order of the rows of the table changes, and the code stays the same.
8.2.3Data definitions
All the constants, types, and global variables used by the routine are collected in the following declarations from the slides:
#define MAX_STACK_SIZE 100
#define EXIT_ROW 6
#define EXIT_COL 6
typedef struct { short int vert, horiz; } offsets;
offsets move[8] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1},
{1, 0}, {1, -1}, {0, -1}, {-1, -1}};
typedef struct { short int row, col, dir; } element;
element stack[MAX_STACK_SIZE];
int top = -1;
short int mark[8][8];
short int maze[8][8] = {{1,1,1,1,1,1,1,1},
{1,0,1,0,0,0,1,1}, {1,0,1,0,1,1,1,1},
{1,1,0,1,1,1,1,1}, {1,0,1,1,0,1,1,1},
{1,1,0,0,1,0,1,1}, {1,1,1,1,1,1,0,1},
{1,1,1,1,1,1,1,1}};MAX_STACK_SIZEis the size of the stack array.EXIT_ROWandEXIT_COLare the coordinates of the exit cell.- The
offsetsstructure holds the two components of a direction. Themove[8]array is the table of Table 8.1 itself; the first pair,{-1, 0}, corresponds to direction 0 (north). Since the values are small,short intis sufficient. elementis the record pushed onto the stack. It has three fields: the row of a cell, its column, and the direction from which the search should continue if we return to that cell (dir). This third field is very important. If only the position were kept on the stack, the directions of that cell would be tried again from 0 on a return. The direction field stores the information "in this cell I have looked as far as this direction".- The
stackarray is the stack itself;top = -1says that the stack is empty. markmarks the visited cells. Because it is a global array, C fills it with zeros when the program starts; no initial value is needed. If it were a local array, its contents would be indeterminate.mazeis an 8 × 8 matrix surrounded by 1s. Each inner pair of braces is a row; the first row is all 1s.
The maximum number of items the stack will hold can also be estimated in advance. A cell is pushed onto the stack only when moving from it to a new, unvisited cell. Since each open cell is visited at most once, the number of items on the stack cannot exceed the number of open cells. The interior of this maze has 13 open cells (the verification program also counted 13). The value 100 of MAX_STACK_SIZE is more than enough for this maze. For a general m × p maze, a safe upper bound is m · p.
8.2.4The path routine
The path-finding routine is called path. To keep the code readable, the slides give it in two parts; the two parts follow one another below:
void path(void) {
short int row, col, next_row, next_col;
int i, dir, found = FALSE;
element position;
stack[0].row = stack[0].col = 1;
stack[0].dir = 1; /* push the start */
mark[1][1] = 1; top = 0;
while (top > -1 && !found) {
position = pop(&top); /* next one */
row = position.row;
col = position.col;
dir = position.dir; /* which way */
while (dir < 8 && !found) {
next_row = row + move[dir].vert;
next_col = col + move[dir].horiz; if (next_row == EXIT_ROW &&
next_col == EXIT_COL)
found = TRUE; /* the exit? */
else if (!maze[next_row][next_col] &&
!mark[next_row][next_col]) {
mark[next_row][next_col] = 1;
position.row = row; /* came from */
position.col = col;
position.dir = ++dir; /* resume dir */
push(&top, position);
row = next_row; col = next_col;
dir = 0;
} else ++dir; /* try another */
} /* back up */
}The code consists of two nested loops. The outer loop takes a position from the stack; the inner loop advances from that position as far as it can. Let us look at it line by line.
- At the start, the entrance cell
(1, 1)is pushed onto the stack. Its direction field is 1. Direction 0 is north, and[0][1]is a wall on the frame; there is no need to try it. The entrance cell is marked in themarkmatrix andtop = 0. - The outer loop runs as long as the stack is not empty and the exit has not been found. In each round a
positionis popped from the stack.row,col, anddirare read from this record. In other words: "I am in this cell and will start trying from this direction." - The inner loop runs as long as
dirhas not reached 8 and the exit has not been found. In each round a neighbor is computed:(next_row, next_col). - If the neighbor is the exit cell,
foundbecomes true and both loops end. - If the neighbor is an open path (
!maze[…]) and has not been visited before (!mark[…]), the search moves into that cell. First the neighbor is marked. Then the current cell is pushed onto the stack, but++diris written into the direction field. This says: "if I return, let me continue from the next direction". Thenrowandcolare turned to the new cell, and withdir = 0all directions of the new cell are tried from the start. - If the neighbor is a wall or has been visited, only
++diris executed and the next direction is tried. - If the inner loop ends with
dir == 8, all eight directions of that cell are exhausted; the cell is a dead end. The code does nothing in this case. In the next round the outer loop pops the last record from the stack, and so a return to the previous cell takes place. The comment "back up" in the code refers to this moment.
A few details need attention. First, the exit check is done before the wall check. In this maze the exit cell is open and the order does not matter. But the exit cell is never marked in the mark matrix; the search ends the moment it is seen. Second, the record pushed onto the stack is not the new cell but the cell that was left. The new cell sits in the variables row and col. When the exit is found, the complete path therefore consists of three parts: the positions on the stack (from stack[0] to stack[top]), the cell where the search currently stands, and the exit cell. As the slides note, the last part of the routine prints these three parts in order; if the exit was not found, the message "No exit path found!" is printed. In the verification program this last part was completed as follows:
if (found) {
printf("row col\n");
for (i = 0; i <= top; i++) /* path on stack */
printf("%2d%5d\n", stack[i].row, stack[i].col);
printf("%2d%5d\n", row, col); /* last position */
printf("%2d%5d\n", EXIT_ROW, EXIT_COL);
} else printf("No exit path found!\n");Third, found, TRUE, and FALSE are a habit from before C99's bool type: they are integers defined with #define FALSE 0 and #define TRUE 1. push and pop are the two familiar functions of the stack implementation; they take top by address because they change it. Fourth, the line position.dir = ++dir both computes the value to be written into the record and changes the local dir. Since dir = 0 is written right afterward, the local change has no effect; what matters is the value written into the record.
Forgetting to mark the new cell. If the line mark[next_row][next_col] = 1 is not written, the algorithm moves from (1, 1) to (2, 1), looks north from there, and returns to (1, 1). It goes back and forth between two cells, adding a record to the stack at every crossing. In the end the stack overflows or the program stays in an infinite loop. The visited mark is the guarantee of termination.
The step-by-step trace slide of the slides writes the same logic more briefly, abbreviating the variable names of the inner loop (nr, nc) and building the new record in one line:
while (top > -1 && !found) {
position = pop(&top);
row = position.row; col = position.col;
dir = position.dir;
while (dir < 8 && !found) {
nr = row + move[dir].vert;
nc = col + move[dir].horiz;
if (nr == EXIT_ROW && nc == EXIT_COL)
found = TRUE;
else if (!maze[nr][nc] &&
!mark[nr][nc]) {
mark[nr][nc] = 1;
position = (element){row, col, ++dir};
push(&top, position);
row = nr; col = nc; dir = 0;
} else ++dir;
} }The expression (element){row, col, ++dir} here is a compound literal, introduced in C99. It builds an unnamed temporary element object and fills its fields in order. It does in one line the work of three separate assignments. This version was also run separately in the verification program and produced the same stack movements.
8.2.5Code trace: backtracking with a stack
Let us run the routine on the maze of Figure 8.1. At each step the contents of the stack are written as row,col,dir triples, from bottom to top. Table 8.2 gives the stack operations in order; the rows are identical to the output produced by the verification program.
| Step | Event | Move | Stack (bottom to top) | top |
|---|---|---|---|---|
| 0 | Start | — | 1,1,1 | 0 |
| 1 | pop (1,1), start from dir 1 | — | (empty) | −1 |
| 2 | push (1,1, dir 5) | (1,1) dir 4 (S) → (2,1) | 1,1,5 | 0 |
| 3 | push (2,1, dir 4) | (2,1) dir 3 (SE) → (3,2) | 1,1,5 · 2,1,4 | 1 |
| 4 | push (3,2, dir 2) | (3,2) dir 1 (NE) → (2,3) | … · 3,2,2 | 2 |
| 5 | push (2,3, dir 1) | (2,3) dir 0 (N) → (1,3) | … · 3,2,2 · 2,3,1 | 3 |
| 6 | push (1,3, dir 3) | (1,3) dir 2 (E) → (1,4) | … · 2,3,1 · 1,3,3 | 4 |
| 7 | push (1,4, dir 3) | (1,4) dir 2 (E) → (1,5) | … · 1,3,3 · 1,4,3 | 5 |
| 8 | (1,5) dead end; pop (1,4) | dir 3…7 blocked | … · 2,3,1 · 1,3,3 | 4 |
| 9 | pop (1,3) | dir 3…7 blocked | … · 3,2,2 · 2,3,1 | 3 |
| 10 | pop (2,3) | dir 1…7 blocked | 1,1,5 · 2,1,4 · 3,2,2 | 2 |
| 11 | pop (3,2) | continue from dir 2 | 1,1,5 · 2,1,4 | 1 |
| 12 | push (3,2, dir 6) | (3,2) dir 5 (SW) → (4,1) | 1,1,5 · 2,1,4 · 3,2,6 | 2 |
| 13 | push (4,1, dir 4) | (4,1) dir 3 (SE) → (5,2) | … · 3,2,6 · 4,1,4 | 3 |
| 14 | push (5,2, dir 3) | (5,2) dir 2 (E) → (5,3) | … · 4,1,4 · 5,2,3 | 4 |
| 15 | push (5,3, dir 2) | (5,3) dir 1 (NE) → (4,4) | … · 5,2,3 · 5,3,2 | 5 |
| 16 | push (4,4, dir 4) | (4,4) dir 3 (SE) → (5,5) | … · 5,3,2 · 4,4,4 | 6 |
| 17 | Exit found | (5,5) dir 3 (SE) → (6,6) = X | stack + (5,5) + (6,6) | 6 |
The first steps advance straight ahead. At (1,1) directions 1, 2, and 3 run into walls; direction 4 (south) opens onto (2,1). In this move (1,1) is pushed with dir 5: if we return, the search will continue from the southwest. From (2,1) the search goes southeast, from there northeast, and from there north. The algorithm enters the corridor along the top edge of the maze through cells (1,3), (1,4), and (1,5).
(1,5); none of this cell's eight neighbors is open and unvisited. In the middle, after four steps back, the search has returned to (3,2) and continues from dir 2. On the right the exit has been found; the path consists of the positions on the stack, (5,5), and (6,6).(1,5) is a dead end. Seven of its eight neighbors are walls and one ((1,4)) has been visited. The inner loop ends with dir == 8 and the outer loop pops (1,4, dir 3) from the stack. This is one step back. At (1,4) the remaining directions from 3 on are tried: southeast (2,5) and south (2,4) are walls, southwest (2,3) and west (1,3) have been visited, and northwest is a wall. No direction opens up; the search goes back again. The same happens for (1,3) and (2,3). After four steps back, the search arrives at (3,2) and continues from dir 2.
Here the value of the direction field shows. At (3,2) directions 0 and 1 have been tried before; direction 1 had in fact led to the dead-end corridor. The value 2 in the record prevents these two directions from being tried again. Directions 2, 3, and 4 are walls; direction 5 (southwest) opens onto (4,1). From here the path runs toward the exit through a single corridor: (4,1) → (5,2) → (5,3) → (4,4) → (5,5). At (5,5), direction 3 (southeast) hits the exit cell and the search ends.
The path found is: (1,1), (2,1), (3,2), (4,1), (5,2), (5,3), (4,4), (5,5), (6,6). That is 9 cells in total. The first seven are read from the stack (top = 6, that is, 7 records), the eighth is the current position, and the ninth is the exit. Over the whole run, 11 pushes and 5 pops were made. The stack reached at most 7 records. The four cells in the dead-end corridor ((2,3), (1,3), (1,4), (1,5)) were visited but are not part of the path. Apart from the exit, all 12 open cells were visited.
8.2.6The worst case
The maze program is a brute-force search. It uses no intelligence: it does not look at which direction the exit lies in, and it always tries the directions in the same order. The eight-entry look-up table has shortened the code and made the job easier, but the search itself is blind. How much work such an algorithm does depends largely on the input. In some mazes the exit is found in a few steps; in others nearly the whole maze is explored.
To state the worst-case cost of an algorithm, it is not enough to compute an upper bound; one must also show that an input that actually reaches that bound exists. This input is called the worst-case input. In the maze, what determines the worst-case input is the order in which directions are scanned. In every cell the algorithm looks north first, then northeast, and so on. If the first path tried in this order is very long, the algorithm follows it to the end.
Figure 8.4 compares the two inputs.
- Input 1: The first path tried is long but correct; it leads to the exit. The algorithm never goes back on this path. Only pushes are made, no pops. The amount of work is proportional to the length of the path.
- Input 2: The first path tried is long and wrong; it curls into the maze like a spiral and ends in a dead end. The algorithm follows this path to the end, and the stack fills with one record for every cell of the spiral. Once the dead end is reached, the stack is emptied one record at a time; at each step back the remaining directions of that cell are tried too. Only when the whole spiral is exhausted does the search return to the start and try the short, correct path. The solution is reached after everything except the correct path has been explored.
Input 2 is the worst-case input: it makes the algorithm do all the work it can possibly do. Every open cell is visited once, pushed onto the stack once, and popped once. This analysis also shows a principle. Before judging an algorithm "slow" or "fast", one must examine how it behaves on which input. It is not right to pass judgment on an algorithm that has not been analyzed.
8.2.7Complexity and comparison with a queue
Let us find the cost of path by counting. Let the size of the maze be m × p.
- Time. A cell is pushed onto the stack only when moving from it to an unvisited cell, and thanks to
markeach cell is visited at most once. The total number of pushes is therefore at most the number of open cells. The number of pops cannot exceed it either. In every cell the inner loop tries at most eight directions; thanks to the direction field, directions tried earlier are not tried again on a return. The total number of direction trials for one cell is therefore at most 8, plus one round for each pop. The result: O(8 · m · p) = O(m · p). On the worst-case input this bound is reached, so the worst case is Θ(m · p). - Memory. The stack grows to at most the number of open cells: O(m · p). The
markmatrix also holds (m + 2)(p + 2) cells, which is O(m · p).
This search with a stack is an example of depth-first search (DFS). One goes in one direction and descends as deep as possible; one returns only at a dead end. This search has an important weakness: the path found is not necessarily the shortest. The algorithm returns the first path it finds. Because of the order in which directions are tried, that path may wind around a distant corner of the maze. In this maze the search ran into the dead end (2,3) → (1,3) → (1,4) → (1,5), came back, and found a path of 9 cells.
If a queue is used instead of the stack, the character of the search changes completely. A queue works by the first-in-first-out (FIFO) rule. The start cell is put into the queue. At each step a cell is taken from the front of the queue and all of its unvisited open neighbors are added at the rear. The cells are thus expanded in order of their distance from the entrance: first those at distance 1, then those at distance 2, and so on. This method is called breadth-first search (BFS).
Depth-first search (DFS) is a search that goes to a neighbor, descends as deep as possible, and at a dead end returns to the latest fork; it is done with a stack or with recursion. Breadth-first search (BFS) is a search that visits nodes in order of their distance from the start; it is done with a queue. If all steps cost the same, the path by which BFS first reaches a cell is the shortest path to that cell.
Why BFS guarantees the shortest path can be explained briefly. The cells in the queue are always ordered by distance: first all those at distance d, then those at distance d + 1. When a cell is reached for the first time, a distance is recorded for it and the cell never enters the queue again. If a cell at distance d could be reached by a shorter path, the previous cell on that path would have left the queue earlier and the cell would have been reached before. The first arrival is therefore always by a shortest path.
In this maze BFS also finds the 9-cell path. That is, the two searches gave a path of the same length here; the BFS in the verification program computed it as 9 cells. The reason is that the maze is narrow: there is a single corridor to the exit. In general, the path found by DFS can be much longer. BFS has a price too: to be able to reconstruct the path, one must store from which cell each cell was reached. The time and memory cost of the two searches are of the same order: O(m · p). The complete code that finds the shortest path with BFS is given in the exercise solutions.
The person best placed to examine the code of these two algorithms is the one who wrote them. Someone else cannot analyze exactly what the code does without tracing it step by step. Code-trace tables are important for this reason: they give the author a chance to test the code and make its behavior visible to the reader.
8.3Expression notations
One of the oldest and most common applications of the stack is the evaluation of arithmetic and logical expressions. When a compiler reads the line x = a / b − c + d * e − a * c, it has to decide in which order to compute this expression. This section defines the problem and introduces the three notations on which the solution rests.
8.3.1The expression evaluation problem
Evaluation of expressions means computing the value of an expression while obeying operator precedence and associativity. An expression consists of two kinds of elements. Operators are symbols that specify the operation to perform, such as +, −, *, and /. Operands are the values the operation is applied to: variables such as a and b, or constants such as 4 and 2. Parentheses are part of the expression as well and change the order of computation.
Let us see with an example why the problem is hard. Let a = 4, b = 2, c = 2, d = 3, e = 3. The expression a / b − c + d * e − a * c reads in mathematics as follows: first the divisions and multiplications, then the additions and subtractions from left to right. That is, ((4 / 2) − 2) + (3 * 3) − (4 * 2). This equals 2 − 2 + 9 − 8 = 1. Someone who evaluates the same expression from left to right, ignoring precedence, would get ((((4/2) − 2) + 3) · 3 − 4) · 2 = 10. The correct result is 1.
A human looks at the expression as a whole and picks out the multiplications first. A computer reads the expression from left to right, character by character. When it sees an operator it cannot apply it yet, because a higher-precedence operator may follow on its right. In a + b * c, computing a + b when the + is seen would be wrong; b * c is needed first. Parentheses complicate matters further: in the expression a / (b − c) + d * (e − a) * c, the subtractions inside the parentheses must be done first.
The solution compilers have used for years has two stages:
- The expression is converted to postfix notation, taking operator precedence and parentheses into account. In this notation there are no parentheses and no precedence; the operators are lined up in the order in which they will be applied.
- The postfix expression is evaluated from left to right in a single pass.
Both stages are done with a stack. This is not a new invention. Many people have solved this problem many times, and a well-known solution exists. On meeting a problem, one should first look for such known solutions and find the fastest way. Only if the problem is truly unsolved does discovery begin.
8.3.2Precedence and associativity
Two rules determine which operator in an expression is applied first.
Operator precedence is the ranking that determines which of different operators is applied first: in C, * comes before +. Associativity determines whether operators of the same precedence are applied from left to right or from right to left: a − b − c means (a − b) − c, because − associates from left to right.
Table 8.3 summarizes the part of C's precedence table needed for these notes. The rows are given in order of decreasing precedence from top to bottom.
| Precedence | Operators | Associativity |
|---|---|---|
| highest | () [] -> . | left to right |
unary − ! ++ -- * & | right to left | |
* / % | left to right | |
+ − | left to right | |
< <= > >= | left to right | |
== != | left to right | |
&& | left to right | |
| lowest | || | left to right |
When reading the table, precedence decides first; if precedence is equal, associativity decides. Parentheses override both: the part inside parentheses is always computed first. The unary operators in the second row (minus sign, logical not, increment and decrement, dereference and address-of) associate from right to left. For example, *p++ means *(p++). The table does not contain all of C's operators; shift, bitwise, conditional, and assignment operators are not included here.
Let us parenthesize the expression a / b − c + d * e − a * c according to the rules. First the operators with the highest precedence: / and the two *. These become (a / b), (d * e), and (a * c). Three additions/subtractions remain: (a/b) − c + (d*e) − (a*c). All have the same precedence and associate from left to right. First the left − is applied, then +, and finally the right −. The result: (((a / b) − c) + (d * e)) − (a * c).
The algorithms in these notes are limited to the five binary operators (+ − * / %) and parentheses. Unary minus, comparison, and logical operators do not change the method; only the precedence table grows. The table in the book by Horowitz, Sahni, and Anderson-Freed (Figure 3.12) contains all of these operators.
Forgetting associativity and evaluating operators of the same precedence from right to left. 8 − 4 − 2 from left to right is (8 − 4) − 2 = 2. Evaluated from the right, it gives 8 − (4 − 2) = 6. For addition and multiplication this mistake does not change the result, because these operations are associative; for subtraction and division it does.
8.3.3Infix, prefix, and postfix
An expression can be written in three forms, depending on where the operator stands relative to its operands. The notations are called infix, prefix, and postfix; these short names are used in the slide titles and function names (postfix, prefix_eval).
Infix notation: the operator is written between its two operands, a + b. To evaluate it, parentheses and precedence must be taken into account. Prefix notation (Polish notation): the operator is written before its operands, + a b. Postfix notation (reverse Polish notation): the operator is written after its operands, a b +. In prefix and postfix notation no parentheses are needed; the expression is evaluated without looking at precedence.
The name "Polish notation" comes from the Polish logician Jan Łukasiewicz, who proposed prefix notation for logical formulas in the 1920s. Postfix notation is its reverse. Reverse Polish notation was once also used in some calculators: the user first entered two numbers and then pressed the operation key.
Table 8.4 gives the equivalents of four expressions in the three notations. Every row in the table was produced with the postfix and prefix functions of the verification program.
| No | Prefix | Infix | Postfix |
|---|---|---|---|
| 1 | *34 | 3*4 | 34* |
| 2 | +2*34 | 2+3*4 | 234*+ |
| 3 | -*+abc/da | (a+b)*c-d/a | ab+c*da/- |
| 4 | **/a+-bcd-eac | (a/(b-c+d))*(e-a)*c | abc-d+/ea-*c* |
The second row of the table shows how precedence disappears in postfix notation. In 2+3*4 the multiplication must be done first. Its postfix equivalent is 234*+. Someone reading from the left sees 2, 3, and 4 first, then sees the operator * and applies it to the last two numbers, that is, to 3 and 4. Then + adds 2 and 12. There is no need to know the precedence: the order of the operators is the order of application itself.
In the third row the parentheses disappear. In (a+b)*c the addition must be done first. In the postfix equivalent, + is written before *: ab+c*. In postfix notation the position of the operators takes over the function of parentheses.
The fourth row is more complex. Because b-c+d associates from left to right, it is (b−c)+d and its postfix equivalent is bc-d+. The division puts a in front of it: abc-d+/. Then it is multiplied by (e-a) (ea-*) and finally multiplied by c (c*). Because the two multiplications associate from left to right, the left one is done first.
8.3.4Converting by hand
There is a simple three-step way to convert an infix expression to postfix by hand. Table 8.5 applies these steps to the expression a / b − c + d * e − a * c.
| Step | Expression |
|---|---|
| Start | a / b − c + d * e − a * c |
| 1. Fully parenthesize | ((((a / b) − c) + (d * e)) − (a * c)) |
| 2. Move the operator to its right parenthesis | ((((a b /) c −) (d e *) +) (a c *) −) |
| 3. Delete the parentheses | a b / c − d e * + a c * − |
- Full parenthesization. According to precedence and associativity, every operation is put into its own parentheses (Example 8.1). Every operator gets exactly one pair of parentheses.
- Moving. Each operator is moved to the right closing parenthesis of its own pair. The pair
(a / b)becomes(a b /). - Deleting. The parentheses are deleted. The remaining sequence is the postfix expression:
a b / c − d e * + a c * −.
For prefix notation, in the second step the operator is moved not to the right closing parenthesis but to the left opening parenthesis of its own pair. The prefix equivalent of the same expression is − + − / a b c * d e * a c.
An important observation lies in the result of the conversion: the order of the operands does not change. In the infix expression the operands are in the order a b c d e a c; in the postfix expression they are in the same order. Only the positions of the operators change. This observation is the basis of the stack algorithm. An operand can be written directly to the output the moment it arrives. Operators, on the other hand, wait on a stack until the right moment comes, that is, until the higher-precedence operations that follow them are finished.
Skipping the full parenthesization step when converting by hand and working only with the parentheses that appear in the expression. In a / b − c there are no parentheses at all, and so no closing parenthesis to move to. All operations must first be parenthesized as ((a / b) − c). Otherwise the result turns into a random arrangement.
8.3.5Postfix to infix with a stack
The conversion in the opposite direction, that is, obtaining a fully parenthesized infix expression from a postfix expression, is a good first step for seeing how the stack works. The rule is short. The expression is read from left to right:
- If an operand arrives, it is pushed onto the stack.
- If an operator arrives, two items are popped from the stack. The first one popped is the right operand and the second is the left operand. The two are combined by putting the operator between them and enclosing the result in a pair of parentheses. The resulting string is pushed back onto the stack.
- When the expression ends, a single item remains on the stack: the fully parenthesized infix expression.
The example in the slides is the expression 42/2−33*+42*−. This is the postfix expression obtained from a / b − c + d * e − a * c by substituting a = 4, b = 2, c = 2, d = 3, e = 3. Table 8.6 gives the stack after every step.
| Token | Action | Stack |
|---|---|---|
4 | operand, onto the stack | 4 |
2 | operand, onto the stack | 4 · 2 |
/ | 2 and 4 are popped, (4/2) is pushed | (4/2) |
2 | operand, onto the stack | (4/2) · 2 |
− | ((4/2)−2) is pushed | ((4/2)−2) |
3, 3 | two operands onto the stack | ((4/2)−2) · 3 · 3 |
* | (3*3) is pushed | ((4/2)−2) · (3*3) |
+ | (((4/2)−2)+(3*3)) is pushed | (((4/2)−2)+(3*3)) |
4, 2 | two operands onto the stack | (((4/2)−2)+(3*3)) · 4 · 2 |
* | (4*2) is pushed | (((4/2)−2)+(3*3)) · (4*2) |
− | final combination | ((((4/2)−2)+(3*3))−(4*2)) |
/ has been processed and (4/2) sits at the bottom of the stack. Middle: + has been processed; there is a single string on the stack. Bottom: the last − has been processed; the only item on the stack is the result.The state of the stack at the two * steps is interesting. After the first * is processed, there are two items on the stack: ((4/2)−2) and (3*3). So cell [1] does not stay empty; (3*3) sits there and top = 1. After the second *, the same cell holds (4*2) this time. The stack never exceeds three items. In this expression the deepest moment is when the pair 3 3 or 4 2 is pushed onto the stack.
When this method is written in C, the stack holds strings rather than characters. Every combination requires allocating memory for a new string and freeing the two parts that are no longer needed. For this reason malloc and free must be used carefully. The complete code is given in the exercise solutions.
8.4Evaluating a postfix expression
Evaluating a postfix expression is the second stage of the two-stage solution, but it is the easier one to understand. Let us therefore examine it first. The rule is almost the same as the rule for converting postfix to infix. The only difference is that the stack holds numbers instead of strings.
- If an operand arrives, its value is pushed onto the stack.
- If an operator arrives, two values are popped from the stack, the operation is performed, and the result is pushed onto the stack.
- When the expression ends, the single value left on the stack is the result.
8.4.1The token: get_token
The evaluator reads the expression character by character. Each read yields a token. A token is the smallest meaningful piece of an expression: an operator, a parenthesis, an operand, or the end of the expression. In real compilers a token may consist of several characters; 123 or total is a single token. To keep things simple, these notes assume that every operand is a single-digit number. Every character is then a token.
typedef enum { lparen, rparen, plus, minus,
times, divide, mod, eos, operand } precedence;
precedence get_token(const char *expr, char *symbol, int *n) {
*symbol = expr[(*n)++];
switch (*symbol) {
case '(': return lparen;
case ')': return rparen;
case '+': return plus;
case '-': return minus;
case '/': return divide;
case '*': return times;
case '%': return mod;
case '\0': return eos;
default: return operand;
}
}The first part of the code defines an enumeration type (enum). The declaration typedef enum { … } precedence; produces nine named integer constants: lparen is 0, rparen is 1, plus is 2, …, operand is 8. These constants label the kind of token. In the rest of the code, a readable name such as plus is used instead of the character '+'. Labeling with typedef enum makes the code easier to work with: readability improves, and the compiler can warn about labels forgotten in a switch.
The function get_token takes three parameters. expr is the expression being evaluated. symbol is the address where the character read is stored; the function thus both returns the kind of the token and passes the character itself to the caller. n is the address of the position currently being read in the expression. The line *symbol = expr[(*n)++] reads the character at the position n points to and advances the position by one. The next call reads the next character. Then the switch determines the kind of the character. Operator and parenthesis characters return their own labels, '\0' returns the end of the expression (eos, end of string), and everything else returns the label operand.
The verification program had the expression "(7%3)" read token by token and obtained the kinds lparen (0), operand (8), mod (6), operand (8), rparen (1), and eos (7) in turn.
An operand is a character; to compute with it, it must be converted to a number. The way to do this is the expression symbol − '0'. In C, a character is really a small integer that holds its code. In the ASCII table the digits are arranged consecutively: the code of '0' is 48, of '1' 49, of '2' 50. Hence '2' − '0' gives 50 − 48 = 2. Subtracting '0' from a digit character gives its numeric value.
It was also possible to keep the expression in a global array named expr. This is how it is in the book by Horowitz and colleagues: the function get_token takes only two parameters and reads expr from the global variable. The version in the slides takes the expression as a parameter. This small difference is the first step of the "write it like a component" principle discussed in the next section.
8.4.2eval: the global version
The first version of the routine that evaluates a postfix expression uses a global stack and a global expression, as in the book:
float eval(void) {
char symbol; precedence token;
float op1, op2;
int n = 0, top = -1;
token = get_token(expr, &symbol, &n);
while (token != eos) {
if (token == operand)
push(&top, symbol - '0');
else {
op2 = pop(&top); /* right operand first */
op1 = pop(&top);
push(&top, apply(token, op1, op2));
}
token = get_token(expr, &symbol, &n);
}
return pop(&top); /* the one left is the result */
}The expression itself (expr) and the stack array (stack) are global; top is local and is passed to the stack functions by address. The flow of the routine is as follows:
n = 0marks the start of the expression andtop = -1the empty stack. The first token is read before the loop.- The loop runs as long as the token is not
eos. At the end of each round the next token is read. This is the pattern "read first, then process in the loop and read the next one". - If the token is an operand, its numeric value, obtained with
symbol − '0', is pushed onto the stack. - If the token is an operator, two values are popped from the stack. The first one popped is
op2, the right operand. Then the left operandop1is popped. The functionapplyperforms the operation and the result is pushed onto the stack. - When the loop ends, the single value left on the stack is returned.
The function apply separates the operator kinds with a switch:
float apply(precedence token, float op1, float op2) {
switch (token) {
case plus: return op1 + op2;
case minus: return op1 - op2;
case times: return op1 * op2;
case divide: return op1 / op2;
case mod: return (int)op1 % (int)op2;
default: return 0; /* not an operator: never reached */
}
}The order in which operands are popped is the most important detail of this routine. In a postfix expression the left operand is pushed onto the stack first and the right operand afterward. Because the stack returns the last item pushed first, the first value popped is the right operand. In the expression 6 2 −, 6 is pushed first and then 2. When − arrives, the first value popped is 2 (op2) and the second is 6 (op1). The result is op1 − op2 = 6 − 2 = 4. Had the operands been popped in the opposite order, 2 − 6 = −4 would have been obtained. For addition and multiplication the order does not change the result, but for subtraction, division, and remainder it does.
The expression (int)op1 % (int)op2 in the mod case comes from a rule of C. The stack holds float values, because the result of a division may be fractional. The % operator, however, cannot be used with float; it is defined only for integers. The two operands are therefore converted to int first. If the remainder of fractional values is needed, the function fmod of the standard library is used.
The default branch in apply is also necessary. If a switch over an enumeration type does not cover some of the labels, the compiler gives a -Wswitch warning. Here lparen, rparen, eos, and operand never reach this function; the default branch says so explicitly and silences the warning.
This routine was run in the verification program with the global expr = "42/2-33*+42*-" and returned the value 1. In the first version in the slides, get_token was called with two arguments, in the form get_token(&symbol, &n). This call does not compile against the three-parameter definition of get_token ("too few arguments"). The correct call is get_token(expr, &symbol, &n), which also passes the global expr.
8.4.3Writing it like a component
The global version works, but it has a serious design problem. The routine depends on the outside world:
/* global version: external dependencies */
char expr[] = "42/2-33*+42*-";
float stack[MAX_SIZE];
float eval(void);eval takes no parameters; it learns which expression to evaluate from the global expr and where to write from the global stack. This dependency has three consequences. First, two expressions cannot be evaluated at the same time: to evaluate the second one, the contents of expr must be changed. Second, the routine cannot be moved to another program; every program that wants to use it must define global variables of the same names. Third, the routine has side effects: while running, it changes an array that other parts of the program also use. A bug in one part of the program can show up in an entirely different place.
In the version written like a component, everything is a parameter or a local variable:
/* component: all parameters/locals */
float eval(const char *expr);
/* the stack is a local array in eval */
/* in main: */
float a = eval("23*54*+9-");
float b = eval("42/2-33*+42*-");The expression comes in as a parameter; the stack is a local array inside eval and is set up anew at every call. The same routine works anywhere, with any expression, without side effects. The two calls in main do not affect each other at all. This version is used in the code traces.
This principle holds not only for this routine but for every function one writes. Functions should be written like a component: they should take everything they need as parameters and give their result as a return value. Uses such as global variables or #define constants read from inside the function create external dependencies. In a project worked on by a team, everyone writes independent pieces like this. The code of a programmer who says "put my variables above main, that is how I work" cannot be merged with other people's code. A personal style is an obstacle to joint work.
The complete code of the component version is:
float eval(const char *expr) {
float y[MAX_SIZE], op1, op2; int top = -1;
for (int n = 0; expr[n] != '\0'; n++) {
char c = expr[n];
if (isdigit(c)) y[++top] = c - '0';
else {
op2 = y[top--]; op1 = y[top--];
switch (c) {
case '+': y[++top] = op1 + op2; break;
case '-': y[++top] = op1 - op2; break;
case '*': y[++top] = op1 * op2; break;
case '/': y[++top] = op1 / op2; break;
}
}
}
return y[top];
}The code is shorter than the global version. Instead of get_token, the for loop walks directly over the characters of the expression; the loop stops at the character '\0'. isdigit(c) (<ctype.h>) tests whether the character is a digit. The stack operations are written as array expressions rather than function calls: y[++top] = … is a push and y[top--] is a pop. The line op2 = y[top--]; op1 = y[top--]; again pops the right operand first. This time the switch is over the character itself and covers the four operators. MAX_SIZE is the size of the local stack; it must be larger than the number of operands in the expression.
8.4.4Code trace: eval("23*54*+9-")
The first example is 23*54*+9-. This is the postfix equivalent of the infix expression 2*3 + 5*4 − 9. Its value should be 6 + 20 − 9 = 17. Table 8.7 gives the contents of the stack after each character is processed.
n | c | Action | Stack | top |
|---|---|---|---|---|
| 0 | '2' | '2' − '0' = 2 onto the stack | 2 | 0 |
| 1 | '3' | 3 onto the stack | 2 · 3 | 1 |
| 2 | '*' | op2 = 3, op1 = 2 → 2 * 3 = 6 | 6 | 0 |
| 3 | '5' | 5 onto the stack | 6 · 5 | 1 |
| 4 | '4' | 4 onto the stack | 6 · 5 · 4 | 2 |
| 5 | '*' | op2 = 4, op1 = 5 → 5 * 4 = 20 | 6 · 20 | 1 |
| 6 | '+' | op2 = 20, op1 = 6 → 6 + 20 = 26 | 26 | 0 |
| 7 | '9' | 9 onto the stack | 26 · 9 | 1 |
| 8 | '-' | op2 = 9, op1 = 26 → 26 − 9 = 17 | 17 | 0 |
| 9 | '\0' | the loop ends, y[0] is returned | 17 | 0 |
eval("23*54*+9-"). In the first drawing the first * has been processed: 6 is on the stack. In the second the second * has been processed: 6 and 20 are on the stack, top = 1. In the third the expression has ended: the only value on the stack is 17.The deepest moment of the stack in the trace is n = 4: three values (6, 5, 4) are on the stack at the same time. This is the moment when the product 5*4 is waiting to be added to 2*3. In a postfix expression the stack stores the intermediate results that are waiting.
The cost is clear. Let the length of the expression be n. Each character is read once. For an operand one push is made; for an operator two pops, one operation, and one push are made. Each of these is O(1). The total time is Θ(n). In the worst case the stack holds all the operands at the same time (for example 1234+++); the extra memory is O(n).
8.4.5Code trace: eval("42/2-33*+42*-")
The second example is the postfix equivalent of the expression that introduced the expression evaluation problem: 42/2-33*+42*-. The expected value is 1. The infix equivalent of this expression was already found with the stack: ((((4/2)−2)+(3*3))−(4*2)). Now the same stack works with numbers instead of strings.
c | Action | Stack |
|---|---|---|
'4', '2' | 4 and 2 onto the stack | 4 · 2 |
'/' | op2 = 2, op1 = 4 → 4 / 2 = 2 | 2 |
'2' | 2 onto the stack | 2 · 2 |
'-' | op2 = 2, op1 = 2 → 2 − 2 = 0 | 0 |
'3', '3' | 3 and 3 onto the stack | 0 · 3 · 3 |
'*' | op2 = 3, op1 = 3 → 9 | 0 · 9 |
'+' | op2 = 9, op1 = 0 → 0 + 9 = 9 | 9 |
'4', '2' | 4 and 2 onto the stack | 9 · 4 · 2 |
'*' | op2 = 2, op1 = 4 → 8 | 9 · 8 |
'-' | op2 = 8, op1 = 9 → 9 − 8 = 1 | 1 |
eval("42/2-33*+42*-"). In the first drawing, after the first -, the stack holds 0. In the second, 3*3 has been computed and 9 sits on top of the 0. In the third, the last - has been processed and the result is 1.This trace shows why the wrong "left-to-right" result of the first comparison does not appear. When the + operator arrives, the stack holds 0 and 9; that is, the product 3*3 has been computed before the addition. It is the conversion stage that knows the precedence. The evaluator merely applies the operators in the order in which they arrive.
The verification program evaluated these two expressions and the expression 623+-382/+* from the exercise; the results are 17, 1, and 7. The program's dump of the intermediate stack is identical to every row in the tables.
8.4.6Malformed expressions
In a well-formed postfix expression, exactly one value remains on the stack at the end of the evaluation. This rule can also be used as a validity test. Keep a counter through the expression: an operand increases it by one and a binary operator decreases it by one (it takes two values and puts back one). If the expression is valid, the counter is at least 2 whenever an operator arrives and is exactly 1 at the end.
- If an operand is missing (for example
2*), there is a single value on the stack when the operator arrives. The short code in the slides executesy[top--]twice and, aftertophas dropped to −1, goes on to ready[-1]. This is a read outside the array and is undefined behavior. - If an operator is missing (for example
234+), two values remain on the stack when the expression ends. The code returns the top value and does not notice the error.
A robust routine should check top >= 0 before every pop and at the end check that top == 0. The pop function in the slides takes over this check by printing an error message on an empty stack. Division by zero must also be handled separately: with float division the result is infinity or NaN (not a number), while for the % operation computing a remainder with a zero divisor is undefined behavior.
Popping op1 and op2 in the wrong order: op1 = y[top--]; op2 = y[top--];. With this code the expression 62- gives −4 instead of 4, and 82/ gives 0.25 instead of 4. Test expressions that contain only addition and multiplication do not catch this bug; one must test with an expression that contains subtraction or division.
8.5Converting infix to postfix
The first stage of the solution is to convert the infix expression to postfix notation. As observed in the hand conversion, the order of the operands does not change; only the positions of the operators change. The algorithm uses this observation directly: operands are written to the output the moment they arrive, while operators wait their turn on a stack.
8.5.1The algorithm and isp/icp
Precedence determines when an operator is written to the output. In a + b * c, the + enters the stack and waits. When * arrives, + is still on the stack. Because * has higher precedence, it must be applied first, that is, it must be written to the output before +. So * goes on top of +. Conversely, in a * b + c, when + arrives, * is on the stack. * has higher precedence and can now be applied; before + enters the stack, * is moved to the output.
The rules of the algorithm are as follows. The expression is read from left to right.
- An operand is written directly to the output.
- When an operator arrives, as long as the precedence of the operator on top of the stack is greater than or equal to that of the incoming operator, the top operator is moved to the output. Then the incoming operator is pushed. Moving it to the output on equality as well ensures left-to-right associativity.
- A left parenthesis
(always enters the stack. While on the stack it behaves like the operator with the lowest precedence; every operator can go on top of it. - When a right parenthesis
)arrives, the operators on the stack are moved to the output until a(is seen. Then the(is discarded from the stack. Parentheses are never written to the output. - When the expression ends, all the operators left on the stack are moved to the output.
The two different behaviors of the left parenthesis cannot be expressed with a single precedence value. On arrival it must pop no operator from the stack; this means the highest precedence. While on the stack, every operator must be able to go on top of it; this means the lowest precedence. The solution is to give every operator two precedences.
The in-stack precedence (isp) is the precedence an operator carries while waiting on the stack. The incoming precedence (icp) is its precedence at the moment it is read from the input. For an incoming operator x, the operator t on top of the stack is moved to the output as long as isp(t) ≥ icp(x).
| Token | isp (in the stack) | icp (incoming) |
|---|---|---|
( | 0 | 20 |
* / % | 13 | 13 |
+ − | 12 | 12 |
# (bottom marker) | −1 | — |
The numbers in the table themselves do not matter; only the order among them does. Horowitz and colleagues use values such as 12 and 13 to conform to C's full precedence table. The incoming precedence of ( is 20 and no isp value reaches 20; therefore nothing comes off the stack when ( arrives. Its in-stack precedence is 0 and the incoming precedence of every operator is greater than 0; therefore every operator goes on top of (. At the same time no operator can pop ( from the stack, because 0 ≥ 12 is never true. Only ) removes (.
The # at the bottom of the stack is a sentinel. Its in-stack precedence is −1; it is never greater than or equal to the incoming precedence of any operator. The loop "move the top operator to the output" therefore stops by itself when it reaches #. There is thus no need to check separately in the loop condition whether the stack is empty. It is the same idea as the wall frame around the maze.
In the verification program the precedences were defined with the following two small functions:
int isp(char c) { /* in-stack precedence */
switch (c) {
case '(': return 0;
case '*': case '/': case '%': return 13;
case '+': case '-': return 12;
default: return -1; /* '#': stack bottom */
}
}
int icp(char c) { /* incoming precedence */
if (c == '(') return 20;
return isp(c);
}8.5.2The postfix routine
void postfix(const char *e, char *out) {
char y[MAX] = {'#'}; int top = 0, k = 0;
for (; *e; e++) {
if (isalnum(*e)) out[k++] = *e;
else if (*e == ')') {
while (y[top] != '(')
out[k++] = y[top--];
top--; /* drop '(' */
} else {
while (isp(y[top]) >= icp(*e))
out[k++] = y[top--];
y[++top] = *e;
}
}
while (top > 0) out[k++] = y[top--];
out[k] = '\0';
}yis the operator stack. The declarationchar y[MAX] = {'#'}writes#into the first cell (the other cells are zeroed).top = 0points to the bottom marker; that is, the stack is logically empty but there is a sentinel at the bottom.kis the position in the output string where the next character will be written.- The loop
for (; *e; e++)advances the pointer to the end of the expression, to'\0'. Because the parametereis a copy, advancing it does not affect the caller's string. isalnum(*e)tests for a letter or digit. An operand is written directly toout.- If
)arrives, the inner loop moves operators to the output until the top of the stack is(. Thentop--discards the(; it is not written to the output. - For every other character (the four operators,
%, and(), the loop "take while greater or equal" runs. Then the incoming character is pushed onto the stack. For(the loop never runs, because icp('(') = 20. - After the loop, as long as
top > 0, that is, until the#at the bottom is reached, the remaining operators are moved to the output. Finally the output string is closed with'\0'.
The function writes its result into the out array supplied by the caller. The caller must allocate this array large enough. Because a postfix expression contains no parentheses, it is never longer than the infix expression; space for the length of the expression plus '\0' is enough.
8.5.3Code trace: a*(b+c)-d
Let us run the routine on a*(b+c)-d. The # is always at the bottom of the stack; it is not shown in the table or the figures.
| Token | Decision | Stack | top | Output |
|---|---|---|---|---|
a | operand → output | (empty) | 0 | a |
* | isp(#) = −1 < icp(*) = 13 → push | * | 1 | a |
( | isp(*) = 13 < icp(() = 20 → push | * ( | 2 | a |
b | operand → output | * ( | 2 | ab |
+ | isp(() = 0 < icp(+) = 12 → push | * ( + | 3 | ab |
c | operand → output | * ( + | 3 | abc |
) | pop up to (: + to the output, ( discarded | * | 1 | abc+ |
- | isp(*) = 13 ≥ icp(−) = 12 → * to the output; isp(#) < 12 → push - | − | 1 | abc+* |
d | operand → output | − | 1 | abc+*d |
| end | remaining - to the output | (empty) | 0 | abc+*d− |
a*(b+c)-d. In the first drawing + has gone on top of the ( on the stack. In the second, - has arrived, moved *, whose precedence is equal or higher, to the output, and entered the stack itself. In the third, the input has ended and the result is abc+*d-.The key moment of the trace is ). The operation b+c inside the parentheses cannot be completed until the closing parenthesis arrives; + therefore waits on the stack. When ) arrives, + is moved to the output. The contents of the parentheses thus pass to the output so as to be applied before the outer *. The result is abc+*d-. This expression reads "first b+c, then multiply by a, then subtract d".
8.5.4Equal precedence: a*(b+c)*d
The second example differs by a single character: * instead of -. The trace is the same up to ). The difference shows when the second * arrives. The first * is on top of the stack and isp(*) = 13 ≥ icp(*) = 13. Equality is also enough to move it to the output. The first * is moved to the output and the second * enters the stack. The result is abc+*d*.
* arrives in the conversion of a*(b+c)*d: the first *, of equal precedence, has been moved to the output and the second * has entered the stack.Moving to the output on equality means left-to-right associativity. The expression a*(b+c)*d means (a*(b+c))*d: the left multiplication is done first. If the left multiplication is written to the output first, it is applied first in the postfix expression too. Because multiplication is associative, the result does not change here, but for subtraction it does. With the correct rule, a-b-c is converted to ab-c-, that is, (a−b)−c. Code that does not move on equality (one that uses >) produces abc--. This means a−(b−c). For a = 9, b = 5, c = 2, the correct result is 2 and the result of the wrong code is 6. The verification program ran both versions and found these two values.
Writing the comparison as isp(y[top]) > icp(*e). The code gives the right result on most test expressions; it goes wrong only on consecutive operators of equal precedence. The bug can therefore go unnoticed for a long time. Expressions such as a-b-c and a/b/c must always be tested.
8.5.5Trace table: a+b*c
The last example in the slides is a+b*c. Table 8.11 follows the format in the book by Horowitz and colleagues: the stack cells [0] and [1] are separate columns and the bottom marker is not counted. The top values in the table are therefore one less than the variable in the code: in the code # sits in cell y[0] and + is written to y[1].
| Token | [0] | [1] | top | Output |
|---|---|---|---|---|
a | −1 | a | ||
+ | + | 0 | a | |
b | + | 0 | ab | |
* | + | * | 1 | ab |
c | + | * | 1 | abc |
| end | −1 | abc*+ |
When * arrives, + is on top of the stack. Because isp(+) = 12 < icp(*) = 13, + is not moved to the output; * goes on top of it. When the input ends, the stack is emptied from the top: first * comes out, then +. The operator with higher precedence is applied first.
A frequently asked question about this table is: "Isn't the last operand c printed to the output?" It is. The postfix routine writes operands to the output the moment they arrive; c has also gone to the output before the last row. At the end only the operators waiting on the stack are emptied.
8.5.6Cost
Let the length of the expression be n. The outer loop processes each character once. At first glance the inner loops seem to make the cost quadratic: a single ) or a single operator can move many items from the stack to the output. But each operator enters the stack at most once and leaves it at most once. The total number of rounds of all the inner loops therefore cannot exceed the number of operators that entered the stack, that is, it is less than n. This kind of counting is called aggregate analysis: the total cost of all steps is computed, not that of a single step. The total time is Θ(n). The stack and the output array use O(n) extra memory.
Conversion and evaluation together are also linear: first the postfix expression is produced in Θ(n) and then evaluated in Θ(n). When parsing an expression, compilers usually merge these two steps or build an expression tree instead of a postfix expression, but the basic idea is the same.
8.6Prefix notation
Prefix notation is the mirror image of postfix notation. The operator comes before its operands. The methods of conversion and evaluation are also similar to those for postfix; the difference lies in the direction from which the expression is read.
8.6.1Infix to prefix
An easy way to convert an infix expression to prefix is to use the postfix algorithm we already have. The method consists of four steps. Table 8.12 applies the steps to the expression (a+b)*c-d/a.
| Step | Expression |
|---|---|
| Start | (a+b)*c-d/a |
| 1. Reverse | a/d-c*)b+a( |
2. Swap ( and ) | a/d-c*(b+a) |
| 3. Convert to postfix (do not pop on equality) | ad/cba+*- |
| 4. Reverse again | -*+abc/da |
The logic of the method is this. When the expression is reversed, the operand on the left of each operator moves to the right and the one on the right moves to the left. When the postfix of the reversed expression is found, the operator is written after its operands. When the result is reversed again, the operator goes in front of its operands and the operands return to their original order. Reversal also flips the parentheses: (a+b) becomes )b+a(. This is why the parentheses are swapped in the second step.
There is an important change in the third step: on equal precedence nothing is popped from the stack; the comparison is made with >. In the reversed expression the associativity is reversed as well. a-b-c, that is, (a−b)−c, becomes c-b-a when reversed. For this expression to convert to the correct prefix, the left - must stay on the stack and the right - must go on top of it. With this rule the verification program found --abc for a-b-c, that is, −(−(a, b), c); this is the correct prefix equivalent.
The C code of the method can be written as follows (it uses the same isp/icp functions):
/* infix -> prefix: reverse, swap parentheses,
convert to postfix without popping on equality (>), reverse again */
void prefix(const char *e, char *out) {
char t[MAX], y[MAX] = {'#'};
int n = strlen(e), top = 0, k = 0;
for (int i = 0; i < n; i++) { /* reverse */
char c = e[n - 1 - i];
t[i] = c == '(' ? ')' : c == ')' ? '(' : c;
}
t[n] = '\0';
for (char *p = t; *p; p++) {
if (isalnum(*p)) out[k++] = *p;
else if (*p == ')') {
while (y[top] != '(') out[k++] = y[top--];
top--;
} else {
while (isp(y[top]) > icp(*p)) /* > : no pop on equal */
out[k++] = y[top--];
y[++top] = *p;
}
}
while (top > 0) out[k++] = y[top--];
out[k] = '\0';
for (int i = 0, j = k - 1; i < j; i++, j--) { /* reverse again */
char tmp = out[i]; out[i] = out[j]; out[j] = tmp;
}
}The result is the same as the third row of Table 8.4. The function produced the prefix equivalent in the table for all four expressions. The reversals, the stack operations, and the conversion apply a constant number of operations to each character of the expression; the total time is Θ(n).
There is also a direct way. The expression is scanned from right to left. Operands are added to the front of the output; operators are handled with the same stack rule, again without popping on equality. The role of the parentheses is also swapped: when reading from right to left, ) is seen first and enters the stack, and when ( is seen, the stack is emptied. Both ways are O(n).
8.6.2Evaluating a prefix expression
A prefix expression is evaluated by reading it from right to left, with the same stack technique as postfix evaluation:
float prefix_eval(const char *e) {
float y[MAX], op1, op2; int top = -1;
for (int i = strlen(e) - 1; i >= 0; i--) {
if (isdigit(e[i])) y[++top] = e[i] - '0';
else {
op1 = y[top--]; op2 = y[top--];
y[++top] = apply(e[i], op1, op2);
}
}
return y[top];
}i starts at the last character and decreases to 0. A digit is pushed onto the stack. When an operator arrives, two values are popped and the function apply performs the operation. This function separates the four operators with a switch:
float apply(char op, float op1, float op2) {
switch (op) {
case '+': return op1 + op2;
case '-': return op1 - op2;
case '*': return op1 * op2;
case '/': return op1 / op2;
default: return 0;
}
}The crucial difference in the code is the order of popping. In a prefix expression, the left operand is written first and the right operand after it, immediately to the right of an operator. Reading from right to left, the right operand is seen first and pushed first. The left operand is pushed afterward and stays on top. Therefore the first value popped is the left operand: op1 = y[top--]; op2 = y[top--];. In postfix evaluation, the first value popped was the right operand.
The expression strlen(e) - 1 contains a detail about types. strlen returns the unsigned size_t. On an empty string, 0 - 1 turns into a very large number in unsigned arithmetic. Because the code assigns this result to int i, in practice −1 is obtained and the loop never runs. Had the loop variable been made size_t, the condition i >= 0 would always be true and the loop would run forever.
The example in the slides is -+*23*549. This is the prefix equivalent of the expression 2*3+5*4−9; its value should be 17, as in the postfix example.
i | e[i] | Action | Stack |
|---|---|---|---|
| 8 | 9 | onto the stack | 9 |
| 7 | 4 | onto the stack | 9 · 4 |
| 6 | 5 | onto the stack | 9 · 4 · 5 |
| 5 | * | op1 = 5 (left), op2 = 4 → 20 | 9 · 20 |
| 4 | 3 | onto the stack | 9 · 20 · 3 |
| 3 | 2 | onto the stack | 9 · 20 · 3 · 2 |
| 2 | * | op1 = 2, op2 = 3 → 6 | 9 · 20 · 6 |
| 1 | + | op1 = 6, op2 = 20 → 26 | 9 · 26 |
| 0 | - | op1 = 26, op2 = 9 → 26 − 9 = 17 | 17 |
*: the first value popped, 5, is the left operand, and the result is 20. In the second, +: 6 + 20 = 26. In the third, -: 26 − 9 = 17.In the last step the popping order decides the result. On the stack 9 is at the bottom and 26 on top. The first value popped, 26, is the left operand and the result is 26 − 9 = 17. Had the postfix rule been applied here, 9 − 26 = −17 would have been obtained. The verification program found 4 for -62 and (6 − 2) · 3 = 12 for *-623.
8.6.3The other conversions
The three notations and evaluation form a four-cornered diagram. Figure 8.11 gives this diagram. Green arrows show the routes whose code is given in these notes, and red question marks show the conversions that remain to be designed.
All the remaining conversions can be designed with the same stack idea:
- Postfix to infix: writing the hand conversion in C. The stack holds strings; the solution is given in the exercises.
- Postfix to prefix: the same as postfix to infix, only the combination is made in the form
op a b. Prefix to postfix: the expression is read from right to left and the combination has the forma b op. - Infix to prefix directly: the expression is scanned from right to left (described in the previous section).
- Prefix to infix: read from right to left; the first value popped is the left operand, and the combination has the form
(a op b). - Evaluating an infix expression directly: two stacks are used, one for operands and one for operators. At the moment the conversion algorithm would write an operator to the output, that operator instead pops two values from the operand stack and pushes the result back. The value is thus computed directly without ever producing a postfix expression.
8.7Parenthesis checking
The conversion from infix to postfix assumes that the parentheses in the expression are correctly formed. This assumption can be checked with a separate algorithm. Parenthesis checking (balanced parentheses) tests that every opening parenthesis is closed with the right type and in the right order. The problem is one of the cleanest applications of the stack.
The parentheses in a string are balanced if the following three conditions hold: every closing parenthesis has a partner that was opened before it and has not yet been closed; this partner is the most recently opened of the unclosed openers and is of the same type as the closer ((), [], {}); and when the string ends, no unclosed opener remains.
The phrase "most recently opened" in the middle of the definition points to the stack. In the string {a*(b+c)-[d]}, the ( was opened after the { and must be closed before it. If the openers are put on a stack, when a closer arrives its partner is always on top of the stack.
8.7.1The balanced routine
bool balanced(const char *e) {
char y[MAX]; int top = -1;
for (; *e; e++) {
if (*e=='(' || *e=='[' || *e=='{')
y[++top] = *e;
else if (*e==')' || *e==']' || *e=='}') {
if (top < 0 || !matches(y[top], *e))
return false; /* extra/wrong */
top--;
}
}
return top == -1; /* none left open? */
}- If an opening parenthesis (
(,[,{) arrives, it is pushed onto the stack. - If a closing parenthesis arrives, two cases are checked. If the stack is empty (
top < 0), this closer has no partner: an extra closer. If the stack is not empty, the code checks whether the opener on top matches the closer. If it does not, the types are mixed up: a wrong match. In both cases the function returnsfalseat once. If they match, the opener is removed from the stack (top--). - Characters that are not parentheses are skipped.
- If the stack is empty when the string ends (
top == -1), every opener has been closed and the result istrue. If it is not empty, there are unclosed openers.
The expression top < 0 || !matches(y[top], *e) in the condition relies on short-circuit evaluation. The || operator evaluates its left side first; if the left side is true, it does not look at the right side at all. When the stack is empty, y[top], that is, y[-1], is not read. Had the conditions been written in the opposite order, an empty stack would cause a read outside the array. The function matches is not given in the slides; in the verification program it was written as follows:
bool matches(char opener, char closer) {
return (opener == '(' && closer == ')') ||
(opener == '[' && closer == ']') ||
(opener == '{' && closer == '}');
}8.7.2Code trace: {a*(b+c)-[d]}
| Character | Action | Stack | top |
|---|---|---|---|
{ | opener → push | { | 0 |
a, * | skipped | { | 0 |
( | opener → push | { ( | 1 |
b, +, c | skipped | { ( | 1 |
) | matches the ( on top → pop | { | 0 |
- | skipped | { | 0 |
[ | opener → push | { [ | 1 |
d | skipped | { [ | 1 |
] | matches the [ on top → pop | { | 0 |
} | matches the { on top → pop | (empty) | −1 |
| end | top == -1 → true | (empty) | −1 |
{ and ( are on the stack. In the second, the ( has been closed and [ has been opened. In the third, the input has ended and the stack is empty: the string is balanced.The stack held at most two openers. This is the depth of nesting: ( and [ are each inside { but independent of each other.
8.7.3Three kinds of errors
An unbalanced string shows up in three different ways. Table 8.15 gives an example of each kind; all three examples gave false in the verification program.
| Input | What happens? | Error |
|---|---|---|
[(a+b]*c) | When ] arrives, ( is on top | Wrong match |
(a+b)) | When the second ) arrives, the stack is empty | Extra closer |
((a+b) | When the input ends, ( is left on the stack | Unclosed opener |
For a single kind of parenthesis no stack is needed; a counter is enough. At an opener the counter increases by one and at a closer it decreases by one. If the counter never goes below zero and is zero at the end, the string is balanced. With several kinds of parentheses a counter is not enough. In the string [(a+b]*c) the numbers of openers and closers are equal, but the types are crossed. To catch this, one must answer the question "which was the most recently opened?" The stack holds this information.
This algorithm runs inside a great deal of software. Compilers check the parentheses and braces in source code this way. HTML and XML validators match opening and closing tags by the same method; there, tag names rather than parentheses are pushed onto the stack. A text editor highlighting the partner of a parenthesis when the cursor is on it is also an application of this algorithm.
Cost: if the length of the string is n, each character is examined once and each operation is O(1); the time is O(n). In the worst case all the characters are openers and all enter the stack; the extra memory is O(n). If an error is found early, the function returns without reaching the end of the string.
8.8Other applications of stacks and queues
The maze, expression evaluation, and parenthesis checking share a common idea: "the last one opened is the first one closed". Wherever this idea is seen, a stack can be used. Wherever "in order", that is, "first come, first processed", is seen, a queue is used. This section briefly introduces a few other applications of this principle.
8.8.1Undo and redo
The undo and redo commands in text editors work with two stacks. When the user performs an operation, the operation is pushed onto the "undo" stack and the "redo" stack is emptied. The undo command takes the operation on top of the "undo" stack, applies its inverse, and puts it onto the "redo" stack. The redo command takes the operation on top of the "redo" stack, applies it again, and puts it onto the "undo" stack.
For example, let the user perform the operations A, B, and C in turn. The "undo" stack is A · B · C. If undo is performed twice, first C and then B are undone. A remains on the "undo" stack and C · B on the "redo" stack, with B on top. If redo is performed once, B is applied again. If at this moment the user performs a new operation D, the C on the "redo" stack is deleted. A new branch has started and the old future cannot be returned to. The back and forward buttons of web browsers also work with the same two stacks.
8.8.2Non-recursive tree traversal
Visiting the nodes of a binary tree in some order is called traversal. Traversal is naturally written recursively: in inorder traversal, the left subtree is traversed first, then the root is visited, then the right subtree is traversed. Recursion stores the pending work on the call stack. The same job can also be done with an explicit stack; this removes the overhead of recursive calls and puts the size of the stack under the programmer's control.
The following node type is used for the code: each node carries a character and two subtree pointers.
typedef struct node *tree_pointer;
typedef struct node {
char data;
tree_pointer left, right;
} node;
void inorder(tree_pointer p) { /* non-recursive */
tree_pointer y[MAX]; int top = -1;
for (;;) {
for (; p; p = p->left) y[++top] = p; /* push while going left */
if (top < 0) break; /* stack empty: done */
p = y[top--];
printf("%c", p->data);
p = p->right; /* move to right subtree */
}
}
void preorder(tree_pointer p) { /* non-recursive */
tree_pointer y[MAX]; int top = -1;
if (p == NULL) return;
y[++top] = p;
while (top >= 0) {
p = y[top--];
printf("%c", p->data);
if (p->right) y[++top] = p->right; /* push right first, */
if (p->left) y[++top] = p->left; /* left stays on top */
}
}
void postorder(tree_pointer p) { /* with two stacks */
tree_pointer y1[MAX], y2[MAX]; int t1 = -1, t2 = -1;
if (p == NULL) return;
y1[++t1] = p;
while (t1 >= 0) {
p = y1[t1--];
y2[++t2] = p; /* order: root, right, left */
if (p->left) y1[++t1] = p->left;
if (p->right) y1[++t1] = p->right;
}
while (t2 >= 0) printf("%c", y2[t2--]->data); /* reversed: left, right, root */
}The function inorder performs inorder traversal. The inner for loop starts at p, descends by following left links, and pushes every node it passes onto the stack. When the left end is reached, the node on top of the stack is popped, printed, and the traversal moves to its right subtree. The traversal ends when the stack is empty and p is NULL. At every moment the stack holds the nodes on the path from the root to the current node whose right side has not yet been visited. The size of the stack therefore does not exceed the height of the tree.
preorder is simpler. The root is pushed onto the stack. In each round the node on top is popped and printed; then its right child and after it its left child are pushed. Because the left child stays on top, it is processed first. postorder is written with two stacks. The first stack transfers the nodes to the second in the order "root, right, left". When the second stack is emptied in reverse, the order "left, right, root" is obtained, that is, postorder traversal.
The verification program built the tree of the expression (a+b)*c-d/a: root -, left subtree (a+b)*c, right subtree d/a. The three traversals gave the outputs a+b*c-d/a (infix without parentheses), -*+abc/da (prefix), and ab+c*da/- (postfix) in turn. The three traversals of an expression tree are the three notations of the expression. Every one of the 9 malloc calls made to build and release the tree was matched by a free.
Cost: in a tree of n nodes, each node enters the stack once and leaves once; the time is O(n). In inorder and preorder traversal the stack holds at most as many nodes as the height of the tree, h (the exact bound for preorder is of the order of h + 1); the extra memory is O(h). In a balanced tree h = O(log n), and in a tree degenerated into a single branch h = n − 1. In postorder traversal with two stacks, the extra memory is O(n) because the second stack holds all the nodes. Level-order traversal, which processes the tree level by level, is done with a queue: the root is put into the queue, in each step a node is taken from the front, and its children are added at the rear.
8.8.3Next greater element
Suppose that for each element of an array we want to find the first greater element to its right. Two nested loops do this in O(n2). A stack does the same job in one pass:
/* first greater element to the right of each item; -1 if none */
void next_greater(const int a[], int n, int result[]) {
int y[MAX], top = -1; /* indices on the stack */
for (int i = 0; i < n; i++) {
while (top >= 0 && a[y[top]] < a[i])
result[y[top--]] = a[i]; /* a[i] answers the waiting item */
y[++top] = i;
}
while (top >= 0) result[y[top--]] = -1; /* nothing greater to the right */
}The stack holds the indices of the items that have not yet found their answer. The values of these items are in decreasing order from bottom to top; this is why the structure is called a monotonic stack. When a new item a[i] arrives, as long as the waiting item on top is smaller than it, a[i] is the answer for that item and the item is popped. Then i is pushed. When the array ends, the items remaining on the stack have no greater item to their right; their answers are −1.
For the array {4, 5, 2, 25, 7, 3, 8} the verification program gave the result 5 25 25 −1 8 8 −1. For example, when 25 arrives, the indices of 5 and 2 are on the stack; both are smaller than 25, and the answer for both is 25. Because every index enters the stack once and leaves once, the total time is O(n); the extra memory is O(n) in the worst case (a decreasing array).
8.8.4Sliding window maximum
Let a window of width k be slid from left to right over an array of n items, and let the largest item in the window be wanted at every position. Scanning each window separately takes O(n · k). A double-ended queue (deque), that is, a queue in which items can be inserted and removed at both ends, brings this down to O(n):
/* maximum of each window of width k; d: deque holding indices */
void sliding_max(const int a[], int n, int k, int result[]) {
int d[MAX], front = 0, rear = -1; /* d[front..rear] */
for (int i = 0; i < n; i++) {
if (front <= rear && d[front] <= i - k) front++; /* left the window */
while (front <= rear && a[d[rear]] <= a[i]) rear--; /* drop smaller ones */
d[++rear] = i;
if (i >= k - 1) result[i - k + 1] = a[d[front]]; /* maximum at front */
}
}The deque holds indices, and their values are in decreasing order from front to rear. When a new item arrives, first the index that has fallen out of the window is dropped from the front. Then every index whose value is not greater than the new item is dropped from the rear: those items can never be the maximum as long as the new item stays in the window. The new index is added at the rear. The maximum of the window is always at the front. For the array {1, 3, −1, −3, 5, 3, 6, 7} and k = 3, the result is 3 3 5 5 6 7. Each index is added once and dropped at most once; the time is O(n) and the extra memory is O(k).
8.8.5Shortest paths with a queue and other backtracking problems
If a queue is used instead of the stack in the maze, the first path found is the shortest. This is the basic property of breadth-first search, and beyond the maze it holds in every network in which the steps cost the same. A game character reaching its goal in the fewest moves, or the shortest chain of acquaintances between two people in a social network, is found by the same method.
The other classic examples of backtracking are also solved with a stack, or with recursion. The Towers of Hanoi problem keeps the pending subproblems on a stack while moving disks from one peg to another. The n-queens problem places n queens on a chessboard so that none threatens another. One queen is placed in each row; if a dead end is reached, the last queen placed is removed and the next column is tried. A Sudoku solver tries digits in the empty cells in turn and undoes the last attempt when a contradiction appears. All three carry the skeleton of the maze routine: a choice is pushed onto the stack and popped at a dead end. These problems are usually written recursively, but they can also be written with an explicit stack as in the maze.
8.9Complexity summary
Table 8.16 gives the costs of the algorithms in these notes together. The justification of each row was explained in the relevant section.
| Algorithm | Structure | Time | Extra memory |
|---|---|---|---|
Maze (path) | stack | O(m · p) | O(m · p) |
| Maze shortest path | queue | O(m · p) | O(m · p) |
| Postfix / prefix evaluation | stack | O(n) | O(n) |
| Infix to postfix / prefix | stack | O(n) | O(n) |
| Parenthesis checking | stack | O(n) | O(n) |
| Non-recursive inorder | stack | O(n) | O(h) |
| Level-order traversal | queue | O(n) | O(n) |
| Next greater element | stack | O(n) | O(n) |
| Sliding window maximum | deque | O(n) | O(k) |
All the linear times in the table rest on the same justification: each item enters the structure at most once and leaves at most once, and every entry and exit is O(1). Nested loops do not break this bound, because the total number of rounds of the inner loops is limited by the number of items removed. This counting method is the tool used most often in analyzing stack and queue algorithms.
8.10Common mistakes
- Popping
op1andop2in the wrong order in postfix evaluation. The first one popped is the right operand. If they are popped the other way round,6 2 −gives −4 instead of 4. - Using the postfix order in prefix evaluation. A prefix expression is read from right to left and the first one popped is the left operand.
- Not popping from the stack on equal precedence in the infix-to-postfix conversion. Code that compares with
>convertsa−b−ctoabc−−, that is, toa−(b−c). - Leaving
(on the stack or writing it to the output when)arrives. If(is not discarded, it stays on the stack and blocks the operators that follow; when the stack is emptied at the end, it also slips into the output. - Forgetting the
markin the maze. The algorithm goes back and forth between two cells, falls into an infinite loop, or overflows the stack. - Not surrounding the maze with 1s. The neighbors of cells on the edge fall outside the array; C does not check this and undefined behavior results.
- Reading the top item in parenthesis checking without checking whether the stack is empty. In
(a+b)), the second)readsy[-1]on an empty stack. - Not checking for stack overflow. In an array-based stack of fixed size, if
MAXis exceeded, items are written outside the array. Either the size must be chosen safely for the input or a check must be made at every push.
8.11Exercises and solutions
The solutions to the six exercises in the slides are given in detail below. All the code was compiled and run in the verification programs.
8.11.1Converting an expression to postfix and prefix
The expression is a/(b-c)+d*(e-a)*c. Let us first convert by hand. The fully parenthesized form is ((a/(b−c)) + ((d*(e−a))*c)). Division and the two multiplications take precedence over addition; the two multiplications associate from left to right.
- Postfix: every operator is moved to its right closing parenthesis.
(b−c)→bc-,a/…→abc-/,(e−a)→ea-,d*…→dea-*,…*c→dea-*c*. Total:abc-/dea-*c*+. - Prefix: every operator is moved to its left opening parenthesis. The result is
+/a-bc**d-eac.
The same result is also found with the postfix routine. In brief: a to the output; / onto the stack; ( onto the stack; b, c to the output; - on top of (; when ) arrives, - to the output. When + arrives, because isp(/) = 13 ≥ 12, / goes to the output and + onto the stack. d to the output; * goes on top of +. (e-a) produces ea- in the same way. When the second * arrives, the first *, of equal precedence, is moved to the output. After c the input ends; the * and + on the stack pass to the output in turn. The postfix and prefix functions of the verification program also gave the results abc-/dea-*c*+ and +/a-bc**d-eac.
8.11.2Evaluating a postfix expression
The expression is 6 2 3 + − 3 8 2 / + *. The stack changes from left to right as follows: 6; 6 · 2; 6 · 2 · 3; + → 2 + 3 = 5, stack 6 · 5; − → 6 − 5 = 1, stack 1; 1 · 3; 1 · 3 · 8; 1 · 3 · 8 · 2; / → 8 / 2 = 4, stack 1 · 3 · 4; + → 3 + 4 = 7, stack 1 · 7; * → 1 · 7 = 7. The result is 7. The stack held at most four values. eval("623+-382/+*") also returned 7.
8.11.3A C routine that converts postfix to infix
The stack now holds dynamically allocated strings instead of characters. The method is the same as the hand conversion from postfix to infix.
/* postfix -> fully parenthesized infix; the stack holds dynamic strings */
char *postfix_infix(const char *e) {
char *y[MAX]; int top = -1;
for (; *e; e++) {
if (isalnum((unsigned char)*e)) {
char *s = malloc(2);
if (s == NULL) return NULL;
s[0] = *e; s[1] = '\0';
y[++top] = s;
} else {
char *b = y[top--], *a = y[top--]; /* right operand first */
char *s = malloc(strlen(a) + strlen(b) + 4);
if (s == NULL) return NULL;
sprintf(s, "(%s%c%s)", a, *e, b);
free(a); free(b); /* parts no longer needed */
y[++top] = s;
}
}
return y[top]; /* the caller must free it */
}- When an operand arrives, a two-byte string is allocated: the character itself and
'\0'. The address of the string is pushed onto the stack. - When an operator arrives, two strings are popped; the first one popped,
b, is the right operand. The size of the new string is the length of the two parts plus four bytes: two parentheses, the operator, and'\0'.sprintfjoins the parts in the form"(a op b)". - After the parts have been copied into the new string they are no longer needed and are released with
free. If this line is forgotten, two blocks leak at every operator. - The return value is the last string on the stack. Releasing this string is the caller's job.
The verification program converted four expressions. For 42/2-33*+42*- it produced ((((4/2)-2)+(3*3))-(4*2)), and for ab+c*da/- it produced (((a+b)*c)-(d/a)). With wrapper functions that count malloc and free calls, 44 allocations and 44 releases were counted; there is no leak. The code also has a gap: if malloc fails, the function returns NULL but does not release the strings left on the stack. A robust version must empty the stack before returning. In terms of cost, each combination copies two parts; as the strings grow longer, the copying grows longer. In an expression of length n, the total copying is O(n2) in the worst case (for example, in a left-leaning chain such as ab+c+d+…, every step copies the whole earlier string).
8.11.4Marking the path found in the maze
When the exit is found, the path consists of the positions on the stack, the last position, and the exit. Writing 2 into these cells makes the path visible in the maze:
/* called after path finds the exit: marks the path in the maze with 2 */
void mark_path(int top, short int row, short int col) {
for (int i = 0; i <= top; i++)
maze[stack[i].row][stack[i].col] = 2;
maze[row][col] = 2; /* last position */
maze[EXIT_ROW][EXIT_COL] = 2; /* exit */
}It is called at the end of path with the line if (found) mark_path(top, row, col);. The function does not change the stack; it only reads it. The rows of the maze then look as follows (1 wall, 0 unvisited path, 2 path found):
11111111
12100011
12101111
11211111
12112111
11221211
11111121
11111111The cells (1,3), (1,4), (1,5), and (2,3) in the dead-end corridor stay 0: they were visited but did not enter the path. Marking takes O(top) time, that is, time proportional to the length of the path.
8.11.5Finding the shortest path in the maze with a queue
The (row, col) pairs of the cells are put into the queue. For every cell, the cell from which it was reached is stored in the prev matrix. When the exit is reached, this information is followed backward to build the path.
/* shortest path in the maze: queue + the cell each cell was reached from */
typedef struct { short int row, col; } cell;
int shortest_path(void) {
cell q[64], prev[8][8]; /* 6x6 interior: at most 36 cells */
int head = 0, tail = 0;
short int seen[8][8] = {{0}};
q[tail++] = (cell){1, 1}; seen[1][1] = 1;
while (head < tail) {
cell h = q[head++]; /* take from the front */
if (h.row == EXIT_ROW && h.col == EXIT_COL) {
int len = 1; /* trace back from the exit */
while (h.row != 1 || h.col != 1) {
maze[h.row][h.col] = 2; /* mark the path */
h = prev[h.row][h.col];
len++;
}
maze[1][1] = 2;
return len;
}
for (int dir = 0; dir < 8; dir++) {
int s = h.row + move[dir].vert;
int t = h.col + move[dir].horiz;
if (!maze[s][t] && !seen[s][t]) {
seen[s][t] = 1;
prev[s][t] = h;
q[tail++] = (cell){s, t}; /* add at the rear */
}
}
}
return 0; /* no path */
}- The queue is a simple array:
headis the position to take from at the front andtailthe position to write to at the rear. Because each cell enters the queue at most once, a circular structure is not needed; an array with as many places as the interior has cells is enough. - A cell is marked (
seen) when it enters the queue, not when it leaves. In this way the same cell cannot enter the queue twice from two different neighbors. - If the cell taken from the front is the exit, the
prevchain is followed back to the entrance. At every step the cell is marked with2and the path length grows by one.
In the verification program the function found the 9-cell path and marked the maze in the same way as the search with a stack; in this maze the shortest path is unique. At most 13 cells enter the queue. The time is O(m · p) and the extra memory (prev, seen, the queue) is O(m · p).
8.11.6Non-recursive preorder and postorder traversal
The solution consists of the functions preorder and postorder in the section on non-recursive tree traversal. In preorder traversal the root is pushed onto the stack; in each round the node on top is popped and printed, and its right and then left child are pushed onto the stack. Postorder traversal is done with two stacks: the first stack produces the order "root, right, left" and the second stack reverses this order. It can also be written with a single stack; in that case, for each node a visit flag that says whether its right subtree has been traversed, or the address of the last node printed, is kept.
8.12Summary
- The stack works by the last-in-first-out rule. In the array implementation, push is
y[++top] = xand pop isy[top--]; both are O(1). - Backtracking: in the maze, every fork is pushed onto the stack; at a dead end an item is popped from the stack and the search returns to the last fork. The direction field in the record makes sure that directions already tried are skipped on a return. The wall frame around the maze removes the boundary check, and the
markmatrix prevents infinite loops. - The worst case is a long and wrong first path: the entire region except the correct path is explored.
pathuses O(m · p) time and memory; the path it finds is not necessarily the shortest. Breadth-first search with a queue guarantees the shortest path. - Notations: infix notation needs precedence and parentheses; prefix and postfix expressions are evaluated without parentheses and without precedence. The order of the operands is the same in all three notations.
- Postfix evaluation: an operand is pushed onto the stack; at an operator, first
op2(right) and thenop1(left) are popped and the result is pushed onto the stack. Θ(n). In prefix evaluation the expression is read from right to left and the first one popped is the left operand. - Infix to postfix: operands are written to the output; the operator on the stack is moved to the output as long as isp ≥ icp.
(has the highest precedence on arrival and the lowest on the stack; when)arrives, the stack is emptied down to(. Popping on equality gives left associativity. Θ(n). - Parenthesis checking: an opener is pushed onto the stack, and a closer must match the opener on top; at the end the stack must be empty. Three kinds of errors: wrong match, extra closer, unclosed opener.
- General principle: a stack wherever "the last opened is the first closed" is seen, a queue wherever "in order" is seen. Undo/redo, non-recursive traversal, next greater element, and the sliding window are other applications of this principle.
- Functions should be written like a component: inputs come in as parameters, the result goes out as the return value, and no dependency on global variables is created.
8.13Key terms
- stack
- LIFO
- backtracking
- maze
- look-up table
- brute force
- worst case
- depth-first search (DFS)
- breadth-first search (BFS)
- shortest path
- expression evaluation
- operator precedence
- associativity
- infix
- prefix (Polish notation)
- postfix (reverse Polish notation)
- token
- enumeration (enum)
- in-stack precedence (isp)
- incoming precedence (icp)
- global variable
- balanced parentheses
- short-circuit evaluation
- undo
- deque (double-ended queue)
- expression tree
- call stack
8.14Test Yourself
What are the postfix and prefix equivalents of the expression
a*b-(c+d)/e?Answer
The fully parenthesized form is
((a*b) − ((c+d)/e)). Postfix:ab*cd+e/-. Prefix:-*ab/+cde. In thepostfixroutine, when-arrives, the*on the stack is moved to the output;(goes on top of-; when)arrives,+passes to the output;/goes on top of-. At the end/and-come out.What is the value of the postfix expression
82/3-42*+? How many values does the stack hold at most?Answer
8 / 2 = 4, 4 − 3 = 1, 4 · 2 = 8, 1 + 8 = 9. The result is 9. The stack holds at most three values: at the moment
4and2are pushed, the stack holds 1 · 4 · 2.What value does
prefix_eval("+*23-84")return? What areop1andop2while-is processed?Answer
From right to left: 4 and 8 are pushed.
-: the first one popped,op1= 8,op2= 4, the result is 4. Then 3 and 2 are pushed;*:op1= 2,op2= 3, the result is 6.+: 6 + 4 = 10. The result is 10.What does
balanced("{[}]")return? At which character, and why?Answer
false.{and[are pushed onto the stack. When the third character}arrives,[is on top of the stack;matches('[', '}')is false. This is the wrong-match error. Since the numbers of openers and closers are equal, a single counter could not catch this error.If the comparison in the
postfixroutine is written as>instead of>=, how isa-b-cconverted? What are the values of the two results fora = 9,b = 5,c = 2?Answer
When the second
-arrives, the first-is not popped from the stack; the second-goes on top of it. The output isabc--, that is,a−(b−c). Its value is 9 − 3 = 6. The correct conversion,ab-c-, has the value (9 − 5) − 2 = 2.Would the path found change if the direction field of the initial record in
pathwere 0 instead of 1?Answer
It would not. Direction 0 looks north from
(1,1), that is, at the wall[0][1]on the frame. This direction is tried, skipped with++dirbecause it is a wall, and the search continues from direction 1 in the same way. Only one unnecessary trial is added.How would
a*(b+c)be converted ifisp('(')were 20 instead of 0?Answer
When
+arrives, isp(() = 20 ≥ icp(+) = 12, and(is moved to the output; then*is moved to the output as well (13 ≥ 12). A parenthesis gets mixed into the output and the order breaks. When)arrives, there is no(on the stack; the inner loop runs past the bottom marker and reads outside the array. This is why(must have the lowest precedence on the stack.What is the postfix of the expression
(a+b)*(c-d)/e? What is its value fora = 5,b = 3,c = 4,d = 2,e = 1?Answer
Postfix:
ab+cd-*e/.*and/have equal precedence and associate from the left; when/arrives,*is moved to the output. Value: 5 + 3 = 8, 4 − 2 = 2, 8 · 2 = 16, 16 / 1 = 16.If a queue is used instead of a stack in the maze, why is the first path found the shortest? Why is a cell that enters the queue marked as it enters?
Answer
The queue yields cells in order of their distance from the entrance: all cells at distance d are processed before those at distance d + 1. The path that first reaches a cell is therefore the shortest. If a cell were not marked on entering, another neighbor could add it to the queue a second time before it left the queue; the queue would grow needlessly and the
previnformation could be overwritten by a wrong path.
8.15Further reading
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Sections 3.5 and 3.6. The maze routine, the
isp/icptable, and expression evaluation are there in the form followed in these notes. - R. Sedgewick, Algorithms in C, Parts 1–4, Section 4.3. Postfix evaluation and infix-to-postfix conversion are treated as the first applications of the stack abstract data type; the relationship between recursion and the stack is treated in Chapter 5.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009, Chapters 10 and 22. The array implementation of the stack and queue and breadth-first and depth-first search are presented together with their correctness proofs.
8.16References
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Silicon Press, 2008. Sections 3.5 (maze) and 3.6 (expression evaluation).
- R. Sedgewick, Algorithms in C, Parts 1–4, 3rd ed., Addison-Wesley, 1998. Sections 4.3 (postfix) and 5 (recursion and the stack).
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009.