PROB7: ROUTES

Find trucking routes between two terminal stations.

DESCRIPTION

The Truckee Freight Company has a network consisting of a number of terminal stations and transfer stations.

• At the terminal stations, the company deals with its customers, i.e., they accept cargo from senders and deliver cargo to recipients. When a cargo is shipped from a particular terminal station (the "source") to another terminal station (the "destination"), it must pass through one or more transfer stations.
• The company's stations are ordered into a tree-like hierarchy.
• The main transfer station is at the highest level of the hierarchy (the root of the tree).
• Every station (be it a terminal station or a transfer station), except the main transfer station, is connected to exactly one station on the next higher level of the hierarchy, called the parent station. A terminal station is not connected to any other station except for its parent. A transfer station is connected to one or more stations on the next lower level of the hierarchy; its children.
• The entire network will have at least two terminal stations.
• Every station appears only once in the shipping network, and is labeled by a unique upper case letter.

Consider the example shown in the figure. The main transfer station is T, and its children are B, W, D, and E. The terminal stations are F, H, R, J, K, W, L, and E. The transfer stations are T, B, M, and D.

Graph representation of the trucking network T(B(FHM(RJK))WD(L)E)

Given the particular arrangement of routes for the Truckee Freight Company, you are to determine routes for transporting a list of customer packages.

INPUT: prob7.dat

The input file will contain a sequence of routing problems separated by a single blank line. A given routing problem will have the form:


NETWORK
SOURCE_TERMINAL_STATION(1) DEST_TERMINAL_STATION(1)
SOURCE_TERMINAL_STATION(2) DEST_TERMINAL_STATION(2)
.
.
.
SOURCE_TERMINAL_STATION(N) DEST_TERMINAL_STATION(N)


• NETWORK is a parenthesized expression version of the routing network. For example, the network in figure 1 would be appear as
  T(B(FHM(RJK))WD(L)E)
  
  In this notation, the children of a node are listed in parenthesis after the node itself. A valid grammar for such expressions is
  
  main-transfer-station ::= transfer-station
  transfer-station ::= letter "(" children ")"
  terminal-station ::= letter
  children ::= child | child children
  child ::= transfer-station | terminal-station
  letter ::= "A" | "B" | ... | "Z"
  
  
  Here , the vertical bar means a logical "or" and the quoted items mean those literal symbols.
• SOURCE_TERMINAL_STATION(k) and DEST_TERMINAL_STATION(k) are the single uppercase characters representing which distinct terminal stations a customer package starts and where it should end.

An example input file using the network depicted in figure 1, along with a trivial routing configuration is:

       column   11111111112
       12345678901234567890
line 1:T(B(FHM(RJK))WD(L)E)[EOL]
     2:F H[EOL]
     3:R H[EOL]
     4:H R[EOL]
     5:J E[EOL]
     6:L F[EOL]
     7:[EOL]
     8:M(AB)[EOL]
     9:A B[EOL]
    10:B A[EOL]
      :[EOF]

OUTPUT: prob7.out

Other than the standard leader and trailer, the output file has a line of output for each line of input:

• The network configuration is echoed to the output file in the same format as the input.
• For each route in a given sequence of routes, the package path is written on a single line in the form:
  
  STATION(1)->STATION(2)->...->STATION(N)
  
  
  The route with the fewest number of transfers is always chosen.
• Like the input file, multiple routing problems are separated by single blank line.

The correct output corresponding to the example input file would be:

       column   111111111122222222223
       123456789012345678901234567890
line 1:Program 7 by team 0[EOL]
     2:T(B(FHM(RJK))WD(L)E)[EOL]
     3:F->B->H[EOL]
     4:R->M->B->H[EOL]
     5:H->B->M->R[EOL]
     6:J->M->B->T->E[EOL]
     7:L->D->T->B->F[EOL]
     8:[EOL]
     9:M(AB)[EOL]
    10:A->M->B[EOL]
    11:B->M->A[EOL]
    12:End of program 7 by team 0[EOL]
      :[EOF]