Homework 5: Arithmetic Expressions with Stacks
Due: Wednesday, Mar. 2, 11:59pm
This assignment will give you practice using stacks in a real parsing application. You will write a program that computes the result of arithmetic expressions. The simplest version will read an expression in postfix notation. For full credit, implement a form of the shunting yard algorithm to interpret regular infix expressions.
This assignment is individual, so everyone should submit their own original code. However, you are welcome to collaborate with other students and discuss aspects of the assignment outside of the code.
Your program should read the expression to be computed from the command line, in the form shown below:
java Calculate "(3+2)*5"
The quotation marks are required because the parentheses would otherwise be interpreted by the shell rather than being passed to your program as input. In this instance, the program should print out the result of 25.
Often when we run a program, it is useful to provide additional information or directives as we issue the command, so as to guide its behavior. We can do this in the form of command line arguments, which are pieces of text given on the same line as the command that runs the program but just after it. This type of guidance should already be familiar from the Unix commands we have seen, although you may not have realized it before. Some examples:
cd lab1 javac MyProgram.java java MyProgram rsubmit lab1 MyProgram.java
In the examples above, the programs run are named cd, javac, java, and rsubmit, respectively. The remainder of each line consists of one or more command line arguments.
In a java program, the command line arguments are provided as arguments to the method main. Recall the signature of main:
public static void main(String[] args)
The command line arguments appear in the array args. The program name itself is not included. So for example, if you run a program with the command
java MyProgram first secondthen the array args would have length two, and the values contained would be first and second.
Note that some symbols such as parentheses don't make good command line arguments, because they are interpreted as character with special meaning by the command shell. This is not a Java issue per se, but the behavior of the underlying operating system. In order to include such characters in a command line argument, or to include spaces, enclose each argument in double quotes. For example:
java MyProgram "four words, one argument"
It is good form in programs that rely on command line arguments always to check that the user has provided the number of arguments expected, and print a short message with the expected usage if they have not. Otherwise execution may terminate abruptly with an ArrayIndexOutOfBoundsException as your program tries to read the nonexistent argument.
Eclipse and other IDEs have alternate means for specifying command line arguments. Instructions for Eclipse are available here.
Since we are reading the expression from the command line arguments, it will be of type String. We can convert this to a series of discrete tokens using a Scanner. This will separate numbers, operators, parentheses, etc. and feed them to us one at a time. To see how the scanner works, compile and run this short demonstration program: ShuntYardStub.java. You may also use this as the starting point for your own program (change the filename).
The simplest possible version of this assignment (which will receive some credit, but not full marks) will only accept arithmetic expressions in postfix notation. For example, "3 2 + 5 *" means (3+2)*5 in our standard infix notation. As a reminder, here is the algorithm for computing the value of postfix expressions:
Handling infix expressions is slightly more complicated, since you have to deal with parentheses. However, it turns out that infix expressions can be converted (parens and all) into postfix ones using a single stack. The value may then be computed using the postfix expression algorithm given above. The outline below is a simplified version of the one given on Wikipedia: Shunting-yard algorithm.
Note that to follow this implementation you will need one stack of type Stack<Object>. For the output queue, use the linked list class you wrote in Lab 4 LinkedList<Object> and use the add method to add elements to the end of it.
o1 is left-associative and its precedence is less than or
equal to that of o2, or
o1 is right-associative, and has precedence less
than that of o2,
UPDATE: there is now a video on how to do this part!
After running this algorithm, you should have a postfix expression in LinkedList form. For full credit, use an iterator to iterate through the linked list and use your postfix calculator to compute and return the value of the expression.
To write an iterator for your linked list class, create a new class ListIterator. This should implement Iterator:
public class ListIterator<E> implements Iterator<E>And then linked list should implement Iterable:
public class LinkedList<E> implements Iterable<E>Look up the required methods for each interface and implement them in your code. This is not a major part of the assignment, but it's really good practice to be able to write and use an iterator. After you've completed this part, you can use a "foreach" loop to compute the postfix expression:
// use a foreach loop to iterate over the output list
for (Object symbol: output) {
...
}
Both the stack and the output stream for the shunting-yard algorithm will need to hold data of heterogeneous types: Double for the numbers, and Character for the operators (not to mention String for function names if you try the extra credit). When you pop an element off the stack and need to figure out what type it has, use the instanceof operator.
If you begin by writing a program to handle postfix expressions, you should be able to reuse most of the code to handle the output of the shunting-yard algorithm.
Make sure to test your program on a range of inputs and demonstrate this in a typescript! Here is an example, but you should have several more demonstrating all the functionality:
script java Calculate "(3+5)*2" java Calculate "2/(1+8)*10" exit
For the normal assignment, you need only consider the normal arithmetic operators +, -, *, /, and ^ (addition, subtraction, multiplication, division, and exponentiation), plus parentheses for grouping. You may ignore the unary minus (e.g., 5+(-3). The full shunting-yard algorithm given at the wikipedia page can handle the unary minus, constants such as pi, and functional expressions like sin(0) and max(3,4). For extra credit, augment your program to compute expressions that include elements like these. Describe the augmentations in your readme.txt.