tree.c

00001 #include "tree.h"
00002 #include <stdlib.h>
00003 #include <stdio.h>
00004 #include <math.h>
00005 #include <string.h>
00006 
00007 /* Returns a string for each type of operator */
00008 float eval_node(struct node* node, int level);
00009 void set_number_node(struct node* node, float num);
00010 
00011 /* local variables */
00012 struct node* expr_root_node;
00013 float Xvalue;
00014 
00015 float eval_expr(struct node* node, float x_value) {
00016   Xvalue = x_value;
00017   return eval_node(node, 0);
00018 }
00019 
00020 float p(float l) {
00021   // printf(" op val: %g\n", l);
00022   return l;
00023 }
00024 
00025 float eval_op (struct node* op, int level) {
00026   float right = eval_node(op->right, level+1);
00027   float left  = eval_node(op->left,  level+1);
00028  
00029   switch(op->data.op) {
00030   case OP_ADD:  return p(left + right);
00031   case OP_SUB:  return p(left - right);
00032   case OP_MUL:  return p(left * right);
00033   case OP_DIV:  return p(left / right);
00034   case OP_EXP:  return p(pow(left,right));
00035   default:
00036     fprintf(stderr, "%d not defined as an operator in decode_op_type\n", op->data.op);
00037     exit(1);
00038   }
00039 
00040 }
00041 
00042 void set_root_node(struct node* node) {
00043   expr_root_node = node;
00044 }
00045 
00046 float eval_node(struct node* node, int level) {
00047   switch(node->type) {
00048   case NODE_NUMBER:
00049     return node->data.fval;
00050 
00051   case NODE_VAR:
00052 //      printf("eval var x: %s\n",node->data.name);
00053 //      printf("eval var x: %d\n",node->type);
00054 //      printf("eval var x: %g\n",node->data.fval);
00055     if (strcmp(node->data.name,"x")==0) {
00056       return Xvalue;
00057     } else {
00058       fprintf(stderr,"Cannot parse variables: %s\n", node->data.name);
00059       exit(1);
00060     }
00061 
00062   case NODE_BINOP:
00063     return eval_op(node, level+1);
00064 
00065   case NODE_FUNC:
00066     if (strcmp(node->data.name,"sin")==0) {
00067       printf("Calling function: sin(...)\n");
00068       float y = eval_node(node->left, level+1);
00069       return sin(y);
00070     }
00071     if (strcmp(node->data.name,"cos")==0) {
00072       printf("Calling function: cos(...)\n");
00073       float y = eval_node(node->left, level+1);
00074       return cos(y);
00075     }
00076     if (strcmp(node->data.name,"tan")==0) {
00077       printf("Calling function: tan(...)\n");
00078       float y = eval_node(node->left, level+1);
00079       return tan(y);
00080     }
00081   }
00082 
00083   exit(1);
00084 }
00085 
00086 
00087 struct node* new_number_node(float num){
00088   struct node* node = calloc(sizeof(*node),1);
00089   node->type = NODE_NUMBER;
00090   node->data.fval = num;
00091   node->left = NULL;
00092   node->right = NULL;
00093   node->parent = NULL;
00094   return node;
00095 }
00096 
00097 
00098 struct node* new_var_node(char* str){
00099   struct node* node = calloc(sizeof(*node),1);
00100   node->type = NODE_VAR;
00101   node->data.name = str;
00102   node->left = NULL;
00103   node->right = NULL;
00104   node->parent = NULL;
00105   return node;
00106 }
00107 
00108 
00109 struct node* new_binop_node(enum op_type op, struct node* left, struct node *right){
00110   struct node* node = calloc(sizeof(*node),1);
00111   node->type = NODE_BINOP;
00112   node->data.op = op;
00113   node->left = left;
00114   node->left->parent = node;
00115   node->right = right;
00116   node->right->parent = node;
00117   node->parent = NULL;
00118   return node;
00119 }
00120 
00121 struct node* new_binop_node_no_right(enum op_type op, struct node* left){
00122   struct node* node = calloc(sizeof(*node),1);
00123   node->type = NODE_BINOP;
00124   node->data.op = op;
00125   node->left = left;
00126   node->left->parent = node;
00127   node->right = NULL;
00128   node->parent = NULL;
00129   return node;
00130 }
00131 
00132 struct node* new_func_node(char* name, struct node* left){
00133   struct node* node = calloc(sizeof(*node),1);
00134   node->type = NODE_FUNC;
00135   node->data.name = name;
00136   node->left = left;
00137   node->left->parent = node;
00138   node->right = NULL;
00139   node->parent = NULL;
00140   return node;
00141 }
00142 
00143 struct node* new_func_node_no_left(char* name) {
00144   struct node* node = calloc(sizeof(*node),1);
00145   node->type = NODE_FUNC;
00146   node->data.name = name;
00147   node->left = NULL;
00148   node->right = NULL;
00149   node->parent = NULL;
00150   return node;
00151 }
00152 
00153 // Try to match a number token
00154 // >0 success
00155 //  0 no match
00156 // -1 syntax error
00157 int isNumber(const char* expr) {
00158     int len = strlen(expr);
00159     int num_of_dots = 0;
00160     int i =0;
00161 
00162     for (int i=0; i<len; i++) {
00163         switch(expr[i]) {
00164 
00165         // find digit, '.'
00166         case '0' ... '9':
00167             continue;
00168         case '.':
00169             num_of_dots++;
00170             if (num_of_dots>1)
00171                 return -num_of_dots; // an error
00172             continue;
00173 
00174         // legal end of match
00175         case ' ' :
00176         case '\t':
00177         case '\n':
00178         case '(' :
00179         case ')' :
00180         case '+' :
00181         case '-' :
00182         case '*' :
00183         case '/' :
00184         case '^' :
00185             return i;
00186 
00187         // error end of match
00188         default:
00189             return -i;
00190         }
00191      }
00192     return i;
00193 }
00194 
00195 int isFunc(const char* expr) {
00196     for (int i=0; i<strlen(expr); i++) {
00197         switch(expr[i]) {
00198         case 'a' ... 'z':
00199         case 'A' ... 'Z':
00200         case '_':
00201             continue;
00202         case '(':
00203             return i;
00204         default:
00205             return i==0 ? -1 : -i;
00206         }
00207     }        
00208     return -1;
00209 }
00210 
00211 int isVar(const char* expr) {
00212     if (strlen(expr)==0)
00213       return 0;
00214 
00215     for (int i=0; i<strlen(expr); i++) {
00216         // match var name
00217         switch(expr[i]) {
00218         case 'a' ... 'z':
00219         case 'A' ... 'Z':
00220         case '_':
00221             continue;
00222 
00223         // match terminating character
00224         case ' ' :
00225         case '\t':
00226         case '\n':
00227         case ')' :
00228         case '+' :
00229         case '-' :
00230         case '*' :
00231         case '/' :
00232         case '^' :
00233             return i;
00234         default:
00235             return i==0 ? -1 : -i;
00236         }
00237     }        
00238     return -1;
00239 }
00240 
00241 // Add right side of OP
00242 struct node* add_right(struct node* node, struct node* right){
00243   node->right = right;
00244   right->parent = node;
00245   return right;
00246 }
00247 
00248 // Add right side of OP
00249 struct node* add_left(struct node* node, struct node* left){
00250   node->left = left;
00251   left->parent = node;
00252   return left;
00253 }
00254 
00255 // Add a Node
00256 struct node* add_op(struct node* left, enum op_type op) {
00257     struct node* binop = NULL;
00258     struct node* parent = NULL;
00259 
00260     // no precedence ordering required
00261     if (left->parent==NULL) {
00262         return new_binop_node_no_right(op, left);
00263     }
00264 
00265     // new operation is same or higher precedence, so append as child of branch
00266     if (op >= left->parent->data.op) {
00267         parent = left->parent;
00268         binop = new_binop_node_no_right(op, left);
00269     add_right(parent, binop);
00270     return binop;
00271     }
00272 
00273     // traverse up the tree until no more parents or parent operation is lower precedence
00274     return add_op(left->parent, op);
00275 }
00276 
00277 // scanner and parser
00278 struct node* scanner(const char* es) {
00279     char buff[200];
00280     int len = strlen(es);
00281     struct node* left = NULL;
00282     int lookahead = -1; // 0: fails, >0: success 
00283 
00284     for (int i=0; i<len; i++) {
00285 
00286         switch(es[i]) {
00287         // skip space
00288         case ' ' :  continue; // printf("[space]");
00289         case '\t':  continue; // printf("[tab]");
00290         case '\n':  continue; // printf("[newline]");
00291 
00292         // find number
00293         case '0' ... '9':
00294         case '.':
00295             lookahead = isNumber(&es[i+1]);
00296             if (lookahead>=0) {
00297                 memcpy(buff, &es[i], lookahead+1);
00298                 buff[lookahead+1] = (char) 0;
00299                 i = i + lookahead;
00300 //                printf("token-number: '%s' (atof:%f)\n", buff,atof(buff));
00301                 
00302                 if (left==NULL) {
00303                     left = new_number_node(atof(buff));
00304                 } else if (left->type==NODE_BINOP) {
00305                     left = add_right(left, new_number_node(atof(buff)));
00306                 } else if (left->type==NODE_FUNC) {
00307                     left = add_left(left, new_number_node(atof(buff)));
00308             left = left->parent;
00309                 }
00310             }
00311             continue;
00312 
00313         // operators
00314         case '+' :
00315 //            printf("token-add: '%c'\n", es[i]);
00316             left = add_op(left, OP_ADD);
00317             continue;
00318         case '-' :
00319 //            printf("token-sub: '%c'\n", es[i]);
00320             left = add_op(left, OP_SUB);
00321             continue;
00322         case '*' :
00323 //            printf("token-mul: '%c'\n", es[i]);
00324             left = add_op(left, OP_MUL);
00325             continue;
00326         case '/' :
00327 //            printf("token-div: '%c'\n", es[i]);
00328             left = add_op(left, OP_DIV);
00329             continue;
00330         case '^' :       
00331 //            printf("token-exp: '%c'\n", es[i]);
00332             left = add_op(left, OP_EXP);
00333             continue;
00334 
00335         case 'a' ... 'z':
00336         case 'A' ... 'Z':
00337             // find function
00338             lookahead = isFunc(&es[i+1]);
00339             if (lookahead>=0) {
00340                 memcpy(buff, &es[i], lookahead+1);
00341                 buff[lookahead+1] = (char) 0;
00342                 printf("token-func: '%s'\n", buff);
00343                 i = i + lookahead;
00344 /*
00345                 if (left==NULL) {
00346                     left = new_func_node(buff);
00347                 } else if (left->type==NODE_BINOP) {
00348                     left = add_right(left, new_func_node(buff));
00349                 }
00350  */               continue;
00351             }
00352 
00353             // find variable
00354             lookahead = isVar(&es[i+1]);
00355             if (lookahead>=0) {
00356                 memcpy(buff, &es[i], lookahead+1);
00357                 buff[lookahead+1] = (char) 0;
00358 //                printf("token-var: '%s'\n", buff);
00359                 i = i + lookahead;
00360 
00361                 if (left==NULL) {
00362                     left = new_var_node(buff);
00363                 } else if (left->type==NODE_BINOP) {
00364                     left = add_right(left, new_var_node(buff));
00365                 }
00366                 continue;
00367             }
00368 
00369         // grouping
00370         case '(' :
00371             printf("token-l-paren: '%c'\n", es[i]);
00372             continue;
00373         case ')' :
00374             printf("token-r-paren: '%c'\n", es[i]);
00375             continue;
00376 
00377 
00378         default:    ;
00379         }
00380     }   
00381 
00382     // find root
00383     while (left->parent != NULL) {
00384         left = left->parent;
00385     }
00386     return left;
00387 }
00388 
00389 
00390 
00391 /*   
00392    static const char expr_str[] = "5*4 * 3 / 2 - 1 + 37\n";
00393 
00394    // compile expression
00395    struct node* expr = comp_expr(expr_str);
00396 
00397    // evaluate expression
00398    eval_expr(expr, 1);
00399 
00400    // some output
00401    printf("Expression: %s\n", expr_str);
00402    x = 3.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00403    x = 3.5; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00404    x = 4.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00405 
00406    // example 2
00407    static const char str2[] = "5*4 * 3 / 2 - x + 37\n";
00408    expr = comp_expr(str2);
00409    eval_expr(expr, 1);
00410 
00411    printf("Expression: %s\n", str2);
00412    x = 1.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00413    x = 3.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00414    x = 3.5; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00415    x = 4.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00416 
00417 
00418    // example 3
00419    static const char str3[] = "5*4 * 3 / 2  - 1 + 37 + sin(x)\n";
00420    expr = comp_expr(str3);
00421    eval_expr(expr, 1);
00422 
00423    printf("Expression: %s\n", str3);
00424    x =-1.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00425    x = 1.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00426    x = 3.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00427    x = 3.5; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00428    x = 4.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00429 
00430    // example 4
00431    static const char str4[] = "5*4 * 3 / 2  - 1 + 37 + sin(x) + 2^3\n";
00432    expr = comp_expr(str4);
00433    eval_expr(expr, 1);
00434 
00435    printf("Expression: %s\n", str4);
00436    x = 1.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00437    x = 5.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00438    x = 7.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00439    x = 9.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00440    x =11.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x));
00441 */
00442