[Solved] CS061 Lab 9-Stacks

High Level:A stack is a data structure that stores items in a LIFO order L ast I n F irst O ut.In other words, the last item you put onto your stack is the first item you can take out. Unlike an array,you cannot take items out of a stack in any order you like, nor can you put items into a stack in any orderyou like.LIFO Analogy:Imagine that you had a Pez dispenser. Each candy is inserted into the Pezdispenser and falls to the bottom. Whenever you want to extract a piece of candyfrom the dispenser, you can only take the one on top (that last one that you putin). You cannot get the first piece of candy back without taking the second piece ofcandy out of the dispenser first. Thus, the last piece of candy that you put in to thedispenser must be the first piece of candy you take out .Visual Stack Example:Below is a numerical example. Lets say you are given the numbers {17, 314, 8, 42}. You can PUSH theseonto a stack in the manner depicted below.Now that your stack has a bunch of items in it, you can take them out by calling POP on thestackremember, they have to come out in LIFO order. Note that the order of items popped is always thereverse of the PUSH order . Popping is visually depicted below.Notice how the PUSH order was {17, 314, 8, 42} but the POP order was {42, 8, 314, 17}.Important Stack Lexicon:Definition: OverflowTo overflow a stack is to try to PUSH an element onto it when it is full.Definition: UnderflowTo underflow a stack is to try to POP an element off of it when it is empty.3. 2 How to implement a stack in LC3:The easiest way to implement a stack that checks for overflow and underflow is as follows:Specs for a stack located from xA001 to xA005 (i.e. a total of 5 slots) A stack structure consists of three members:1. BASE: A pointer to the bottom of the stack (well use R4) actually, to 1 slot below the lowestavailable address , in this case BASE = xA0002. MAX: The highest available address in the stack (R5), in this case xA0053. TOS: A pointer to the current T op O f the S tack (R6);in this case, for the empty stack, TOS starts at BASE = xA000 To PUSH a value onto a stack (we will push the value in R0) : Verify that TOS is less than MAX (if not, print Overflow message & quit) Increment TOS Write the desired value to the Top Of Stack: Mem[TOS] <- (R0) To POP a value off a stack (we will capture it in R0) : Verify that TOS is greater than BASE (if not, print Underflow message & quit) Copy the value at the Top Of Stack to the destination register: R0 <- Mem[TOS] Decrement TOSNote that when pushing, we first increment , then write;when popping, we first read , then decrement.Note that you dont have to actually remove anything when you POP; all you have to do is decrementTOS after reading. Any PUSH you do later will simply overwrite whatever was there previously.3.3 Setup/Initialization of a 5-slot stack: Set R4 = BASE to xA000 Set R5 = MAX to xA005 Set R6 = TOS to BASE = xA000 (i.e. stack starts out empty)Exercise 1: Stack PUSH1. Write the following subroutine:;; Subroutine: SUB_STACK_PUSH; Parameter (R0): The value to push onto the stack; Parameter (R4): BASE: A pointer to the base ( one less than the lowest available; address) of the stack; Parameter (R5): MAX: The highest available address in the stack; Parameter (R6): TOS (Top of Stack): A pointer to the current top of the stack; Postcondition: The subroutine has pushed (R0) onto the stack (i.e to address TOS+1).; If the stack was already full (TOS = MAX), the subroutine has printed an; overflow error message and terminated.; Return Value: R6 updated TOS;Test Harness:To ensure that your subroutine works, write a short test harness. Make sure your stack stores the valuesas expected in memory and prints an overflow error message as necessary.Exercise 2: Stack POPWrite the following subroutine:;; Subroutine: SUB_STACK_POP; Parameter (R4): BASE: A pointer to the base ( one less than the lowest available; address) of the stack; Parameter (R5): MAX: The highest available address in the stack; Parameter (R6): TOS (Top of Stack): A pointer to the current top of the stack; Postcondition: The subroutine has popped MEM[TOS] off of the stack and copied it to R0.; If the stack was already empty (TOS = BASE), the subroutine has printed; an underflow error message and terminated.; Return Values: R0 value popped off the stack; R6 updated TOS;Test Harness:Add a call to the POP subroutine to your test harness from exercise 1. Make sure your TOS value updatesas expected, and that overflow/underflow error messages print appropriately.Exercise 3: Reverse Polish CalculatorReverse Polish Notation (RPN) is an alternative to the way we usually write arithmetic expressions. Whenwe want to add two numbers together, we usually write, 12 + 7 and get 19 as a result. In RPN, toexpress the same thing, we write, 12 7 + and get 19 i.e. we first specify the two operands, then theoperation to be performed on them. In this exercise, you will implement a Reverse Polish NotationCalculator that performs a single operation, multiplication.Subroutine (write me!);; Subroutine: SUB_RPN_MULTIPLY; Parameter (R4): BASE: A pointer to the base ( one less than the lowest available; address) of the stack; Parameter (R5): MAX: The highest available address in the stack; Parameter (R6): TOS (Top of Stack): A pointer to the current top of the stack; Postcondition: The subroutine has popped off the top two values of the stack,; multiplied them together, and pushed the resulting value back; onto the stack.; Return Value: R6 updated TOS address;Your main program must do the following:1. Prompt user for a single digit numeric character, and convert it to a number in R0 (if you wish, youcan invoke a helper s/r to do this) ; then invoke PUSH s/r to push R0 onto stack.2. Repeat, to get second operand & push it onto stack.3. Prompt for the operation symbol (in this case, a *). You can simply discard it once received, sincemultiplication is the only operation we are implementing.4. Call the SUB_RPN_MULTIPLY subroutine to pop the top two values off the stack, multiply them,and push the result back onto the stack. if you wish, you may use a helper s/r to do the actual multiplication it only needs to handle themultiplication of two single digit numbers.5. POP the result off the stack and print it out to the console in decimal format. use a helper s/r to do the output: pass in the number in R0, and print it as numeric characters; itonly has to be able to print 1 or 2 digit numbers. (You can use your lab 7 subroutine to do this).Hints: You will need the following subroutines to get the job done: SUB_STACK_PUSH (exercise 1) SUB_STACK_POP (exercise 2) SUB_RPN_MULTIPLY SUB_MULTIPLY (optional) SUB_GET_NUM (optional) SUB_PRINT_DECIMAL (use the subroutine from lab 7) You do not need to implement any input validation we will test only with single-digit numbers. As in assignment 5, you will have nested subroutine invocations make sure you get the registerbackup & restore exactly right!!