L10

Due by the end of this meeting

Starter Files:

SUBMIT   /   Submission Summary

Postfix Calculator (Stacks)

In this lab you are going to implement a postfix calculator using a Deque for a stack.

Download the starter program Postfix and run it. It then repeatedly prompts the user for a postfix expression, stopping when the input is empty.

At present it produces 0.0 as the result for every expression. You need to revise it so that it evaluates each of those expressions. Allow double values for the numbers.

A postfix expression is one where the operators follow the numbers they apply to. For example: 

15 6 +
is the postfix version of 15 + 6, and 
15 6 + 7 *
is the postfix version of (15 + 6) * 7. (Note that the postfix version doesn't use any parentheses -- it doesn't need to!)

Sometimes multiple numbers will appear before any operator. For example: 

15 6 7 + *
is the postfix version of 15 * (6 + 7).

The method for evaluating a postfix expression is always the same:

So for the expression 
15 6 7 + *
the numbers 15, 6 and 7 get pushed onto the stack (in that order), then the + pops the top two numbers (7 and 6), adds them (to get 13), then pushes 13 onto the stack (so now the stack contains 15 and 13). Then the * pops the 13 and 15 off the stack, multiplies them (to get 195), which it pushes back onto the stack.

When we get to the end of an expression, the value of the expression is the number left on the stack. (There should be exactly one number left on the stack.)

Your program must implement the four basic operators: +, -, * and /. The program reports each operation as it's carried out.

>>> 15 6 7 + * 6.0 + 7.0 = 13.0 15.0 * 13.0 = 195.0 Result: 195.0

Your program must notice if the expression has too many operators or numbers:

>>> 1 + 2 Error: Too many operators Result: 0.0 >>> 1 2 3 * Error: Too many numbers Result: 0.0

Unknown operators should be treated as +:

>>> 10 2 % Warning: Unknown operator % treated as + 10.0 % 2.0 = 12.0 Result: 12.0 >>> 1 2 3 +* Warning: Unknown operator +* treated as + 2.0 +* 3.0 = 5.0 Error: Too many numbers Result: 0.0

Notes

Use java.util.ArrayDeque for the stack. Do not use java.util.Stack, or any other kind of stack. Remember to use only the Stack operations -- push, pop and peek -- and utility operations -- such as size, clear and isEmpty. You will be penalized for using other Deque operations.

The right-hand operand comes off the stack before the left-hand one. Make sure you do the - and / operations the right way round:

>>> 10 3 - 10.0 - 3.0 = 7.0 Result: 7.0
>>> 10 4 / 10.0 / 4.0 = 2.5 Result: 2.5

Submit this/these files:

SUBMIT   /   Submission Summary