Mathematica-like environment on the mbed using USB keyboard input, VGA output, and a thermal printer.
Dependencies: mbed Thermal 4DGL-uLCD-SE USBHost_Modified uVGAIII
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
Generated on Mon Aug 15 2022 23:52:04 by 1.7.2