Project 1: The Shunting Yard Algorithm, Due Wednesday, 9/26
So far, we've learned about Lists, Stacks, and Queues. We'll use the latter two to do some arithmetic.
Writing a calculator that can handle an input like 1 + 2 * 3 ^ 2 is actually reasonably hard; order of operations means we can't just compute left to right. Instead, we would have to read the entire line, keeping track of what operations we've seen, so we can compute the ones with highest precedence first. This is a pain.
The operations can also be written using Reverse Polish Notation (also known as RPN, or postfix notation). Some examples of RPN:
| Infix | Postfix |
|---|---|
| 1 + 2 | 1 2 + |
| 1 + 2 * 3 | 1 2 3 * + |
| 1 * 2 + 3 | 1 2 * 3 + |
Solving RPN equations
Doing arithmetic in RPN notation is really easy if you have a stack (what a coincidence!). Here's what you do:
While unread tokens exist in the input queue // a "token" is a number or operator
Read the token. If the token is a number, push it on the stack
If the token is an operator
Pop two numbers off the stack
Apply the operator to those two numbers
Push the result back onto the stack
There should be one token containing the answer remaining in the stack
Great! That seems pretty easy. How do we get infix notation into RPN?
Converting Infix Notation to RPN
For this, we'll use Edsgar Dijkstra's "shunting yard algorithm." Dijkstra is CS royalty for two reasons: his contributions to CS are fundamental and legion, and he was really good at pithily calling people idiots. For both reasons, you'll see his name again.
First, a note about precedence. Every operation has precedence, which is where order of operations comes from. Multiplication has higher precedence than addition, so you would compute the multiplication first. The Wikipedia page on this algorithm has a precedence table for our operations.
The way it works is this:
While tokens remain in the input,
Read a token
If the token is a number, add it to the output queue
If the token is an operator o1,
while the operator at the top of the stack has higher or equal precedence compared to o1,
pop that operator off the stack, and add it to the output queue
push o1 onto the stack
If the token is a left parenthesis,
push it on the stack
If the token is a right parenthesis,
while the token at the stop of the stack is not a left parenthesis,
pop the stack, and put that token in the output queue
pop the left parenthesis, but do not put it in the output queue
//if the token at the top of the stack is an operator,
//pop the stack, and put that token in the output queue
while the stack is non-empty
pop the stack, and push that operator onto the output queue
The output queue now holds your tokens in postfix notation.
What I'm Giving You
Here are two files, Token.java and Operator.java. Operator extends Token. I'm giving you no other code; it will be your job to make the rest, organized however you like.
Token has a static method called tokenFactory(String). TokenFactory takes in a string (like "+", or "42"), and returns a Token. This Token may be a standard Token (that is, a number), or it may be an Operator casted up to a Token. It is not given to you set up to handle parentheses.
Your Queues and Stack should hold Tokens. How can you tell if a Token t is an Operator? Remember the instanceof operator?
if (t instanceof Operator) {
Operator o = (Operator)t;
//Operator stuff
}
What You'll Give Me
Turn in code such that running "java Project1" will allow me to do the following:
60 points: A full program which can read in RPN and print out the answer. Note RPN has no parentheses. Example:
taylor@albert:~/ShuntingYard$ java Project1 1 2 3 * + = 7 taylor@albert:~/ShuntingYard$ java Project1 1 2 * 3 + = 5
It should work with the following operators: + - * / ^.
90 points: Implement the full shunting yard algorithm, to convert infix notation that does NOT contain parentheses to RPN, and then print out the answer. Example:
taylor@albert:~/ShuntingYard$ java Project1 1 + 2 * 3 = 7 taylor@albert:~/ShuntingYard$ java Project1 1 * 2 + 3 = 5
100 points: Add in capability for parentheses. This may involve alteration of Token and/or Operator.
taylor@albert:~/ShuntingYard$ java Project1 4 * ( 2 + 3 ) = 20
Include a README telling me what step you completed.
Implement your own Stack and Queue, don't just use Java's.
Organization and clarity of your code matters. Plan your code before you write it. It shouldn't be all one big main method. Comment. Properly handle error cases.
The algorithm is not a hard one to implement, but you've never been given this little guidance before. It is a frequent occurrence in programming that you first make a program that works, and then make one that is clean and works stylistically. If that happens to you here, you should feel good about it.
Assumptions
You may assume that input consists solely of numbers, operations, and parentheses, that there is always a space between them, and the input always ends with an equals sign.
You may NOT assume that what comes in is correct infix notation (or, if you're working on step 1, postfix notation). In other words, if I pass in 1 + 2 3 =, does your program burst into flames, or handle this correctly? Find ways to send in awful input, and make sure your program works correctly.