Project 3: Expression Computation (Due: 11/27/2018)
You are to write a scheme program that takes an expression in infix notation and evaluate it. Neither precedence nor associativity among operators is assumed. Therefore, each expression will contain the necessary and sufficient set of parentheses to disambiguate the order of computation. The operations that you can expect are:
“+” : addition
“-” : subtraction
“*” : multiplication
“/” : real division
“^” : exponentiation (you must write this function)
For example, given the following expressions
(3 + 5)
((1 + ((6 / 3) * 4)) – (5 * 6))
((2 + 3) ^ (2 * 4))
((1 – ((5 + 3) * (4 ^ 3))) – (20 / 4))
your program should produce the expected results, i.e.
8
-21 390625 -516
YOU CANNOT USE THE “EVAL” FUNCTION IN THIS ASSIGNMENT You will turn in a zip file containing:
(a) the compute program(s) – commented, and
(b) a listing of the output generated by invoking compute on the above data
Your program must be named “compute”. The program must contain a function named “compute”. Optionally, you can also define other functions to facilitate computation as you like.
The TA will execute your program on “rlogin” using “plt-r5rs < compute”, where “compute” is the name of the file containing your scheme program. plt-r5rs (/usr/local/bin/plt-r5rs) is the UNIX
scheme interpreter provided by Racket. The TA will add tests at the end of your program. The tests will be of the form “(compute ‘(…))”.
If you download the Scheme interpreter for windows, the Language you will select will be “R5RS” under Legacy Languages. This will define how your interpreter works and to which functions you have access. Note, however, that the TA will execute your programs on Rlogin!
You are restricted to:
The LISP Numeric Primitives: +, -, *, /
The LISP Predicates: =, <, >, >=, <=, <>, even?, odd? and zero?
symbol?, number?, list? and null?
The LISP functions: define, quote (‘), car, cdr, cons, cond, eq?, and equal?
The car and cdr family of functions, e.g., caar, cadr, cddr, etc. If you need additional helper functions, define them.