CPS 108 : Arithmetica

Spring 1999

Due February 1

For this mastery, you will write an arithmetic interpreter that allows users to enter, change, combine, and evaluate arithmetic expressions interactively. The name arithmetica was suggested by Professor Michael Littman as a pun on the popular mathematics interpreter Mathematica. This program is your first mastery program and it must be done alone.

Specification

You are to write a program that implements a simple arithmetic interpreter. A user of your program should be able to enter arithmetic expressions interactively while your program keeps track of them. The user can enter expressions that conform to the types described in the table below. Your program should save the expression entered as an expression tree so that it can be evaluated whenever the user requests.

A user can explicitly save an expression to a named variable. Such variables can be used to refer to the saved expression in other expressions. If the user uses a variable name in an expression that has not previously been given a value, you should assume its value is zero.

Unless the user explicitly saves an expression to such a variable, it is saved as the current expression. If the entered expression is incomplete, it is combined with the current expression and the result is stored again as the current expression. Otherwise, it replaces the current expression. Additionally, the user can refer to the current expression explicitly using the special name "!!".

In these ways (using variables and a saved current expression), the user can build complex expressions interactively. Whenever the user enters a complete expression, it should be evaluated and the value printed for the user.

An example session might look like the following (the user's input is in bold):

Welcome to Arithmetica
> 3 + 7 * 2
17
> (3 + 7) * 2
20
> + 10
30
> * 10
300
> --!!
299
> a = 2 ^ 4
16
> b = 16
16
> c = a - b
0
> b = 2 * 16
32
> c
-16
> a = ++b
33
> c
1
> print(c)
((a) - (b))
> sum(a, b, c, !!, (3 + 7) * 2)
351
> ^D

The user can end a session with your interpreter at any time by typing ctrl-d (the control and d key at the same time). Your implementation should ignore spaces and lines of input that are empty, i.e., only zero or more spaces, and lines that begin with the comment character "#".

Expressions

Your program should recognize the following expressions:

expression	*syntax*	semantics	*examples*
Constant	`<any integer>` `[0-9]+`	an integer constant	`87` `13` `0`
Variable	`<any string>` `[a-zA-z_]+`	an expression represented by a word Note, the special symbol "!!" refers to the current expression	`a` `bugs` `total_squished`
Assignment	`var = expr`	assigns an expression to a variable by copying the expression	`a = 87` `bugs = 12 * a` `a = b = ++c`
Unary Operator	`op expr`	prefixes an expression - // negation ++ // one plus -- // one minus	`-13` `++(a + b * c)` `--bugs`
Unary Functions	`fun(expr)`	a function that takes an expression as its single argument sin // sine cos // cosine sqrt // square root print // infix	`sin(a * b)` `sqr(x) - y ^ 2` `print(bugs)`
Binary Operator	`expr op expr`	combines two expressions into a single expression + // plus - // minus * // times / // divide % // remainder ^ // power	`a + b` `a ^ 2` `a + 10 * c`
Multi-Argument Functions	`fun(expr,...)`	a function that takes one or more expressions as arguments (each separated by a comma) sum avg mean	`sum(a, 1, ++b)`
Parentheses	`(expr)`	raises an expression's precedence	`(a + b) * 3` `sum(3*(bugs+t))`

Operators have the following precedence from left to right (listed from highest to lowest):

`()`	parentheses
`-`, `--`, `++`	unary operators
`^`, `*`, `/`, `%`	arithmetic operators
`+`, `-`	arithmetic operators
`=`	assignment

Implementation

As you may have guessed by now, a well implemented expression tree is a key component of this assignment. You may use as little or as much of the exptree example code discussed in class. An important aspect of this assignment is the allowable expressions it recognizes. Your design should be open to adding new kinds of expressions with minimal effort.

Unlike the example in class, this program requires you to convert the user's entered text from a string into an expression tree. Since the user enter's each expression in infix notation (convenient for humans), you will need to convert it to postfix notation (convenient for computers) to build your tree. To convert the infix expressions entered by the user into an expression tree, we suggest you use Dijkstra's infix to postfix algorithm discussed in Weiss, Algorithms, Data Structures, and Problem Solving, page 362 or Main and Savitch, Data Structures and Other Objects, page 332. Additionally, there is an online resource here in the form of a past CPS lab. Keep in mind that this part (class?) of the program also has to know about kinds of expressions (to recognize and create them). It should also be designed to be open to adding new kinds of expressions.

You should not need to invent any of the data structures for this program. The C++ STL contains a variety of "containers" such as stack, vector, list, and map. Additionally, string is now a standard C++ class. For example, you may want to represent the user's variables using an STL map of strings to expression trees. You cannot use the CPS tapestry libraries for this program.

It is suggested you start small and build up the functionality of you program. In particular, you should not implement every variety of operator before you have tested even one of them.

Extra Credit

For extra credit, you could implement the following extensions (note, you can add more operators as well, but that will not be worth much extra credit):

Variables	allow spaces in variable names
References	allow variables that refer to other expressions instead of copies of them
History	give the user access to a history of the expressions that have been typed in For this extension, use the standard UNIX shell syntax to access the history (i.e., `!!` refers to the current expression, `!12` refers to the twelfth expression entered, or `!-1` refers to the previous expression entered).
Completion	complete the partial variable name from those already entered by the user when tab is pressed

Additionally, you can also optimize your interpreter by ensuring that only one copy of each expression exists at any given time. A reasonable way to do this is called reference counting and is discussed in Meyers, More Effective C++, Item 29.

Comments?