Expression Evaluation Assignment CIT 594, Assignment 5: Expression Evaluation Dave Matuszek, Spring 2002 Purposes of this assignment: To give you experience with StringTokenizer To give you experience with implementing and using stacks To give you experience with creating "wrapper" classes To give you experience with creating and using Exceptions To teach you one of the fundamental algorithms of computer science To give you yet more experience with Forté (There's a lot in this assignment!) Overview Your assignment is to write a "calculator" applet. Instead of clicking buttons, the user types in either an expression or an assignment, and the calculator computes and displays the result. Examples: The user types in (2+3)*(4+ 5), and the calculator responds with 45.0. The user types in ABC=3.0*17, and the calculator responds with 51.0. The user types in X=2*ABC, and the calculator responds with 102.0. The user types in 3, and the calculator responds with 3.0. The user types in 1/3, and the calculator responds with 0.3333333333333333. An arithmetic expression consists of: Numbers. All numbers will be represented internally by double values. You do not need to worry about how many digits appear in your output; however Java decides to display it as a String will be fine. Variables. A variable is a simple name, and stands for a double value. When used in an expression, a variable may be replaced by its value. Parentheses. They have their usual meaning. Only ( and ) will be used; don't use { } [ ]. + for addition; used only as a binary operator. - for subtraction; used only as a binary operator. * for multiplication. / for division. ^ for exponentiation. (See java.lang.Math). An assignment consists of: A variable name, such as X or HelloThere. An equals sign, =. An expression, as defined above. The GUI for this program will be very simple; all you need (along with your name) is a TextField for the user to type in an expression or assignment, and a scrollable TextArea for displaying the results. Each time the user types in something, append to the TextArea two lines: (1) the expression the user typed in, and (2) the result. If you think of other things you wish to add to the GUI, you may do so. This is an applet, so it's better to use AWT rather than Swing. The algorithm You need two stacks, a value stack (to hold the numbers), and an operator stack (to hold the operators). Numbers will be double values, operators will be char values. The algorithm is roughly as follows. Note that no error checking is done explicitly; you should add that yourself. If the first token is a variable and the second token is =, this is an assignment. Compute the rest of the expression as usual, do the assignment, and terminate. While there are still tokens to be read in, Get the next token. If the token is: A number: push it onto the value stack. A variable: get its value, and push its value onto the value stack. A left parenthesis: push it onto the operator stack. A right parenthesis: While the thing on top of the operator stack is not a left parenthesis, Pop the operator from the operator stack. Pop the value stack twice, getting two operands. Apply the operator to the operands, in the correct order. Push the result onto the value stack. Pop the left parenthesis from the operator stack, and discard it. An operator (call it thisOp): While the operator stack is not empty, and the top thing on the operator stack has the same or greater precedence as thisOp, Pop the operator from the operator stack. Pop the value stack twice, getting two operands. Apply the operator to the operands, in the correct order. Push the result onto the value stack. Push thisOp onto the operator stack. While the operator stack is not empty, Pop the operator from the operator stack. Pop the value stack twice, getting two operands. Apply the operator to the operands, in the correct order. Push the result onto the value stack. At this point the operator stack should be empty, and the value stack should have only one value in it, which is the final result. There are some obvious opportunities for helper methods here. You should also consider writing a method that, given an operator, returns its precedence. For debugging my program, I found it very helpful to print out (1) the operator stack, (2), the value stack, and (3) the next token, on a single line. (The toString method of java.util.Stack is very nice.) For example, given the input 1+2*(3+4), my trace routine prints out: [] [] 1
[] [1.0] +
[+] [1.0] 2
[+] [1.0, 2.0] *
[+, *] [1.0, 2.0] (
[+, *, (] [1.0, 2.0] 3
[+, *, (] [1.0, 2.0, 3.0] +
[+, *, (, +] [1.0, 2.0, 3.0] 4
[+, *, (, +] [1.0, 2.0, 3.0, 4.0] )
[+, *] [1.0, 2.0, 7.0]
[+] [1.0, 14.0]
[] [15.0] Assignments Here's a simple little helper class that I wrote. Notice that it's a wrapper for java.util.HashMap. import java.util.*;
public class Memory {
HashMap map;
/** Creates new Memory */
public Memory() {
map = new HashMap();
}
public void store(String name, double value) {
map.put(name, new Double(value));
}
public double fetch(String name) {
return ((Double)map.get(name)).doubleValue();
}
} To use this class: Create a Memory object, say, myVariables. If String variable is the name of a variable, and double value is the value you want it to have, save this in memory by saying: myVariables.store(variable, value); If String variable is the name of a variable whose value you want to get back (say, into double value), say: value = myVariables.fetch(variable); Requirements Your name must be displayed on the applet. In fact, that's a general rule for all future assignments, even if I forget to mention it explicitly. This assignment requires two stacks. For pedagogical reasons only, you are to implement these stacks in two different ways. The value (number) stack. Write a ValueStack class, which implements the following methods: double push(double) double peek() double pop() boolean empty() int search(double) (Optional; you aren't likely to need it.) You can use either an array implementation or a linked-list implementation. You may "borrow" code directly from the textbook, if you prefer, provided you put a reference to it in your comments. However, even if you borrow code, use the above signatures for your methods. The operator ("op") stack. Write an OperatorStack class that simply provides a wrapper for Java's java.util.Stack class. That is, your class will contain a private Java Stack object, and it will use Java's provided methods for operations on the class. All your class does is take and return char values (each operator is represented as a single char), rather than Object values. The whole point of this class is to take care of the chore of wrapping and unwrapping char values in Character objects, so the user of an OperatorStack doesn't have to bother doing so. Provide the following methods: char push(char) char peek() char pop() boolean empty() int search(char) (Optional; you aren't likely to need it.) Use a StringTokenizer to break the input expression up into operators + - * / ^ ( ) and operands (numbers and variables). StringTokenizer is defined in the java.lang package; it isn't too hard to figure out, and it's really useful for this kind of job. Hint: you want the three-argument constructor, since you want to use the operators as delimiters. Use Exceptions. Whenever you detect an error in the expression or assignment being evaluated, create and throw an ArithmeticException. (The ArithmeticException class is in java.lang.) I strongly recommend that your most important routine have a signature something like: double evaluate(String expression) throws ArithmeticException This isn't as scary as it sounds. ArithmeticException is a class like any other, and you can create and throw one with code such as throw new ArithmeticException("my message"); Then, when you call evaluate, you do so like this: try { result = evaluate(expression); } catch (ArithmeticException e) { /* Do something with e */ } Use Forté to do this assignment. Extra Credit You can get a small amount of extra credit by improving your expression evaluator in the following ways: As described, the calculator handles only binary + and - (add and subtract); it doesn't handle unary + and -. (A unary + or - is either the first thing in the expression, or the first thing after a left parenthesis.) Fix this. As described, the calculator treats every operator as left associative, but exponentiation should be right associative. Fix this. Allow blanks in the expression (everywhere except inside numbers and variables). Due This assignment is due by midnight, Thursday, February 21. Do all your work in a single folder (directory), jar that directory, and submit it via Blackboard.
