SUNY Geneseo, Department of Computer Science
CSci 141 , Fall 2004
Prof. Doug Baldwin
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.” To complete this assignment, you will therefore need to know something about stacks, know how to use stacks to implement a calculator, and know about some Java features that will help you read and process inputs to your calculator.
Stacks are described in chapter 12 of Algorithms and Data Structures: The Science of Computing.
An Implementation of the Stack class described in chapter 12 is available on the Web. Documentation for this class is also available on the Web. The main documentation page is an index to documentation for all the Java classes written for use with Algorithms and Data Structures: The Science of Computing. To see the documentation for a specific class, click on that class’s name in the left-hand panel of the page.
The calculator you will write for this assignment is a boolean calculator. In other words, the operations it applies to values are the basic boolean operations of “and,” “or,” and “not.” The values to which it applies these operations are the truth values “true” and “false.” See chapter 5 of Algorithms and Data Structures: The Science of Computing for complete descriptions of these operations. In the following, I will represent the operators using the following symbols:
| Operation | Symbol |
|---|---|
| Complementation | ~ |
| Conjunction | ^ |
| Disjunction | v |
I will represent the truth values by the letters T (for true) and F (for false).
Your calculator will need to respect the precedence of operators. Specifically, it should apply complementation (“not”) before it applies conjunction (“and”), which it should in turn apply before it applies disjunction (“or”). For example, the expression “F ^ T v F” should evaluate to F (false, evaluating “F ^ T” to F, then applying “v” to this and F), not to T (as if “T v F” were evaluated first, yielding T, which was then anded with T). There is an elegant, stack-based, algorithm for evaluating 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 values to which the operators will be applied. The algorithm works as follows:
Initialize both stacks to be empty
for each symbol (i.e., value or operator) in the expression
If the symbol is a value
Push it onto the values 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 values stack as many times as there are operands to this operator
Apply the popped operator to the popped values
Push the result onto the values 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 its operands
Apply the operator to the operands
Push the result onto the values stack
The answer is the top (and only) item on the values stackThe 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. With a bit of special-case code, you can make the algorithm handle parenthesized expressions.
You will need to read text from the user for this program. You can use any of the techniques you have used before (e.g., the JOptionPane class, readers and streams, etc.) to do this.
You also need to break text into “symbols” for the calculator to process. If you use the notation I have suggested above for operators and values, each symbol is conveniently exactly 1 character, so you can read an input expresion as a string and then process it character by character.
You will need to push a variety of non-object types onto the stacks for this exercise (e.g., booleans, characters, etc.) Wrapper classes, such as those that you used with lists will be helpful for this, although the exact classes will be different (you aren’t working with numbers as you were in the list exercises).
Design and code in Java a program that acts as a boolean calculator, as described in the Background section. Your calculator should handle at least complementation, congjunction,and disjunction. These operations should obey the precedence rules given in the Background section.
This exercise should be completed by Tuesday, November 16. I will grade ite through face-to-face meetings with you, and these meetings must be completed by 1:00 PM on Wednesday, November 17.
To arrange a grading appointment, simply sign up on the schedule outside my office. Make your appointment 15 minutes (half a block on the schedule) long. Each student should sign up for an individual appointment.
Ideally, I would like to see your program run during the grading appointment. You can bring the program to my office on a laptop computer, or you can set the program up in a lab and then bring me to the lab. I will also need to see the program code (which I can almost certainly do on-line when running the program).