Implement a binary search tree of positive integers (>0) in LC-3 assembly language. The binary search tree will be manipulated interactively using a menu system with single-letter commands:
P: print the contents of the tree, in order, one per line
I: insert a new value into the tree
R: remove a value from the tree
D: print the maximum depth of the tree
Q: quit the program
For the insert and remove commands, your program will need to read a positive (15-bit) hexadecimal integer value from the keyboard. Write code that will read a positive integer value from the keyboard, one digit at a time, stopping when Enter is pressed, and return it. Input validation and error checking are not required. You may either implement this as a subroutine or as a new TRAP at location x30 that will return the complete value in R0.
You will also need to be able to print positive integers. Again, write either a subroutine or a TRAP at location x31 that will print the value in R0 as a hexadecimal integer.
The rest of the program should use subroutines appropriately.
For the remove operation, you do not need to remove the node from the tree: it is enough to "mark" the node as deleted and ignore it when doing other operations (this is known as "lazy deletion").
For the insert operation, each new node in the tree will be added after the last one in memory, as represented by the LAST label. This will cause the tree to grow forward in memory; the stack of course will grow in the opposite direction. You do not need to implement stack safety, but be careful when testing!
Start out your tree with the data in a4q3-data.asm. You may add extra fields to the nodes, but keep those initial values and its tree structure. The nodes correspond to the following C struct:
A simple microwave oven control panel, described as follows.
The control panel has four buttons: time UP, time DOWN, START, and CANCEL. The oven can only cook food in for times that are increments of 1 minutes, up to 5 minutes (so: 1, 2, 3, 4, or 5 minutes). While the oven is cooking, there is a COUNTdown timer input that will decrement the time remaining by 1 minute until cooking is finished. The display will show one of the following messages: "READY", "1 MIN", "2 MINS", "3 MINS", "4 MINS", "5 MINS", or "DONE".
The panel will start out as "READY". The user can use the UP/DOWN buttons to increment/decrement the time in one-minute intervals up to 5 minutes, or back down to zero ("READY"), showing the selected time in the display. The CANCEL button will reset back to zero. When the user wants to start cooking, they can press START, and the oven will cook as long as there is at least 1 minute of time selected. The display will show the (ceiling of the) number of minutes remaining; e.g. if they are cooking for 2 minutes, it will show "2 MINS" for the first minute and "1 MIN" for the second. It will use the COUNT timer for decrementing. If the user hits CANCEL during cooking, it will automatically stop cooking and return to "READY". If cooking completes, the panel will display "DONE", and remain there until the user presses one of the buttons, which will behave the same way as they do in "READY".
in LC-3 assembly language, using an interrupt handler of your own design to read the control panel input and manage the FSM state. That is, the current state and transitions to the next state will all be handled within the interrupt handler.
Since the only input device available is the keyboard, and there is no hardware timer device in our LC-3 simulator, use the following keyboard equivalents:
a: time UP
z: time DOWN
(spacebar): COUNTdown timer
Since the main program doesn't have other work to do (there's no microwave), it should just busy-loop, printing the display value for the current state when it changes.
You may hard-code your states or use a transition table. Describe your approach in the comments at the beginning of your solution.