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 '(':
      S.push('(');

    case ')':
      while top of S != '('
      {
         write top of S to output;
         S.pop();
      }
      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;
         S.pop();
      }
      S.push(token);
   }
}

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

Searching a Graph

(The homework problem.)

Consider a flight map:

City file:

Phil
Hb
SC
Pitt
Balt
DC
You should have at least 10 cities.

Flight file:

Phil SC
Phil Hb
Phil Balt
SC Pitt
Hb SC
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.

Algorithm

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;
      else
         mark that city as visited and push onto stack;
   }

if the stack is empty
   no flight path exists
else
   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