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