Lab. 10  of CS 216

Due as specified on course webpage

Do  MIPS program calctree.a

Write a recursive function "evaluate"

The question file is calctree.a (Mars-friendly version: calctree.s)

It will call my function "parse" to set up an expression tree. The version you will load expects you to type in prefix (polish) notation. However, when you run mipsmark, specific text cases will be provided. (Case 0 is simply the number 12345).

evaluate will be called with the argument pointing to the root of the expression tree. Nodes will either contain an operator and 2 pointers, or 0 and one binary number. You can think of it this way:

struct interiornode 
{   char operator;  // but it's stored in a word
    struct node* left;
    struct node* right;   //subtree pointers, can be either interiornode or leafnode
}
struct leafnode
{   int flag = 0;	//instead of a char
    int value;		// the number from input
}
(You need not understand parse. For those interested, it is similar to polish.a in using a FSM to extract tokens. Since the input is prefix, it uses "recursive descent," when an operator is encountered, it calls itself to build subtrees for the left and right operands.)

Problem statement

    ## Write a function "evaluate" that will return the integer result
    ## of evaluating an arithmetic expression tree.
    ## Argument is a pointer to the root of the tree. Each node contains either
    ##  -- an operation: '+', '-', '*', or '/'
    ##        followed by two pointers (not null) to a subtree -OR-
    ##  -- the value 0, followed by an integer
    ##
    ##  -- in case of divide by 0, print DivError and return -99999

If you want to use macros

rename (either) file to calctree.am,  and use mapp calctree to produce calctree.a before using spim or mipsmark and submit cs216

If you test with Mars

Some small differences in the acceptable instruction formats, what I have observed so far, and the fixes, are: 

sub   $sp, 4    #requires 3 operands
sub   $sp, $sp, 4

To avoid these problems this week, get the file calctree.s, and then rename it to calctree.a

Polish notation (prefix)

Polish universities have always be short of money, so by tradition professors share offices. As a result, in the early 20th century, some got together and realized that infix notation caused ambiguities in longer expressions, AND this could be avoided by putting the operation first,  + 2 2 instead of 2 + 2.
as an example, what is 5 - 3 + 4? There are 2 possible trees representing this expression. By doing a preorder traverse of a tree, the difference is clear without needing ()'s.

It could be:

(5 - 3) + 4  	+ - 5 3 4 	= +6
5 - (3 + 4)  	- 5 + 3 4	= -2
 
Submission: Test with mipsmark and submit cs216 as usual.