![](/media/cache/img/default_profile.jpg.50x50_q85.jpg)
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
Revision 6:646d22295054, committed 2018-12-13
- Comitter:
- zrussell3
- Date:
- Thu Dec 13 20:27:21 2018 +0000
- Parent:
- 5:1cbfc69d87b5
- Commit message:
- Implemented parsing
Changed in this revision
--- a/main.cpp Thu Dec 13 19:28:26 2018 +0000 +++ b/main.cpp Thu Dec 13 20:27:21 2018 +0000 @@ -4,6 +4,9 @@ #include "USBHostKeyboard.h" #include "uVGAIII.h" +extern "C" struct node* scanner(const char* es); +extern "C" float eval_expr(struct node* node, float x_value); + #include <math.h> #define SIZE_X 480 @@ -200,6 +203,10 @@ printer.printf(currentLine); printer.feed(2); + struct node* expr = scanner(currentLine); + float val = eval_expr(expr, 3.0); + uLCD.printf("Evaluate: %f \n",val); + for(size_t i = 0; i < 48; i++) { currentLine[i] = NULL; } @@ -308,6 +315,10 @@ ecran.puts("Ready!"); VGA_Lock.unlock(); + static const char es[] = "1 + 2 ^ 3 * 4 + 5 * x"; + struct node* expr = scanner(es); + float val = eval_expr(expr, 3.0); + while(1) { led=!led; Thread::wait(600); // Wait .6s in main thread
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tree.c Thu Dec 13 20:27:21 2018 +0000 @@ -0,0 +1,442 @@ +#include "tree.h" +#include <stdlib.h> +#include <stdio.h> +#include <math.h> +#include <string.h> + +/* Returns a string for each type of operator */ +float eval_node(struct node* node, int level); +void set_number_node(struct node* node, float num); + +/* local variables */ +struct node* expr_root_node; +float Xvalue; + +float eval_expr(struct node* node, float x_value) { + Xvalue = x_value; + return eval_node(node, 0); +} + +float p(float l) { + // printf(" op val: %g\n", l); + return l; +} + +float eval_op (struct node* op, int level) { + float right = eval_node(op->right, level+1); + float left = eval_node(op->left, level+1); + + switch(op->data.op) { + case OP_ADD: return p(left + right); + case OP_SUB: return p(left - right); + case OP_MUL: return p(left * right); + case OP_DIV: return p(left / right); + case OP_EXP: return p(pow(left,right)); + default: + fprintf(stderr, "%d not defined as an operator in decode_op_type\n", op->data.op); + exit(1); + } + +} + +void set_root_node(struct node* node) { + expr_root_node = node; +} + +float eval_node(struct node* node, int level) { + switch(node->type) { + case NODE_NUMBER: + return node->data.fval; + + case NODE_VAR: +// printf("eval var x: %s\n",node->data.name); +// printf("eval var x: %d\n",node->type); +// printf("eval var x: %g\n",node->data.fval); + if (strcmp(node->data.name,"x")==0) { + return Xvalue; + } else { + fprintf(stderr,"Cannot parse variables: %s\n", node->data.name); + exit(1); + } + + case NODE_BINOP: + return eval_op(node, level+1); + + case NODE_FUNC: + if (strcmp(node->data.name,"sin")==0) { + printf("Calling function: sin(...)\n"); + float y = eval_node(node->left, level+1); + return sin(y); + } + if (strcmp(node->data.name,"cos")==0) { + printf("Calling function: cos(...)\n"); + float y = eval_node(node->left, level+1); + return cos(y); + } + if (strcmp(node->data.name,"tan")==0) { + printf("Calling function: tan(...)\n"); + float y = eval_node(node->left, level+1); + return tan(y); + } + } + + exit(1); +} + + +struct node* new_number_node(float num){ + struct node* node = calloc(sizeof(*node),1); + node->type = NODE_NUMBER; + node->data.fval = num; + node->left = NULL; + node->right = NULL; + node->parent = NULL; + return node; +} + + +struct node* new_var_node(char* str){ + struct node* node = calloc(sizeof(*node),1); + node->type = NODE_VAR; + node->data.name = str; + node->left = NULL; + node->right = NULL; + node->parent = NULL; + return node; +} + + +struct node* new_binop_node(enum op_type op, struct node* left, struct node *right){ + struct node* node = calloc(sizeof(*node),1); + node->type = NODE_BINOP; + node->data.op = op; + node->left = left; + node->left->parent = node; + node->right = right; + node->right->parent = node; + node->parent = NULL; + return node; +} + +struct node* new_binop_node_no_right(enum op_type op, struct node* left){ + struct node* node = calloc(sizeof(*node),1); + node->type = NODE_BINOP; + node->data.op = op; + node->left = left; + node->left->parent = node; + node->right = NULL; + node->parent = NULL; + return node; +} + +struct node* new_func_node(char* name, struct node* left){ + struct node* node = calloc(sizeof(*node),1); + node->type = NODE_FUNC; + node->data.name = name; + node->left = left; + node->left->parent = node; + node->right = NULL; + node->parent = NULL; + return node; +} + +struct node* new_func_node_no_left(char* name) { + struct node* node = calloc(sizeof(*node),1); + node->type = NODE_FUNC; + node->data.name = name; + node->left = NULL; + node->right = NULL; + node->parent = NULL; + return node; +} + +// Try to match a number token +// >0 success +// 0 no match +// -1 syntax error +int isNumber(const char* expr) { + int len = strlen(expr); + int num_of_dots = 0; + int i =0; + + for (int i=0; i<len; i++) { + switch(expr[i]) { + + // find digit, '.' + case '0' ... '9': + continue; + case '.': + num_of_dots++; + if (num_of_dots>1) + return -num_of_dots; // an error + continue; + + // legal end of match + case ' ' : + case '\t': + case '\n': + case '(' : + case ')' : + case '+' : + case '-' : + case '*' : + case '/' : + case '^' : + return i; + + // error end of match + default: + return -i; + } + } + return i; +} + +int isFunc(const char* expr) { + for (int i=0; i<strlen(expr); i++) { + switch(expr[i]) { + case 'a' ... 'z': + case 'A' ... 'Z': + case '_': + continue; + case '(': + return i; + default: + return i==0 ? -1 : -i; + } + } + return -1; +} + +int isVar(const char* expr) { + if (strlen(expr)==0) + return 0; + + for (int i=0; i<strlen(expr); i++) { + // match var name + switch(expr[i]) { + case 'a' ... 'z': + case 'A' ... 'Z': + case '_': + continue; + + // match terminating character + case ' ' : + case '\t': + case '\n': + case ')' : + case '+' : + case '-' : + case '*' : + case '/' : + case '^' : + return i; + default: + return i==0 ? -1 : -i; + } + } + return -1; +} + +// Add right side of OP +struct node* add_right(struct node* node, struct node* right){ + node->right = right; + right->parent = node; + return right; +} + +// Add right side of OP +struct node* add_left(struct node* node, struct node* left){ + node->left = left; + left->parent = node; + return left; +} + +// Add a Node +struct node* add_op(struct node* left, enum op_type op) { + struct node* binop = NULL; + struct node* parent = NULL; + + // no precedence ordering required + if (left->parent==NULL) { + return new_binop_node_no_right(op, left); + } + + // new operation is same or higher precedence, so append as child of branch + if (op >= left->parent->data.op) { + parent = left->parent; + binop = new_binop_node_no_right(op, left); + add_right(parent, binop); + return binop; + } + + // traverse up the tree until no more parents or parent operation is lower precedence + return add_op(left->parent, op); +} + +// scanner and parser +struct node* scanner(const char* es) { + char buff[200]; + int len = strlen(es); + struct node* left = NULL; + int lookahead = -1; // 0: fails, >0: success + + for (int i=0; i<len; i++) { + + switch(es[i]) { + // skip space + case ' ' : continue; // printf("[space]"); + case '\t': continue; // printf("[tab]"); + case '\n': continue; // printf("[newline]"); + + // find number + case '0' ... '9': + case '.': + lookahead = isNumber(&es[i+1]); + if (lookahead>=0) { + memcpy(buff, &es[i], lookahead+1); + buff[lookahead+1] = (char) 0; + i = i + lookahead; +// printf("token-number: '%s' (atof:%f)\n", buff,atof(buff)); + + if (left==NULL) { + left = new_number_node(atof(buff)); + } else if (left->type==NODE_BINOP) { + left = add_right(left, new_number_node(atof(buff))); + } else if (left->type==NODE_FUNC) { + left = add_left(left, new_number_node(atof(buff))); + left = left->parent; + } + } + continue; + + // operators + case '+' : +// printf("token-add: '%c'\n", es[i]); + left = add_op(left, OP_ADD); + continue; + case '-' : +// printf("token-sub: '%c'\n", es[i]); + left = add_op(left, OP_SUB); + continue; + case '*' : +// printf("token-mul: '%c'\n", es[i]); + left = add_op(left, OP_MUL); + continue; + case '/' : +// printf("token-div: '%c'\n", es[i]); + left = add_op(left, OP_DIV); + continue; + case '^' : +// printf("token-exp: '%c'\n", es[i]); + left = add_op(left, OP_EXP); + continue; + + case 'a' ... 'z': + case 'A' ... 'Z': + // find function + lookahead = isFunc(&es[i+1]); + if (lookahead>=0) { + memcpy(buff, &es[i], lookahead+1); + buff[lookahead+1] = (char) 0; + printf("token-func: '%s'\n", buff); + i = i + lookahead; +/* + if (left==NULL) { + left = new_func_node(buff); + } else if (left->type==NODE_BINOP) { + left = add_right(left, new_func_node(buff)); + } + */ continue; + } + + // find variable + lookahead = isVar(&es[i+1]); + if (lookahead>=0) { + memcpy(buff, &es[i], lookahead+1); + buff[lookahead+1] = (char) 0; +// printf("token-var: '%s'\n", buff); + i = i + lookahead; + + if (left==NULL) { + left = new_var_node(buff); + } else if (left->type==NODE_BINOP) { + left = add_right(left, new_var_node(buff)); + } + continue; + } + + // grouping + case '(' : + printf("token-l-paren: '%c'\n", es[i]); + continue; + case ')' : + printf("token-r-paren: '%c'\n", es[i]); + continue; + + + default: ; + } + } + + // find root + while (left->parent != NULL) { + left = left->parent; + } + return left; +} + + + +/* + static const char expr_str[] = "5*4 * 3 / 2 - 1 + 37\n"; + + // compile expression + struct node* expr = comp_expr(expr_str); + + // evaluate expression + eval_expr(expr, 1); + + // some output + printf("Expression: %s\n", expr_str); + x = 3.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 3.5; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 4.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + + // example 2 + static const char str2[] = "5*4 * 3 / 2 - x + 37\n"; + expr = comp_expr(str2); + eval_expr(expr, 1); + + printf("Expression: %s\n", str2); + x = 1.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 3.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 3.5; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 4.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + + + // example 3 + static const char str3[] = "5*4 * 3 / 2 - 1 + 37 + sin(x)\n"; + expr = comp_expr(str3); + eval_expr(expr, 1); + + printf("Expression: %s\n", str3); + x =-1.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 1.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 3.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 3.5; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 4.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + + // example 4 + static const char str4[] = "5*4 * 3 / 2 - 1 + 37 + sin(x) + 2^3\n"; + expr = comp_expr(str4); + eval_expr(expr, 1); + + printf("Expression: %s\n", str4); + x = 1.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 5.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 7.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x = 9.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); + x =11.0; printf("Value[x=%2.3g]: %2.3g\n", x, eval_expr(expr, x)); +*/ +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tree.h Thu Dec 13 20:27:21 2018 +0000 @@ -0,0 +1,62 @@ +#ifndef TREE_H +#define TREE_H + +/* The type of any binary or unary operators */ +enum token_type { + TOKEN_NUM, + TOKEN_ADD, + TOKEN_SUB, + TOKEN_MUL, + TOKEN_DIV, + TOKEN_EXP, + TOKEN_VAR, + TOKEN_FUN, + TOKEN_LPA, + TOKEN_RPA +}; + + +/* The type of any binary or unary operators */ +enum op_type { + OP_ADD, + OP_SUB, + OP_MUL, + OP_DIV, + OP_EXP +}; + +/* The type of each node */ +enum node_type { + NODE_NUMBER, /* Holds one number in data.fval, no children */ + NODE_VAR, /* Holds the name of the var in data.name */ + NODE_BINOP, /* Has the operator in op and both left and right children*/ + NODE_FUNC /* Has the function name in data.name and a left child */ +}; + + + +/* The structure that holds the parse tree */ +struct node{ + enum node_type type; + union data{ + float fval; + char *name; + enum op_type op; + } data; + struct node *left; + struct node *right; + struct node *parent; +}; + +/* Prints a tree of nodes, indenting as it descends the tree */ +void print_node(struct node*); +/* Creates a new node of number type */ +struct node* new_number_node(float num); +/* Creates a new node of var type */ +struct node* new_var_node(char* str); +/* Creates a new node for a binary operator, with left and right children */ +struct node* new_binop_node(enum op_type, struct node* left, struct node *right); +struct node* new_func_node(char* name, struct node* left); + + +#endif