75 Points
Due: 2/15/00 at the start of class

Problem

Write a program that evaluates infix arithmetic expressions, including support for parentheses. The following operators must be supported:

    +
    -
    *
    /
    ( ... )
    + (unary)
    - (unary)

Implementation Language

For this assignment, your program must be written in Pascal. Your solution may only use standard Pascal code, not extensions or special library routines provided with your compiler.  Your program must adhere to proper use of the Pascal language as well as good programming style, including embedded routines, scoping, parameter passing, identifier naming, routine length, etc.

Input Format

Your program should be able to evaluate valid arithmetic expressions of arbitrary length. Your program should read a sequence of zero or more "candidate expressions", one per line, from its standard input (in the sense that this exists in Pascal). For each line of input, your program should attempt to interpret the line's contents as an expression. The "end" of the list of expressions is indicated by EOF on standard input. Optionally, you can choose to implement your program to recognize the single-token expression "quit" as representing the end of input if you find this easier. Blank lines in the input should simply be skipped.

Expressions will be made up of the following tokens:

• integers (operands)
• * / + - (standard binary math operators)
• + and - (unary versions of both)
• Left and Right parentheses

To be more precise, the following EBNF grammar describes the syntax of allowable expressions:

    <expression> --> <term>   { ( '+' | '-' ) <term>   }
    <term>       --> <factor> { ( '*' | '/' ) <factor> }
    <factor>     --> <integer>
		  |  ( '+' | '-' ) <factor>
                  |  '(' <expression> ')'

Examples:

(1 + 2 + 3 + 4 + 5) should evaluate to 15
(1 - 2 - 3 - 4 - 5) should evaluate to -13
(- 1 - 2 - 3 - 4 - 5) should evaluate to -15
(1 * 2 * 3 * 4 * 5) should evaluate to 120
(1 / 2 / 3 / 4 / 5) should evaluate to 1/120 = 0.0083
(- (3 * 2) + (101 - 99) * (999 - 994)) should evaluate to 4
- - -  4 +  + 6 should evaluate to 2
(1 + 2 * 3 - 4 / 5 + 6 * 7 - 8 / 9) should evaluate to 2129/45 = 47.31

Output Format

For each input expression, your program should produce one line of output. If the expression is valid and can be evaluated, the integer result of the evaluation is printed. For an expression that does not evaluate to a whole number, the answer should be printed as a fraction of integers together with its real number equivalent (see examples above). Otherwise, an appropriate error message should be issued:

• If one or more invalid token(s) appear in the expression, print the error message: "Expression contains invalid token(s)."

• If the expression is not syntactically correct (such as 8 + * 9), print the error message: "Incorrect expression syntax."

• If evaluation of the expression requires division by zero, print the message: "Division by zero."

Submitting Your Program

Your Pascal implementation is to be organized in a single file. The comments at the beginning of the file should identify the assignment and should give your name. Every Pascal procedure/function should be preceded by comments explaining its purpose, calling sequence, and implementation.

Be sure to follow the Program Submission Guidelines in preparing your report to turn in. In accordance with these guidelines, you will need to develop a set of test cases for your program that tests both positive and negative cases. For test cases that you are unable to run, be sure to indicate "Unable to perform test" in the corresponding test result within your report.

In gathering information for your report, you may find it useful to place all of these test cases in a single input file that you can feed to your program through I/O redirection. You can then capture the results of your tests while running under a command prompt (Windows or UNIX) for inclusion in your program report.