75 Points
Due: 4/25/00 at the start of class

Problem

This assignment is a duplicate of Program 1, in a different language.

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 Prolog. You will be programming in a "logic programming" style, as described in Chapter 15 of the text book. Since this program must be written in Prolog, appropriate use of logic programming language features is expected. In particular, you may not use any versions of assert, retract, record, erase, flag, or any of the other database features of Prolog.

As with prior programs, your solution must adhere to good programming style, including correct use of parameter passing, identifier naming, predicate length, commenting, headers for each predicate, 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. 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

In your solution, be sure to place comments at the beginning of each file that identify the assignment and give your name. Every Prolog predicate (rule or fact) should be preceded by comments explaining its purpose and the interpretation of its arguments. If you have multiple rules or facts that have the same name and arity (number of arguments), group them together; the header comments for such a predicate only need to be provided once at the beginning of the group, rather than repeated for each such rule or fact.

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. You may reuse test cases from Programs 1 and 2, but be sure you have made any necessary corrections or additions based upon the comments received for those assignments.

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.