Stack Applications

Tom Kelliher, CS23

Mar. 20, 1996

Infix to Postfix Conversion

Recall the recursive descent parser.

Key ideas:

• Relative positioning of operands unchanged:

  a + b * c
  a b c * +
  

  Always copy operand from input to output.
• Some operators ``held-up'' in stack.
• Parenthesized sub-expressions.

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

Flight file:

Phil SC
Phil Hb
Phil Balt
SC Pitt
Hb SC
Pitt Hb
Balt DC
DC Pitt

Request file:

Phil DC
DC Phil

• Your program recognizes invalid departure/arrival cities.
• Your program can find a complex set of flights from a departure city to an arrival city and print the list of cities.
• Your program doesn't follow a cycle in the flight map.
• Your program recognizes when there is no set of flights connecting a given departure city and arrival city.

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?