Homework 4
[Base Code]Due Date
This assignment is due before midnight on Monday, June 27th. Please refer to the page on electronic submission for more information. If you choose to use a single late day, the deadline becomes extended until 11:59pm on June 28th (so it extends the deadline by 24 hours). After that, each additional late day will extend the deadline an additional 24 hours. Remember that you can use at most 2 late days on this assignment.Programming
(60 Points) Calculator (Mini-Compiler/Interp): For this program, you will be writing a mini-interpreter for a very simple language. You have two tasks in this assignment: to build a data structure and to build a program that takes another program as input and execute it.Fortunately, the language is very simple: you can only add using "Reverse Polish Notation" (RPN). The notation allows you to specify a long series of computations using postfix operations. This simply means that operators come AFTER their arguments. For example: 3 5 + means 3 + 5, which is 8. Parentheses are not needed to write any complex expression: it can be controlled by placement of the operators. For example, 3 4 2 + - means that 4 + 2 is to be computed first, then 3 - 6 is to be executed producing -3. Keep in mind you ONLY have to worry about + signs for this assignment (not -).
The trick to executing this is to move from left to right. Each time you see a number, push it onto a stack structure (place it on top of a stack. If you see an operator, pop the top two items on the stack and do the operation on them. Then place the result back on the stack. Try it with the example above. The stack delays using the first 3 until the 4 and 2 are added. I will provide some additional links on this topic shortly.
I have already taken care of input processing for you. Users will write their program on the command line:
gcc -Wall -o calculator calculator.c mathreader.c
./calculator 3 4 + 2 +
Result: 9
You will want to use the the included code to write this assignment. It will process the inputs and simply return the next token (operator OR number) on demand. See the .h file for details.
Your job is to implement the stack structure. This is very much like a linked list structure, except with two simple operations:
- push: STACK *push(STACK *st, int value), which takes in the current stack and adds an int to the very top. You do NOT have to have this function as part of your code as long as you use a linked structure that resembles a stack. Full code for stacks is given in the Kernighan and Ritchie book.
- pop: MATHTERM *pop(STACK **pst), which takes in the current stack and removes the top element (and returns it). I pass a stack pointer pointer because I intend to modify the pointer itself when I remove the top element (and I can't return two things). Again, if this declaration confuses you, you may "pop" from the stack directly from your main function. You may write all of this program as part of a single main (leaving intact my code from mathreader.c in its own file).
This makes the rest of the program simple: just follow these guidelines:
- If you read a number from input, push it to the stack.
- If you read an operator, pop two items, do the appropriate operation on them, and PUSH THE RESULT ON THE STACK.
- When you run out of inputs, your answer is on top of the stack.
- If you ever end up trying to dereference a NULL pointer, you must print "Parse Error" and halt the program.
In essence, this code is not particularly long. If you can implement the stack similarly to the list (except only operating on the FIRST element), then the above instructions are a very short loop using the functions I've given you.
Written
(40 Points) Tree Climbing: Suppose you have a large tree in your backyard. It starts with a large, single, mammoth trunk and has branches that divide upwards. This tree is special in that after each meter in height, each branch splits into two branches (and they continue to grow). All branches continue growing in this fashion until they end at the top of the tree bearing a single large fruit.Suppose you want all of this fruit. And are willing to climb the tree to get it.
Say that climbing the tree is not the difficult and requires no work. Freeing the fruit from the tree, however, requires time. Given a tree of height n, how much work will you need to do in order to pick all of the fruit on the tree? Define your unit of work and show how the work grows as the height of the tree grows.
Now, suppose there is another tree whose branches do not always grow to the full height of the tree -- instead they stop early and bear fruit. While you can see that collecting fruit from this tree will require less time than the perfect tree above, does this fact change the worst-case amount of time to pick all the fruit? On average, how long will it take to pick all the fruit from the tree? Use only the amount of information I've given you and bound the average case (note I haven't told you the probability that a branch divides or stops and bears fruit).
Now, suppose I tell you that each branch has a 50% chance of stopping after each meter of growth. Give some intuition (doesn't have to be rigorous) about whether this changes the complexity of this problem (does it change the fundamental growth-rate function)?
This can be submitted as paper or in a file called hw4b.txt in electronic submission. If you submit electronically, only use plain text files (or ask me if you want to use another format). For paper, you can hand it to me at class. For late submissions, please ask me if you need to submit paper.
Grading
Grading will be based on correctness as mentioned in each problem. Read each problem very carefully to ensure that you've completed all that is required. A programmer needs to be able to read a paragraph description and implement the requirements rigorously. (80%)COMMENTS and description will account for 10% of each assignment. You must use comments to describe in a succinct fashion what is happening in your code. Also, name, id, etc should be placed in a comment at the very top of all your files.
Your code must be ANSI compliant. If you follow what the books say, this should not be an issue, but bad habits are known to pop up at this stage. (5%)
The last 5% is based on elegance/efficiency/style. For this project, efficiency won't be taken heavily, but formatting your code as we've been doing will be. Don't write code that completely defies any reasonable formatting convention (even if it is correct). For example, don't do things like:
int main(void) { int x;int y; int z; int c,d;c=5; if (c == 1) { d = 7; c = 4; } return 0; }
You are submitting two files: calculator.c and hw4b.txt, each with a description of how your code works either in comments or in a separate README file. Don't submit binaries (like a.out). Place your .c files (and perhaps README file as plain text) in a directory on the cunix machine and see the submission instructions. For this assignment, a README file is recommended to describe exactly what you completed for both assignments.