StackMac

A stack machine executes programs consisting of commands that manipulate an internal stack. The stack is initially empty.

StackMachine.java

The commands are:

push N  ; push N onto the stack (N is any Double)

pop     ; removes top element from a stack

add     ; replace top two elements of the stack by their sum

mul     ; replace top two elements of the stack by their product

sub     ; replace top two elements of the stack by their difference: [a, b, ... ] => [a-b, ... ]

div     ; replace top two elements of the stack by their quotient: [a, b, ... ] => [a/b, ... ]

For example, the following program computes 2³:

(push 2, push 2, mul, push 2, mul)

The following types of exceptions are thrown by the commands:

stack empty

stack too short (not enough elements to complete the operation)

divide by 0

syntax error

Part 1

Draw a class diagram (or two) showing how you would design the stack machine. Don't forget to include commands and exceptions. Your design should be flexible enough to easily accommodate new types of commands that may be added in version 2.0.

Notes

·       Consider introducing classes such as StackMachine and Program.

·       Consider introducing a Command interface with an execute method that might throw an exception.

·       Consider introducing a class for each type of command. In other words, we are representing commands as objects.

·       Don't forget to show operations and attributes as needed.

Part 2

Implement a generic stack class for the stack machine:

class Stack<T> { ??? }

Notes

·       You will need to implement the following methods: push, pop, top, clear, and toString.

·       pop and top may throw EmptyStack exceptions

·       How will you store the elements in the stack? List? Set?

Part 3

Implement your design using your solution for part 2.

Notes

·       Executing arithmetic commands may throw ShortStack exceptions if there aren't at least two elements on the stack.

·       div may throw a DivByZero exception. Restore the stack before throwing this exception.

·       Consider making the execute method and stack in your StackMachine class static. Then, commands can make static references to the stack without needing to have an association to the stack machine.

·       The execute method of StackMachine should have separate catch clauses for each type of exception. For now it just prints the exception but in the future we could potentially have different strategies for each type of exception caught.

·       After the last command is execute the stack machine should print the stack.

·       Before the first command is execute the stack machine should clear the stack.

Part 4

Create and run StackMacTests.java

For example, suppose we want to compute f(x) = 5x² – 3. Here's one implementation:

Push(3.0)
Push(5.0)
Push(x)
Push(x)
// compute 5x^2
Mul
Mul
Sub // now subtract 3

Assume we want to figure out f(2). Here are some snapshots of the stack after each command:

[3]
[5 3]
[2 5 3]
[2 2 5 3]
[4 5 3]
[20 3]
[17]

Part 5

A parser converts strings into commands or throws an exception. Implement a parser for stack machine commands.

Part 6

A console for the stack machine perpetually runs a read-executes-print loop (REPL):

display a prompt

read a command from the keyboard

execute the command

display the result

The console catches any exceptions thrown, prints a useful error message, then resumes the REPL.

Here's a sample session:

-> clear
done
-> push 2
done
-> add
error: stack too short
-> push 3
done
-> mul
done
-> push 5
done
-> mul
done
-> top
30
-> quit
bye

Implement a console for the stack machine.