Java Program for Stacks, Queues and Trees
Profs Akhter/Russell Project 2: Stacks, Queues, and Trees CS310 - Spring 2020 1 Project 2: Stacks, Queues, and Trees DUE: Sunday, March 1 st at 11:59pm Setup Download the project2.zip and unzip it. This will create a folder section-yourGMUUserName-p2. Rename the folder replacing section with the s001, s003, s004, s005 based on the lecture section you are in. Rename the folder replacing yourGMUUserName with the first part of your GMU email address. After renaming, your folder should be named something like: s001-krusselc-p2. Complete the readme.txt file (an example file is included: exampleReadmeFile.txt) Submission Instructions Make a backup copy of your user folder! Remove all test files, jar files, class files, etc. You should just submit your java files and your readme.txt Zip your user folder (not just the files) and name the zip section-username-p2.zip (no other type of archive) following the same rules for section and username as described above. o The submitted file should look something like this: s001-krusselc-p2.zip --> s001-krusselc-p2 --> JavaFile1.java JavaFile2.java JavaFile3.java ... Submit to blackboard. DOWNLOAD AND VERIFY WHAT YOU HAVE UPLOADED IS THE RIGHT THING. Submitting the wrong files will result in a 0 on the assignment! Basic Procedures You must: Have code that compiles with the command: javac *.java in your user directory. Have code that runs with the command: java SimpleCompiler [filename] [true|false] You may: Add additional methods and variables, however these methods must be private. Add additional nested, local, or anonymous classes, but any nested classes must be private. You may NOT: Make your program part of a package. Add additional public methods, variables, or classes. You may have public methods in private nested classes. Use any built in Java Collections Framework classes in your program (e.g. no LinkedList, ArrayList, etc.). Create any arrays anywhere in your program, except the toArray() method of the CallStack class. You may not call the toArray() method of the stack to bypass this requirement. Alter any method signatures defined in this document of the template code. Note: “throws” is part of the method signature in Java, don’t add/remove these. Alter provided classes or methods that are complete (Node, runCompiler() in SimpleCompiler, etc.). Add any additional import statements (or use the “fully qualified name” to get around adding import statements). Add any additional libraries/packages which require downloading from the internet. Grading Rubric Due to the complexity of this assignment, an accompanying grading rubric pdf has been included with this assignment. Please refer to this document for a complete explanation of the grading. Profs Akhter/Russell Project 2: Stacks, Queues, and Trees CS310 - Spring 2020 2 Overview By the end of this project, you will have defined a stack class, a binary search tree (more information below), and a simple compiler that takes as input a postfix program and not only compiles it, but also evaluates it and prints the output!. You will use file I/O to read programs from files and evaluate them using your “SimpleCompiler”. If you’re unfamiliar with postfix notation, the following programs (and their more familiar infix versions) are shown below: Postfix Program Equivalent Infix Program Output Notes 3 2 + 3 + 2 This program takes 3 and 2, then adds them. 3 2 + print print 3 + 2 5 This program takes the output from “3 2 +” and prints it. Print is an operator with one parameter. x 3 2 + = x print x = 3 + 2 print x 5 This program adds 3 and 2, then stores it in a variable called x. Later, it is asked to print x. How the SimpleCompiler Works When you have completed the assignment, your “SimpleCompiler” will have two modes: normal and debug. In normal mode, the SimpleCompiler will do all the computations and display the output of any print statements. In debug mode, the SimpleCompiler will perform one “step” at a time. The SimpleCompiler is run in the following ways: java SimpleCompiler [path-to-program] [debug-mode-true|false] For example, when I run the SimpleCompiler without debug mode on one of the provided sample programs (sample1.txt in this case), I type and see the following: > java SimpleCompiler ../prog/sample1.txt false Program: 1 2 + 3 4 - 5 6 + 4 2 / * * + print -19 And when I run the SimpleCompiler with debug mode, I type and see the following: > java SimpleCompiler ../prog/sample1.txt true Program: 1 2 + 3 4 - 5 6 + 4 2 / * * + print ######### Step 1 ############### ----------Step Output---------- ----------Lookup BST--------- ----------Call Stack-------- 1 ----------Program Remaining---- 2 + 3 4 - 5 6 + 4 2 / * * + print Press Enter to Continue When I press enter I see: ######### Step 2 ############### ----------Step Output---------- ----------Lookup BST--------- ----------Call Stack-------- 1 2 ----------Program Remaining---- + 3 4 - 5 6 + 4 2 / * * + print Profs Akhter/Russell Project 2: Stacks, Queues, and Trees CS310 - Spring 2020 3 Press Enter to Continue The debug mode and printing have already been done for you, but your job will be to build the supporting data structures and processing the program. You will do this in stages: Step 1: Read the input from a file into a queue (a linked list queue!) Step 2: Create a stack to support the SimpleCompiler’s computations (a linked list stack!) and process simple math programs (e.g. “3 2 + print”). Step 3: Create a binary search tree (more information below) which would serve as a symbol table to support the SimpleCompiler when looking up variable names and processing math/printing with variables. More information on these stages is given in the later parts of this document. tl;dr You’re building a postfix compiler with a debug-mode command. Commands for running the compiler are above. Postfix Program Processing with a Stack and No Variables The basic procedure is as follows: 1. Treat the incoming program as a “queue” (the left side in the front of the queue). 2. When you encounter a value, push it on the stack (i.e., Call Stack). 3. When you encounter an operator, pop what you need off the stack and perform the operation. 4. Depending on the operator, you might need to push the result back on the stack. Example: Input Queue Current Symbol Call Stack Notes 3 2 + 4 2 - * 1 + print We start with our input in a queue and nothing on the stack. 2 + 4 2 - * 1 + print 3 We examine the first input in the queue and discover it is a value (not an operator), so we will put it on the stack. + 4 2 - * 1 + print 2 3 The next input is also a value, so we will put it on the stack (top of the stack is to the right). 4 2 - * 1 + print + 3 2 Now we have an operator. Addition takes two values, so we pop twice from the stack and add those two. The result of addition goes back on the stack, the “+” sign is thrown away. 2 - * 1 + print 4 5 Value, goes on the stack. - * 1 + print 2 5 4 Value, goes on the stack. * 1 + print - 5 4 2 Subtraction operator, pop twice, subtract, push result. 1 + print * 5 2 Multiplication operator, pop twice, multiply, push result. + print 1 10 Value, goes on the stack. Print + 10 1 Addition operator, pop twice, add, push result. print 11 The print operator takes only one value, so we pop once and print that value. Additionally, printing does not push anything new onto the stack! All done, nothing in queue! Note: Chapter 11 of your textbook has some useful information about postfix calculations if you want more info! tl;dr The compiler will take programs like “1 2 + print” and print the number 3. See Chapter 11 for some more info. Postfix Program Processing with a Stack and Variables The basic procedure is as follows: 1. Treat the incoming program as a “queue” (the left side in the front of the queue). 2. When you encounter a non-operator, push it on the stack. Profs Akhter/Russell Project 2: Stacks, Queues, and Trees CS310 - Spring 2020 4 3. When you encounter an operator, pop what you need off the stack. If you pop a variable off the stack, look it up in the “LookUpBST” which is a binary search tree. Perform the operation with the values you’ve discovered. 5. Depending on the operator, you might need to push the result back on the stack. Example: Input Queue Current Symbol Call Stack LookUp BST Notes x 3 2 + = y 4 = x y + print We start with our input in a queue and nothing on the stack. 3 2 + = y 4 = x y + print x x is not an operator, so push it on the stack. 2 + = y 4 = x y + print 3 x Not an operator, goes on the stack. + = y 4 = x y + print 2 x 3 Not an operator, goes on the stack. = y 4 = x y + print + x 3 2 Operator; addition takes two values, pop twice and push