Lab 5A: Stacks Q1 Fun with stacks 4 Points Consider a generic Stack class implemented using...

Transcribed Image Text:

Lab 5A: Stacks Q1 Fun with stacks 4 Points Consider a generic Stack class implemented using a linked list with the following methods: public boolean isEmpty(), which returns true if and only if the stack is empty; public T pop() throws StackUnderflowException, which removes and returns the top element of the stack (if the stack is empty, it throws StackUnderflowException); public T peek () throws StackUnderflowException, which returns the top element of the stack (but does not remove it; it throws an exception if the stack is empty); public void push (T element), which pushes an element onto the stack Predict the output of each of the following code snippets Q1.1 1 Point A. B. Stack s = new Stack (); s.push(5); s.push(50); try{ What is the output? s.push(30); } catch (Exception e) { System.out.println("An exception was thrown"); } D. System.out.println(s.pop()); System.out.println(s.pop()); System.out.println(s.peek()); 5 50 30 50 5 30 C. 50 An exception was thrown 50 5 An exception was thrown O A OB OC OD Q1.2 1 Point A. B. Stack s = new Stack (); s.push(5); try{ What is the output? System.out.println(s.peek()); } catch (Exception e) { System.out.println("An exception was thrown"); } C. System.out.println(s.pop()); System.out.println(s.isEmpty()); s.push(10); s.push(43); s.push(s.pop()); 5 True 10 D. 5 False 10 5 True 43 OA OB OC D 5 True An exception was thrown Q1.3 1 Point Stack s new Stack (); try { B. A. What is the output? } catch (Exception e) { System.out.println("An exception was thrown"); } 10 5 s.push(5); s.push(10); C. while (!s.isEmpty()) System.out.println (s.peek()); D. } 10 10 10 ... // infinite loop. // nothing is output OA OB OC OD { 10 5 An exception was thrown Q1.4 1 Point Stack s = new Stack (); try { } s.push(5); s.push(9); s.push(3); s.push(s.pop() + s.pop()); System.out.println(s.peek()); } catch (Exception e) { System.out.println("An exception was thrown"); } What is the output? O 12 O 14 O 3 An exception was thrown Q2 Stack Implementation of Postfix Operations 3 Points Postfix notation: operators are placed after operands. Terminology: Operands: numbers Operators: + -/* Study the example below: An operator acts on the two values to its left, where a value may be either a number in the original expression or result of a previous operator. Note the order of the operands (further left -> operator -> closer left). This matters to - and /. Infix Postfix 53 A / B (214) x 23 Study the algorithm to evaluate postfix expressions using a stack. 1. Scan the expression. 2. When we see an operand, push it onto the stack. 3. When we see an operator, pop two values off of the stack, and apply the operator to them, then push the result back onto the stack. 4. In the end, if we have exactly one value on the stack, that is our answer. See the worked example below for the expression: 5 4 - 7 * push(5) push(4) - sign encountered pop() 4 pop() 5 53- A B / 24 23 * push(1) 5-4 = 1 push(7) *sign encountered 7 pop() 1 push(7) 1*7=7 Ans: 7 Q2.1 1 Point Evaluate the expression using a stack: 5 7 + 6 2 Enter your answer here Save Answer Q2.2 1 Point Evaluate the expression using a stack: 4 5 7 2 + Enter your answer here Save Answer Q2.3 1 Point Evaluate the expression using a stack: 4 2 3 5 1 Too many operands-stack overflow Not enough operands-stack underflow Save Answer I + * * + * Q3 Implementing Stack using Linked List 8 Points Please download the Stack starter code. In this section, you will implement a generic Stack class implemented using a linked list. Refer to the LLNode class in the starter code. Note that both class variables are private so you cannot access them directly. You must use the get and set methods defined for you. Also, assume that the StackUnderflowException class has been defined such that it inherits Java's Exception class. Your task is to implement four methods in the generic class LinkedListStack . public class Linked ListStack { private LLNode head; // constructor public Linked ListStack() { head = null; } Q3.1 1 Point public boolean isEmpty() { // TODO: return true if the stack is empty, false otherwise // Hint: You do not need more than 1 line of code Enter your answer here Save Answer Q3.2 2 Points // head of linked list, also stack top pointer public void push(T element) { // TODO: push an element to the stack Enter your answer here Save Answer Q3.3 2 Points public T peek () throws StackUnderflowException { // TODO: return the top element of the stack (but do NOT remove it). // Throw StackUnderflowException if stack is empty Enter your answer here Save Answer Q3.4 3 Points public T pop() throws StackUnderflowException { // TODO: remove and return the top element of the stack // Throw StackUnderflowException if stack is empty Enter your answer here Save Answer Lab 5A: Stacks Q1 Fun with stacks 4 Points Consider a generic Stack class implemented using a linked list with the following methods: public boolean isEmpty(), which returns true if and only if the stack is empty; public T pop() throws StackUnderflowException, which removes and returns the top element of the stack (if the stack is empty, it throws StackUnderflowException); public T peek () throws StackUnderflowException, which returns the top element of the stack (but does not remove it; it throws an exception if the stack is empty); public void push (T element), which pushes an element onto the stack Predict the output of each of the following code snippets Q1.1 1 Point A. B. Stack s = new Stack (); s.push(5); s.push(50); try{ What is the output? s.push(30); } catch (Exception e) { System.out.println("An exception was thrown"); } D. System.out.println(s.pop()); System.out.println(s.pop()); System.out.println(s.peek()); 5 50 30 50 5 30 C. 50 An exception was thrown 50 5 An exception was thrown O A OB OC OD Q1.2 1 Point A. B. Stack s = new Stack (); s.push(5); try{ What is the output? System.out.println(s.peek()); } catch (Exception e) { System.out.println("An exception was thrown"); } C. System.out.println(s.pop()); System.out.println(s.isEmpty()); s.push(10); s.push(43); s.push(s.pop()); 5 True 10 D. 5 False 10 5 True 43 OA OB OC D 5 True An exception was thrown Q1.3 1 Point Stack s new Stack (); try { B. A. What is the output? } catch (Exception e) { System.out.println("An exception was thrown"); } 10 5 s.push(5); s.push(10); C. while (!s.isEmpty()) System.out.println (s.peek()); D. } 10 10 10 ... // infinite loop. // nothing is output OA OB OC OD { 10 5 An exception was thrown Q1.4 1 Point Stack s = new Stack (); try { } s.push(5); s.push(9); s.push(3); s.push(s.pop() + s.pop()); System.out.println(s.peek()); } catch (Exception e) { System.out.println("An exception was thrown"); } What is the output? O 12 O 14 O 3 An exception was thrown Q2 Stack Implementation of Postfix Operations 3 Points Postfix notation: operators are placed after operands. Terminology: Operands: numbers Operators: + -/* Study the example below: An operator acts on the two values to its left, where a value may be either a number in the original expression or result of a previous operator. Note the order of the operands (further left -> operator -> closer left). This matters to - and /. Infix Postfix 53 A / B (214) x 23 Study the algorithm to evaluate postfix expressions using a stack. 1. Scan the expression. 2. When we see an operand, push it onto the stack. 3. When we see an operator, pop two values off of the stack, and apply the operator to them, then push the result back onto the stack. 4. In the end, if we have exactly one value on the stack, that is our answer. See the worked example below for the expression: 5 4 - 7 * push(5) push(4) - sign encountered pop() 4 pop() 5 53- A B / 24 23 * push(1) 5-4 = 1 push(7) *sign encountered 7 pop() 1 push(7) 1*7=7 Ans: 7 Q2.1 1 Point Evaluate the expression using a stack: 5 7 + 6 2 Enter your answer here Save Answer Q2.2 1 Point Evaluate the expression using a stack: 4 5 7 2 + Enter your answer here Save Answer Q2.3 1 Point Evaluate the expression using a stack: 4 2 3 5 1 Too many operands-stack overflow Not enough operands-stack underflow Save Answer I + * * + * Q3 Implementing Stack using Linked List 8 Points Please download the Stack starter code. In this section, you will implement a generic Stack class implemented using a linked list. Refer to the LLNode class in the starter code. Note that both class variables are private so you cannot access them directly. You must use the get and set methods defined for you. Also, assume that the StackUnderflowException class has been defined such that it inherits Java's Exception class. Your task is to implement four methods in the generic class LinkedListStack . public class Linked ListStack { private LLNode head; // constructor public Linked ListStack() { head = null; } Q3.1 1 Point public boolean isEmpty() { // TODO: return true if the stack is empty, false otherwise // Hint: You do not need more than 1 line of code Enter your answer here Save Answer Q3.2 2 Points // head of linked list, also stack top pointer public void push(T element) { // TODO: push an element to the stack Enter your answer here Save Answer Q3.3 2 Points public T peek () throws StackUnderflowException { // TODO: return the top element of the stack (but do NOT remove it). // Throw StackUnderflowException if stack is empty Enter your answer here Save Answer Q3.4 3 Points public T pop() throws StackUnderflowException { // TODO: remove and return the top element of the stack // Throw StackUnderflowException if stack is empty Enter your answer here Save Answer