Computer Programming II

Lab Project #3b - Infix to Postfix with the Boxcar Algorithm

(Original version of the project by Prof. J. Saraille, CSUS)

PROBLEM:

You are to write a program in C++ that converts expressions written in infix notation to postfix (known as RPN). This project must use the stack and queue ADT code that you developed for project 3a. Include this code as two separate files, stack.h and queue.h using the #include preprocessor directive.

Here is an example of an input file:

$ (T + Q/H - U*K) - (T-B) /L*A $

$ (A + B ) / ( C - D) $

$ B * B - F * A * C /(T + A ) $

$ X * (X) + R - F / G $

$ X * (X + R - F / G $

Here is the output file corresponding to the input above:

Infix: $ ( T + Q / H - U * K ) - ( T - B ) / L * A $

Postfix: T Q H / + U K * - T B - L / A * -

Infix: $ ( A + B ) / ( C - D ) $

Postfix: A B + C D - /

Infix: $ B * B - F * A * C / ( T + A ) $

Postfix: B B * F A * C * T A + / -

Infix: $ X * ( X ) + R - F / G $

Postfix: X X * R + F G / -

Infix: $ X * ( X + R - F / G $

Postfix: Bad Expression.

In addition to the above, the program should also print out the rules table defined at the end of this specification just for your own debugging purposes. The program reads an infix expression from an input text file and writes it to an output text file. The program then, if possible, writes the translation of the expression. If the infix expression contains an error, it is not possible to make a translation. In that case the program writes the message "Bad Expression". This continues until all the infix expressions have been processed.

DESIGN

You must hand in a design detailing your data structures used to implement a stack and a queue. You don't need to write algorithms for the functions that manipulate the stacks and the queues. Your DETAILED documentation for the main portion of the project must be handed in as comments at the top of your program.

IMPLEMENTATION

Make sure you use typedefs of structs for your stack and queue elements. Build your code well and make it flexible with error-checking and full use of typedefs and #define macros.

Assume that the input will contain a series of infix expressions. Each expression will be on a line all by itself. Each variable in each expression will be a single upper case letter. The other meaningful symbols in expressions will be '$', '+', '-', '*', '/', '(', and ')'. All other characters must be treated as white space. The dollar sign ('$') will be the first and last symbol in every expression. Those two dollar signs will be the ONLY dollar signs in any expression. Any amount of white space is permitted to appear at any location in the input. Blank lines are permitted anywhere. There are no other rules about how the input must appear. You have to write the code of your program so that the program works correctly on ANY input that conforms to the rules above. See the sample input above, and create some good test input files for your own use in verifying that your program works.

THE BOXCAR ALGORITHM

The method the program will use to translate infix formulas is called the boxcar algorithm and is credited to E.W. Dijkstra. There are just a few action rules for doing translations. This tends to make translation rather easy. However, one must decide which action rule to apply, and when to apply it. Most of the logic required to make such decisions is fairly simple, but to write working code requires the talent of visualizing the abstractions of stacks and queues clearly in one's mind.

The program employs a stack and queue. Before starting to translate each expression the program makes sure that both the stack and the queue exist and are empty. A translation always begins by reading the initial '$' and pushing it onto the stack. During translation, any variable read from the input is immediately enqueued.

Let's agree to use the name "current symbol" for the black space character most recently read from the input. When the current symbol is NOT the initial dollar-sign, and is NOT a variable, the program consults a table in order to get the number of a rule to apply. The rule tells what the program must do next in order to go forward with the translation. The rule number lies in the ROW of the table corresponding to the symbol on the top of the stack, and the COLUMN of the table corresponding to the current symbol. Although there is a large number of combinations of stack top symbol and current symbol, there are only 5 rule numbers.

Here are the rules:

RULE 1. Push the current symbol onto the stack and read another black space character from the input.

RULE 2. Pop the stack and enqueue the symbol that comes out. Do NOT read a new black space character from the input.

RULE 3. Pop the stack and read another black space character. Do NOT save any characters, or put anything in the queue at this time.

RULE 4. Stop. The symbols now on the queue represent the postfix translation of the infix expression.

RULE 5. Stop. An error in the input has been discovered.

Rule Number Table

(Row corresponds to stack top. Column corresponds to current input character.)

$ + - * / ( )

$ 4 1 1 1 1 1 5

+ 2 2 2 1 1 1 2

- 2 2 2 1 1 1 2

* 2 2 2 2 2 1 2

/ 2 2 2 2 2 1 2

( 5 1 1 1 1 1 3

DELIVERABLES

The required design can be handed in separately from your source code. The source file and sample runs should be on hardcopy and should follow our class coding and testing standards.