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

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

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:

- Scan the tokens in order from left to right
- If the token is a number, push it on the stack
- If the token is an operator, pop two numbers off the stack, combine them using the operator, and push the result onto the stack
- Once all the tokens have been processed in this way, the stack should contain exactly one element: the result.

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

- While there are tokens to be read:
- Read a token.
- If the token is a number, then add it to the output list.
- If the token is an operator, o
_{1}, then: - while there is an operator token, o
_{2}, at the top of the stack and eithero

_{1}is left-associative and its precedence is*less than or equal*to that of o_{2}, or

o_{1}is right-associative, and has precedence*less than*that of o_{2},- pop o
_{2}off the stack, onto the output list;

- pop o
- Finally push o
_{1}onto the stack. - If the token is a left parenthesis, then push it onto the stack.
- If the token is a right parenthesis:
- Until the token at the top of the stack is a left parenthesis, pop operators off the stack and add them to the output list.
- Pop the left parenthesis from the stack, but not onto the output list.
- If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
- When there are no more tokens to read:
- While there are still operator tokens in the stack:
- If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
- Pop the operator and add it to the output list.
- Exit.

**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`.

`Postfix.java`or`Calculate.java`, whichever one you did.`Stack.java``LinkedList.java``ListIterator.java``Node.java``typescript`showing that you have**sufficiently tested your program using a range of inputs**`readme.txt`