SE250:lab-8:rwan064
Introduction
Thanks to Jhor053 for fixing the problem with Graphviz and putting it on the wiki (Graphviz Solution)
Task 2
Construct an expression (calling mkNode) that, when passed to prefix tree, produces the output -(-(a b)) Graph the tree using tree to graph.
Code:
int main( void )
{
ParseTree* t = mkNode( '-', mkNode( '-', mkNode( 'a', 0 ), mkNode( 'b', 0 ), 0 ), 0);
tree_to_graph( t, "output.png" );
prefix_tree( t );
return 0;
}
Output:
$ make && ./parsetree.exe gcc -Wall parsetree.c -o parsetree.exe -(-(a b))
The graph:
<html> <img src="http://studwww.cs.auckland.ac.nz/~rwan064/lab8/task1.png" width="179" height="293" alt="Task 1 Graph" /> </html>
This task was quite easy since the example given on the lab handout was very similar.
Task 3
Now, construct an expression that produces ?(>(+(a b) c) *(z +(y b)) ?(=(a 2) -(x y) -(y x))) Hint: the ? is a ternary node.
Code:
ParseTree* t = mkNode( '?', mkNode( '>', mkNode( '+', mkNode( 'a', 0 ), mkNode( 'b', 0 ), 0 ), mkNode( 'c', 0 ), 0 ),
mkNode( '*', mkNode( 'z', 0 ), mkNode( '+', mkNode( 'y', 0 ), mkNode( 'b', 0 ), 0 ), 0 ),
mkNode( '?', mkNode( '=', mkNode( 'a', 0 ), mkNode( '2', 0 ), 0 ),
mkNode( '-', mkNode( 'x', 0 ), mkNode( 'y', 0 ), 0 ),
mkNode( '-', mkNode( 'y', 0 ), mkNode( 'x', 0 ), 0 ), 0 ), 0 );
Output:
?(>(+(a b) c) *(z +(y b)) ?(=(a 2) -(x y) -(y x)))
This task was much harder than task 1 since the expression we had to generate the tree for was much bigger. At first I couldn't figure out what part of the expression given in the question came after the colon in the ternary operator. But then I found that this was just seperated by a space since the colon wasn't in the tree expression in the question.
What I then did was figure out what code actually might produce this tree. I came with this answer: (a + b) > c ? ( y + b ) * z : ( a = 2 ) ? ( x - y ) : ( y - x )
After figuring this out it was quite easy to write the code to create the parse tree and also draw the graph in task 4.
Task 4
Draw a picture of what you expect the graph of this tree to look like, then graph the tree using tree to graph and compare the result with your prediction. Discuss any discrepancies in your report.
Graph:
<html> <img src="http://studwww.cs.auckland.ac.nz/~rwan064/lab8/task2.png" width="768" height="317" alt="Task 2 Graph" /> </html>
The graph actually came out the way i drew it, so no discrepancies there.
Task 5
The ? corresponds to the C conditional expression, which has the form cond ? e1 : e2. Why does the parse tree not need to include the colon (:)?
Task 6
Write a (recursive) function to evaluate a parse tree that consists of nodes that are either digits or the operators +, , * and /. For example, int v = eval( mkNode(’+’, mkNode(’1’,0), mkNode(’2’,0), 0) ); should set v to the value 3. Think about what to do if an operator does not have exactly two arguments, or if a digit has arguments. Justify your decisions in your report.
My first attempt:
int eval( ParseTree *t ) {
if ( (t->name >= '0') && (t->name <= '9' ) ) {
// it's a digit
return t->name - '0'; // Return that digit
}
else {
// it's an operator - must have exactly two arguments
int left = eval( t->arg[0] ); // evaluate left side
int right = eval( t->arg[1] ); // evaluate right side
// do the operation
switch ( t->name ) {
case '+':
return left + right;
break;
case '-':
return left - right;
break;
case '*':
return left * right;
break;
case '/':
return left / right;
break;
default:
// it's something else we don't want.
// what to do?
break;
}
}
return 0;
}
Test code:
ParseTree* t = mkNode( '*', mkNode( '3', 0 ), mkNode( '-', mkNode( '7', 0 ), mkNode( '2', 0 ) , 0 ), 0 ); printf( "eval " ); prefix_tree( t ); printf( " : %d\n", eval( t ) );
Output:
eval *(3 -(7 2)) : 15