Course Links

Exercises

Resources

External

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.

Specifications

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.

For details on reading command line arguments, see the tutorial. (You don't need to complete the activity.)

Tokenization

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, if you wish.

Postfix Computation

The simplest possible version of this assignment (which will receive a passing grade, 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:

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 (ignoring operator associativity) 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, just use a LinkedList<Object> and use the addLast method to add things to it.

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.

An alternate way to handle the issue would be to replace the output queue with a string (or StringBuilder). Tokens sent to the output by the shunt-yard algorithm would be converted to strings and appended. When the shunt-yard algorithm completes the string will contain the entire expression in postfix order. One advantage of this approach is that a new scanner can be built from the postfix string, and the existing postfix code can be used verbatim. On the other hand, there is some inefficiency in having the program convert multiple times between strings and other values.

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 without making too many changes.

The pseudocode above will work for the operators + - * and / but not ^ (exponentiation). While the first four operators are left-associative, the latter is right-associative and needs slightly different treatment (described in the the full pseudocode under the wikipedia link) -- but it boils down to using less than in the precedence comparison rather than less than or equal to. What does left-associative mean? We interpret 1+2+3 as (1+2)+3. On the other hand, 2^1^2 is interpreted as 2^(1^3) because ^ is right-associative. For full credit your program should implement the complete shunt-yard algorithm including associativity.

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