SE250:lab-8:dcho040
check out the error
- parsetree.c line 111 'strcimp' to 'strcmp'
- change the function 'error' and 'expect' because 'error' function is used in 'expect' function so have to define earlier.
task2
expression : -(-(a b))
fomula : -(a-b)
code : ParseTree* test = mkNode('-',mkNode('-',mkNode('a',0),mkNode('b',0),0),0);
prefix_tree(p);
char filename[] = "task2.jpg";
tree_to_graph(p, filename);
result : -(-(a b))
graph <html> <img src='http://daniel.hosting.paran.com/task2.jpg'> </html>
task3
expression : ?(>(+(a b) c) * (z + (y b)) ?(=(a 2) - (x y) -(y x)
fomula : a+b>c ? z*y+b : (a==2 ? z-y : y-x)
code : ParseTree* first = mkNode('>', mkNode('+', mkNode('a', 0), mkNode('b', 0), 0), mkNode('c', 0), 0); //(>(+(a b) c)
ParseTree* second = mkNode('*', mkNode('z', 0), mkNode('+', mkNode('y', 0), mkNode('b', 0), 0), 0); //* (z + (y b))
ParseTree* thirdA = mkNode('=', mkNode('a', 0), mkNode('2', 0), 0); //=(a 2)
ParseTree* thirdB = mkNode('-', mkNode('x', 0), mkNode('y', 0), 0); //-(x y)
ParseTree* thirdC = mkNode('-', mkNode('y', 0), mkNode('x', 0), 0); //-(y x)
ParseTree* third = mkNode('?', thirdA, thirdB, thirdC, 0); //?(=(a 2) - (x y) -(y x)
ParseTree* final = mkNode('?', first, second, third, 0); // done
prefix_tree(final);
char filename[] = "task3.jpg";
tree_to_graph(final, filename);
result : ?(>(+(a b) c) * (z + (y b)) ?(=(a 2) - (x y) -(y x)
task4
graph <html> <img src='http://daniel.hosting.paran.com/task3.jpg'> </html>
The results are exactly same as what i expected.
task5
* Because many argument can separate expression without using :
mkNode('?', thirdA, thirdB, thirdC, 0) //it is clear thirdB : thirdC
task6
- eval function plan
Do the calculation (+ - * /) more than 2 arguments can be used more than one calculation can be used (ex 1+2-5*3)
- code
int eval(ParseTree* root) {
int i, division, result = 0;
// number
if ((root->name >= '0') && (root->name <= '9')){
return root->name - '0';
// multiply
}else if (root->name == '*') {
result = 1;
for (i=0; i<root->arity; i++)
result = result * eval(root->arg[i]);
return result;
// division
}else if (root->name == '/') {
result = eval(root->arg[0]);
for (i=1; i<root->arity; i++){
division = eval(root->arg[i]);
if (division)
result = result / division;
else {
printf("the number was divided by 0 and put 0 for that result\n");
result = 0;
}
}
return result;
// addition
}else if (root->name == '+') {
for (i=0; i<root->arity; i++)
result += eval(root->arg[i]);
return result;
// substraction
}else if (root->name == '-') {
result = eval(root->arg[0]);
for (i=1; i<root->arity; i++)
result -= eval(root->arg[i]);
return result;
// else
}else{
printf("unexpeted data");
return 0;
}
}
- Test
Test1
- intput (v = 1+2)
int v = eval( mkNode('+', mkNode('1', 0), mkNode('2', 0), 0));
- output
3
Test2 (v = 2*4*5)
- intput
int v = eval( mkNode('*', mkNode('2', 0), mkNode('4', 0), mkNode('5', 0), 0));
- output
40
Test3 (v = 8/2/2)
- intput
int v = eval( mkNode('/', mkNode('8', 0), mkNode('2', 0), mkNode('2', 0), 0));
- output
2
Test4 (v = 3-5-4)
- intput
int v = eval( mkNode('-', mkNode('3', 0), mkNode('5', 0), mkNode('4', 0), 0));
- output
-6
Test4 (v = 3-5+4*2)
- intput
int v = eval( mkNode('-', mkNode('3', 0), mkNode('+', mkNode('5', 0), mkNode('*', mkNode('4', 0), mkNode('2', 0) , 0) , 0) , 0));
- output
-10 (wrong!!)
- discussion
computer do 3-(5+(4*2))
- solution
(-) calculation should do from front to back so it need to recompose.
(3-5)+(4*2)
int v = eval( mkNode('+', mkNode('-', mkNode('3', 0), mkNode('5', 0), 0), mkNode('*', mkNode('4', 0), mkNode('2', 0), 0), 0));
output : 6
From string to parse tree
ParseTree* recogniseE( TokenStream* tokens ) {
if ( current( tokens ) == ’(’ ) {
ParseTree* e;
advance( tokens );
e = recogniseE( tokens );
expect( tokens, ’)’ );
return e;
}
else if ( isdigit( current( tokens ) ) ) {
ParseTree* e = mkNode( current( tokens ), 0 );
advance( tokens );
return e;
} else {
ParseTree* lhs = recogniseE( tokens );
ParseTree* rhs;
char op = current( tokens );
if ( ! isBinOp( op ) )
error( ”BinOp expected” );
advance( tokens );
rhs = recogniseE( tokens );
return mkNode( op, lhs, rhs, 0 );
}
}
- this is not working because if 'tokens' is operation, this code will repeat forever.
ParseTree* lhs = recogniseE( tokens );
- and if there is '(', unless ')' is next character, program can't find ')', because code stop before find')'
discussion
even just calculate(+ - * /), there are a lot of things to deal with to get a right answer.