CSC 212: Programming with Data Structures

Homework 5: Arithmetic Expressions with Stacks

Due: Wednesday, Mar. 2, 11:59pm

Credit for this assignment: Nick Howe

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.

Command Line Arguments

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
java MyProgram
rsubmit lab1

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 second
then 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.

Command Line Arguments in Eclipse

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: You may also use this as the starting point for your own program (change the filename).

Postfix Computation

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.
For this assignment, you will use the generic Stack class you wrote during Lab 5, not the Java built-in Stack class.

Infix Computation

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.

  • 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, o1, then:
      • while there is an operator token, o2, at the top of the stack and either

        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,

        • pop o2 off the stack, onto the output list;
      • Finally push o1 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.

Iterator for Linked List

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) {

Hints and Comments

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:

java Calculate "(3+5)*2"
java Calculate "2/(1+8)*10"

Extra Credit

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.

To Submit

  • or, whichever one you did.
  • typescript showing that you have sufficiently tested your program using a range of inputs
  • readme.txt