2. (a) You are given the following requirements for a stack abstract data type: (1) It must be possible to make a stack empty. (2) It must be possible to push a given element on to a stack. (3) It must be possible to pop the topmost element from a stack. (4) It must be possible to determine the depth of a stack. Write a contract for a homogeneous stack abstract data type. Express your contract in the form of a Java generic interface, with a comment specifying the expected behaviour of each method. [Notes] public interface Stack { // A Stack object represents a homogeneous stack with elements of // type E. public void clear (); // Make this stack empty. public void push (E x); // Add element x to the top of this stack. public E pop (); // Remove and return the topmost element of this stack. public int depth (); // Return the number of elements in this stack. } [1 mark for class declaration + 1 mark for each method declaration and comment.] Ad (b) Briefly describe a possible representation for a stack. [Notes] For a bounded stack (depth cap), use a variable depth and an array elems of length cap. Store the elements in elems[0...depth-1], with the topmost element in elems[depth-1]. Alternative answer: For an unbounded stack, use a singly-linked list together with a variable depth. Store one element in each node, with the topmost element in the first node. [3 marks for any sensible answer, -1 mark for unclear explanation.] [3] (c) A stack machine has instructions that push integers on to a stack and pop integers off the stack. A typical stack machine has instructions such as those summarised in Box 2A. A stack machine makes it easy to evaluate complicated expressions. Any integer expression can be translated to stack machine code. After the code is executed, the stack will contain a single integer, which is the result of evaluating the expression. For example: Expression Stack machine code LOAD 4; LOAD 5; LOAD 6; MULT; ADD Expected result +34 4+ (5 6) 2- (3 4)+5 (2-3) 4+5 LOAD 2; LOAD 3; LOAD 4; MULT; SUB; LOAD 5; ADD LOAD 2; LOAD 3; SUB; LOAD 4; MULT; LOAD 5; ADD -5 +1 Draw diagrams showing the contents of the stack after executing each instruction in the stack machine code "LOAD 4; LOAD 5; LOAD 6; MULT; ADD". Assume your stack representation of part (b). [Unseen problem] Assuming the array representation with cap = 8: 0 1 2 3 4 5 After LOAD 4: elems 4 After LOAD 5: elems 4 5 After LOAD 6: elems 4 5 6 After MULT: elems 4 30 After ADD: elems 34 [-1 mark for each conceptual error.] 1) 16 7 depth 1 depth 2 depth 3 depth 2 depth 1 [4] Assume that the stack-machine instructions are represented by the Java class of Box 2B. In terms of your stack contract of part (a), implement the following method: static int execute (Instruction [] instrs); // Execute the stack-machine code instrs, and return the result. [Unseen problem] static int execute (Instruction[] instrs) { Stack s = new ArrayStack (); for (Instruction instr : instrs) { switch (instr.opcode) { case LOAD: {s.push(instr. operand); break; } case ADD: { int right = s.pop(); int left = s.pop(); s.push (left + right); break; } case SUB: { int right = s.pop(); int left = s.pop(); - - s.push (left right); break; } } } case MULT: { int right = s.pop(); s.pop(); return s.pop(); int left = s.push(left * right); break; } [-1 mark for each conceptual error, or 2 marks if severe.] Act Go to [8] 1007 Instruction LOAD i ADD SUB MULT Effect Push the integer i on to the stack. Pop two integers off the stack, add them, and push the result back on to the stack. Pop two integers off the stack, subtract the topmost integer from the second- topmost integer, and push the result back on to the stack. Pop two integers off the stack, multiply them, and push the result back on to the stack. Box 2A Summary of stack machine instructions. public class Instruction { } // Each Instruction object represents a stack machine instruction. public byte opcode; // LOAD, ADD, SUB, or MULT public int operand; // used only if opcode is LOAD public static final byte LOAD 0, ADD = 1, SUB = 2, MULT = 3; Box 2B Representation of stack machine instructions.