Implement an expanded version of the HPAir problem. In addition to the “from” and “to” cities, each line of input contains a fl ight number (an integer) and the cost of the fl ight (an integer). Modify the HPAir program so that it will produce a complete itinerary for each request, including the fl ight number of each fl ight, the cost of each fl ight, and the total cost of the trip.
For example, the input fi les could appear as
cityFile: Albuquerque
Chicago
San Diego
flightFile: Chicago, San Diego 703 325
Chicago, Albuquerque 111 250
Albuquerque, Chicago 178 250
requestFile: Albuquerque, San Diego
Albuquerque, Paris
San Diego, Chicago
For this input, the program should produce the following output:
Request is to fly from Albuquerque to San Diego.
Flight #178 from Albuquerque to Chicago Cost: $250
Flight #703 from Chicago to San Diego Cost: $325
Total Cost ............. $575
Request is to fly from Albuquerque to Paris.
Sorry. HPAir does not serve Paris.
Request is to fly from San Diego to Chicago.
Sorry. HPAir does not fly from San Diego to Chicago.
When the nonrecursive isPath method fi nds a sequence of fl ights from the origin city to the destination city, its stack contains the corresponding path of cities. The stumbling block to reporting this path is that the cities appear in the stack in reverse order; that is, the destination city is at the top of the stack and the origin city is at the bottom. For example, if you use the program to fi nd a path from city P to city Z in Figure 6-6 , the fi nal contents of the stack will be P-W-Y-Z with Z on top. You want to display the origin city P fi rst, but it is at the bottom of the stack. If you restrict yourself to the stack operations, the only way that you can write the path in its correct order is fi rst to reverse the stack by popping it onto a temporary stack and then to write the cities as you pop them off the temporary stack. Note that this approach requires that you process each city on the path twice. Evidently, a stack is not the appropriate ADT for the problem of writing the path of cities in the correct order; the appropriate ADT is a traversable stack . In addition to the standard stack operations isEmpty , push , pop , and peek , a traversable stack includes the operation traverse . The traverse operation begins at one end of the stack and visits each item in the stack until it reaches the other end of the stack. For this project, you want traverse to begin at the bottom of the stack and move toward the top.