SUNY Geneseo, Department of Computer Science
CSci 141 , Fall 2003
Prof. Doug Baldwin
Due Monday, November 24
This assignment asks you to write a program that acts as a simple calculator. Inside the calculator, you will need a data structure known as a "stack," which is somewhat like a list, but with a different set of operations. To complete this assignment, you will therefore need to write a stack class, know how to use stacks to implement a calculator, and know about some miscellaneous Java features.
A stack is basically a list of objects, except with very tight restrictions on how you can add objects to or remove them from the list. There are really only two main messages to stacks, one to add an item to the stack and one to remove an item:
The item that is about to be popped from a stack is often called the "top" of the stack. Thus another way to describe how push and pop interact is that push puts the new item at the top of the stack, and pop removes the top item.
While push and pop are the most important messages to stacks, a practical stack class will provide a few other messages too:
Your calculator will need to respect the precedence of operators. Specifically, it should apply multiplication and division before it applies addition or subtraction. For example, the expression "2 + 4 * 5" should evaluate to 22 (4 * 5 evaluates to 20, then add 2), not to 30 (as if 2 + 4 evaluated to 6, then multiply by 5). There is an elegant, stack-based, algorithm for evaluating arithmetic expressions with precedence.
The algorithm uses two stacks: one to keep track of operators that are waiting to be applied (because there might be a higher-precedence operator coming up) and one to keep track of the numbers to which the operators will be applied. The algorithm works as follows:
Initialize both stacks to be empty
for each symbol (i.e., number or operator) in the expression
If the symbol is a number
Push it onto the numbers stack
Else (the symbol must be an operator)
If the operators stack is empty,
or this symbol has higher precedence than the
top of the operators stack
Push this symbol onto the operators stack
Else
Pop the operators stack
Pop the numbers stack twice
(assuming all operators have two operands)
Apply the popped operator to the popped numbers
Push the result onto the numbers stack
Do the next iteration of the loop without changing
the input symbol
End of "for each symbol..." loop
While the operators stack isn't empty
Pop an operator and two numbers
Apply the operator to the numbers
Push the result onto the numbers stack
The answer is the top (and only) item on the numbers stackFor example, suppose the input expression were "10.5 + 4*2 - 1". Key actions of the calculator would be
The above presentation of the algorithm is designed to be as clear as possible, not as simple to code as possible.You can actually code the algorithm a little differently if you wish. For example, if you treat the end of the expression as a very low precedence "operator," you don't need the second loop. You can also adapt the algorithm to handle at least some unary operators (operators with only one operand) fairly easily. With a bit of special-case code, you can make the algorithm handle parenthesized expressions.
You will need to read text from the keyboard for this program. You can use many of the same input classes that you used in Homework 1 to do this. The online document Text Input and Output in Java (http://cs.geneseo.edu/~baldwin/reference/java-textio.html) summarizes these classes.
You also need to break text into "symbols" for the calculator to process. The quick and dirty (but perfectly acceptable) way to do this is to require the user to type expressions with one symbol per line. For example, the expression "1 + 2" would actually be entered
1 + 2
With this convention, you can use the readLine message to read
each symbol into a separate string.
If you feel more ambitious, the Java library provides classes called "tokenizers"
that break text into symbols. There are two tokenizer classes: StringTokenizer,
which breaks a string into symbols but leaves it up to you to read the string,
and StreamTokenizer, which reads symbols directly from an input
stream. If you feel like learning a bit on your own, you can use one of these
classes to give yor calculator a more natural user interface.
Calculators, obviously, do a lot of work with numbers. Depending on exactly
how you write your calculator, you may need to represent numbers in several
different ways, and to convert between representations. For example, when you
read numbers from the user, they will probably be strings of digits. When you
actually do calculations, you will need to do them on a primitive numeric data
type (I'd recommend double). When you push numbers onto a stack,
they will need to be objects of some sort (double is not an object
type in Java).
The Java library provides wrapper classes for numbers that can help with all of these representation and conversion issues. These wrappers are discussed in the separate online Java Numeric Wrapper Classes document (http://cs.geneseo.edu/~baldwin/reference/java-numwrapper.html).
In particular, you can create Double objects to encapsulate numeric
values that need to be pushed onto the numbers stack. For example, if x
and y are the operands to an addition whose result needs to be
pushed, you might write code such as
numbers.push( new Double( x + y ) );You can convert strings of digits directly to Double objects using
the static valueOf method of class Double. For example,
if symbol is a string containing the current symbol from an expression,
and you know that it is a number and so should be pushed on the numbers stack,
you might say
numbers.push( Double.valueOf( symbol ) );Finally, when you pop Double objects off of the stack, you can
extract non-object double values from them with the doubleValue
message. For example
Double wrapped = (Double)numbers.pop();double x = wrapped.doubleValue();
Design and code in Java a class that represents stacks of arbitrary objects. Then design and code a program that uses your stack class to implement a calculator, as described in the Background section. Your calculator should handle at least addition, subtraction, multiplication, and division of real numbers. These operations should obey the usual precedence rules (i.e., do multiplication and division first, then addition and subtraction; operations with the same precedence should be done left-to-right).
All operations on your stacks (push, pop, peek, isEmpty, and creation) should
run in asymptotically constant time. If it helps you determine whether yours
do, you may assume that our List class's first, rest,
setFirst, setRest, and isEmpty messages,
and constructors, run in constant time.
Turn in a printout of your stack class and calculator program. You do not have to turn in a proof that the stack operations run in constant time, but I will grade (in part) on whether they do, so it is in your interest to know anyhow.
In grading this assignment, I expect that you will be able to produce a working stack class with constant-time operations, and a working calculator that uses it. Some foreseeable ways to earn points above and beyond the "what I expect" level (once you satisfy the expectations) include providing a nice user interface, good error handling, implementing additional operations, good class and program design (e.g., associating methods with appropriate classes, defining additional methods to make code easy to write and understand, etc.), and clear and well-documented code.