Stack Applications

Tom Kelliher, CS23

Mar. 20, 1996

Infix to Postfix Conversion

Recall the recursive descent parser.

Key ideas:

Discover the holding rules:

a + b + c

a + b * c * d

(a + b) * c

a * (b + c + d) * e

Pseudocode (no error checking):

Stack S;

while there is a token
   get next token;

   switch (token)
    case operand:
      write operand to output;

    case '(':

    case ')':
      while top of S != '('
         write top of S to output;
      S.pop();   // remove '(' from S

    case operator:
      while !S.StackIsEmpty() 
         && top of S has higher or equal precedence than token
         write top of S to output;

while !S.StackIsEmpty()
   write top of S to output;   // May still have valid operators on stack

Searching a Graph

(The homework problem.)

Consider a flight map:

City file:

You should have at least 10 cities.

Flight file:

Phil SC
Phil Hb
Phil Balt
SC Pitt
Pitt Hb
Balt DC
DC Pitt
You should have at least 20 flights.

Request file:

Phil DC
DC Phil
You should have sufficient requests to demonstrate:

Basic Data Structures

Implemented as various classes.

  1. Adjacency lists to represent flight map.
  2. Vector of unvisited cities.
  3. Itinerary stack.
  4. Functions to map from a city name to a city number and vice-versa.


read city file, construct names array, visited array,
   empty adjacency lists;

read flight file, filling adjacency lists to construct flight map;

open request file;

while there is a request
   check its validity;
   mark departure point visited and push onto stack;

   while the stack is not empty and the destination 
      is not on top of stack
      if there are no unvisited cities on the adjacency list for
         the top of stack city
         pop it from the stack;
         mark that city as visited and push onto stack;

if the stack is empty
   no flight path exists
   print the flight path

Example Execution

Stacks and Recursion

What does recursion use?

What data structure is used for activation records?

Thomas P. Kelliher
Tue Mar 19 11:49:02 EST 1996
Tom Kelliher