75 Points
Due: 3/7/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 Scheme. You will be programming in a "functional" style, as described in Chapter 14 of the text book. Since this program must be written in Scheme, appropriate use of functional language features is expected, and you may not use any of the imperative features of Scheme. Hence,

• You must use recursion rather than iteration.

• No assignment is permitted. Assignment is an imperative concept, based on the model of a stored memory machine, and it does not exist in pure functional languages. Scheme does have some imperative features, and those are the ones to avoid: set!, set-car!, set-cdr!, and all other operations with names ending in "!" are not allowed.

• Do not use global variables--bound names with values that change over the life of your program. In fact, none of your bound names, whether global or local, should change in value over time. Global constants, with a value that never changes, are fine. For local names, think of them as names for common subexpressions that you wish to use in more than one place.

• The control structures you cannot use are do and begin. That still leaves you with plenty of control structures to work with, though. Here are some suggestions:
  • For selection, use cond or if. The if function is a special case of cond. If you only use cond, you'll probably never miss begin.
  • For iteration, use a named let. That means using recursion in spirit whenever you need to repeat a series of actions. Alternatively, you can define a separate recursive function if you prefer.
  • If you prefer, you can also write a simple recursive function to perform any iterative task you wish. If find it easier to write a recursive function than to use a named let, then it is perfectly OK to do that instead.

• Although it is not an imperative feature, you may not use eval in your solution. Can you figure out why?

As with Program 1, your solution must adhere to good programming style, including correct use of parameter passing, identifier naming, function length, commenting, headers for each function, 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 Scheme function or global constant should be preceded by comments explaining its purpose, and for functions, explaining its 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. You may reuse test cases from Program 1, but be sure you collect your graded Program 1 report so that you can correct or improve your test cases based on the comments you receive.

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.