The Ecere SDK - sdk/blob - samples/eC/ecas/expression.ec

   1 public import "ecere"
   2 import "misc"
   3
   4 #include <stdio.h>
   5
   6 public:
   7
   8 enum CASCharFlag {letter, end, white, number, op};
   9
  10 class CASCharFlags : CharFlags {
  11    CASCharFlags() {
  12       flags[0] = (byte)CASCharFlag::end;
  13       Set("\t\n\v\f\r ", CASCharFlag::white);
  14       Set("0123456789.", CASCharFlag::number);
  15       Set("!%&()*+,-/:;<=>?@[\\]^{|}~", CASCharFlag::op);
  16    }
  17 };
  18
  19 CASCharFlags cascharflags {};
  20
  21 enum ExpressionType {null=0, i, f, c, v, openfunction, function, openparenthesis, parenthesis, prefix, postfix, binary};
  22    //i means integer
  23    //f means floating point
  24    //c means constant
  25    //v means variable
  26
  27 enum ExpressionClass {nullary=0, prefix, postfix, binary, vallary, nary};
  28 //I define a vallary operator as one that binds a single expression on both sides (e.g. (), [], {}, "")
  29 //An nary operator is one that binds an array of expressions on both sides (e.g. sum(3,4,5))
  30
  31 ExpressionClass expression_class[ExpressionType] = {
  32    nullary, nullary, nullary, nullary, nullary, prefix, nary, prefix, vallary, prefix, postfix, binary
  33 };
  34 //function and parenthesis are weird classes.  They are considered nullary, but they do contain data:
  35 //  function's arguments are in the Array<Expression> arg
  36 //  parenthesis's argument is in b, just like the prefix it was before
  37
  38 enum PrefixOperator {root=0, positive, negative};
  39 int prefix_op_order[PrefixOperator] = {
  40    0, 4,4
  41 };
  42 const char *prefix_op_string[PrefixOperator] = {
  43    "root", "+", "-"
  44 };
  45
  46 enum PostfixOperator {factorial=0};
  47 int postfix_op_order[PostfixOperator] = {
  48    6
  49 };
  50 const char *postfix_op_string[PostfixOperator] = {
  51    "!"
  52 };
  53
  54 //A lot of CAS operations may weed out operators like subtract, but it is included to make it possible to maniuplate the expression for readability, etc.
  55 enum BinaryOperator {add, subtract, multiply, divide, power, equals, comma};
  56 int binary_op_order[BinaryOperator] = {
  57    3,3, 4,4, 5, 2, 1
  58 };
  59 const char *binary_op_string[BinaryOperator] = {
  60    "+", "-", "*", "/", "^", "=", ","
  61 };
  62
  63 enum ParenthesisType {parenthesis, brackets, braces};
  64 const char *parenthesis_type_string[ParenthesisType] = {
  65    "()", "[]", "{}"
  66 };
  67
  68 enum CASFunction {sum, product, polynomial, exp, ln, sin, cos, tan, arcsin, arccos, arctan};
  69
  70 const char *function_string[CASFunction] = {
  71    "sum", "product", "polynomial", "exp", "ln", "sin", "cos", "tan", "arcsin", "arccos", "arctan"
  72 };
  73
  74 class CASFunctionDefinition {
  75    virtual bool Expression::Sanitize(void) {
  76       return true;
  77    }
  78    virtual void Expression::Simplify(void);
  79 };
  80
  81 bool Expression::SanitizeSingleArgument(void) {
  82    if (arg.size != 1)
  83       return false;
  84    return true;
  85 }
  86
  87 class FunctionList : Dictionary {
  88    Array<CASFunctionDefinition> f {};
  89    FunctionList() {
  90       CASFunction i;
  91       for (i=0; i<CASFunction::enumSize; i++)
  92          array.Add(StrDup(function_string[i]));
  93       f.size = CASFunction::enumSize;
  94       f[CASFunction::sum] = {
  95
  96       };
  97       f[CASFunction::product] = {
  98
  99       };
 100       f[CASFunction::polynomial] = {
 101
 102       };
 103       f[CASFunction::exp] = {
 104          bool Expression::Sanitize()
 105          {
 106             Expression right;
 107             if (arg.size != 1)
 108                return false;
 109             right = arg[0];
 110             delete arg;
 111             type = binary;
 112             binary.op = power;
 113             a = {type=c, mom=this, c=e};
 114             b = right;
 115             return true;
 116          }
 117       };
 118       f[CASFunction::ln] = {
 119          Sanitize = SanitizeSingleArgument;
 120
 121       };
 122       f[CASFunction::sin] = {
 123          Sanitize = SanitizeSingleArgument;
 124
 125       };
 126       f[CASFunction::cos] = {
 127          Sanitize = SanitizeSingleArgument;
 128
 129       };
 130       f[CASFunction::tan] = {
 131          Sanitize = SanitizeSingleArgument;
 132
 133       };
 134       f[CASFunction::arcsin] = {
 135          Sanitize = SanitizeSingleArgument;
 136
 137       };
 138       f[CASFunction::arccos] = {
 139          Sanitize = SanitizeSingleArgument;
 140
 141       };
 142       f[CASFunction::arctan] = {
 143          Sanitize = SanitizeSingleArgument;
 144
 145       };
 146    }
 147    //these functions check to make sure the input is a function of correct range before executing
 148    bool Sanitize(Expression expr) {
 149       bool ret = false;
 150       if (expr.type==function && expr.function.func<f.size)
 151          ret = f[expr.function.func].Sanitize(expr);
 152       return ret;
 153    }
 154    void Simplify(Expression expr) {
 155       if (expr.type==function && expr.function.func<f.size)
 156          f[expr.function.func].Simplify(expr);
 157    }
 158 };
 159
 160 class CASDictionary : struct {
 161    Dictionary v {};
 162    FunctionList f {};
 163 };
 164
 165 enum CASConstant {i, e, pi};
 166
 167 const char *constant_string[CASConstant] = {
 168    "𝑖", "ℯ", "π"
 169 };
 170
 171 class ExprChildWalker {
 172 public:
 173    Expression expr;
 174    Expression user0, user1, user2;
 175
 176    void Go(void) {
 177       switch (expr.ExprClass()) {
 178          case prefix:
 179          case vallary:
 180             On(&expr.b);
 181             break;
 182          case postfix:
 183             On(&expr.a);
 184             break;
 185          case binary:
 186             if (On(&expr.a))
 187                On(&expr.b);
 188             break;
 189          case nary:
 190             for (iter:expr.arg) {
 191                if (!On(&iter))
 192                   break;
 193             }
 194             break;
 195       }
 196    }
 197    //return false to end iteration
 198    virtual bool On(Expression *e);
 199 };
 200
 201 class Expression : struct {
 202 public:
 203    ExpressionType type;
 204    Expression mom; //easier to type than "parent" :)
 205
 206    //tags
 207    bool constant:1, approx:1;
 208    void ClearTags(void) {
 209       constant = false;
 210       approx = false;
 211    }
 212
 213    union {
 214       long long i;
 215       long double f;
 216       CASConstant c;
 217       uint v;
 218       struct {
 219          CASFunction func;
 220       } function;
 221       struct {
 222          ParenthesisType type;
 223       } parenthesis; //also used for openparenthesis
 224       struct {
 225          PrefixOperator op;
 226       } prefix;
 227       struct {
 228          PostfixOperator op;
 229       } postfix;
 230       struct {
 231          BinaryOperator op;
 232       } binary;
 233    };
 234    union {
 235       struct {
 236          Expression a; //binary left child or postfix child
 237          Expression b; //binary right child, prefix child, or vallary child
 238       };
 239       Array<Expression> arg; //only for nary operators (e.g. functions)
 240    };
 241
 242    void DebugPrint(File out, CASDictionary dict, uint spacelevel, Expression correctMom) {
 243       uint d = spacelevel;
 244       char tagstr[16];
 245       while (d--)
 246          out.Putc(' ');
 247       if (this==null) {
 248          out.Printf("null pointer\n");
 249          return;
 250       }
 251       if (mom != correctMom)
 252          out.Printf("Incorrectly parented to %p instead of %p ", mom, correctMom);
 253       memset(tagstr, '-', 2);
 254       tagstr[2] = 0;
 255       if (constant)
 256          tagstr[0] = 'c';
 257       if (approx)
 258          tagstr[1] = 'a';
 259       out.Printf("%s  ", tagstr);
 260       switch (type) {
 261          case null:
 262             out.Printf("nothing\n");
 263             break;
 264          case i:
 265             //out.PrintLn(i);
 266             out.Printf("%lld\n", i);
 267             break;
 268          case f:
 269             //out.PrintLn(f);
 270             out.Printf("%.15Lg\n", (long double)f);
 271             break;
 272          case c:
 273             out.Printf("%s (constant)\n", c<CASConstant::enumSize ? constant_string[c] : "Invalid constant");
 274             break;
 275          case v:
 276             out.Printf("%s\n", dict.v.name(v));
 277             break;
 278          case openfunction:
 279             out.Printf("%s(\n", dict.f.name(function.func));
 280             b.DebugPrint(out, dict, spacelevel+2, this);
 281             break;
 282          case function:
 283             out.Printf("%s()\n", dict.f.name(function.func));
 284             for (iter:arg)
 285                iter.DebugPrint(out, dict,spacelevel+2, this);
 286             break;
 287          case openparenthesis:
 288             out.Printf("%c\n", OpString()[0]);
 289             b.DebugPrint(out, dict, spacelevel+2, this);
 290             break;
 291          case parenthesis:
 292             out.Printf("%s\n", OpString());
 293             b.DebugPrint(out, dict, spacelevel+2, this);
 294             break;
 295          case prefix:
 296             out.Printf("%s\n", OpString());
 297             b.DebugPrint(out, dict, spacelevel+2, this);
 298             break;
 299          case postfix:
 300             out.Printf("%s\n", OpString());
 301             a.DebugPrint(out, dict, spacelevel+2, this);
 302             break;
 303          case binary:
 304             out.Printf("%s\n", OpString());
 305             a.DebugPrint(out, dict, spacelevel+2, this);
 306             b.DebugPrint(out, dict, spacelevel+2, this);
 307             break;
 308       }
 309    }
 310
 311    void Free(void) {
 312       ExprChildWalker w {this;
 313          bool On(Expression *e) {
 314             e->Clear();
 315             if (*e)
 316                e->mom = null;
 317             delete *e;
 318             return true;
 319          }
 320       };
 321       w.Go();
 322       if (ExprClass()==nary)
 323          delete arg;
 324       delete w;
 325    }
 326    void Clear(void) { //keeps parent the same
 327       if (this) {
 328          Free();
 329          type = null;
 330       }
 331    }
 332    //sort of like delete this, but does not affect anything else but this block
 333    //Note:  Make sure that arg array is taken care of if this is an nary
 334    void Delete(void) {
 335       if (this) {
 336          type = null;
 337          mom = null;
 338          delete this;
 339       }
 340    }
 341    ~Expression() {
 342       if (this) {
 343          Elope(null);
 344          Free();
 345       }
 346    }
 347    //Copy() makes a copy of this Expression that makes no references to this expression
 348    Expression Copy(Expression newMom) {
 349       Expression ret {mom=newMom};
 350       if (!this)
 351          return ret;
 352       memcpy(ret, this, sizeof(class Expression));
 353       ret.mom = newMom;
 354       switch (ExprClass()) {
 355          case prefix:
 356          case vallary:
 357             ret.b = b.Copy(ret);
 358             break;
 359          case postfix:
 360             ret.a = a.Copy(ret);
 361             break;
 362          case binary:
 363             ret.a = a.Copy(ret);
 364             ret.b = b.Copy(ret);
 365             break;
 366          case nary: {
 367             uint i,e;
 368             e = arg.size;
 369             ret.arg = {size=e};
 370             for (i=0; i<e; i++)
 371                ret.arg[i] = arg[i].Copy(ret);
 372          }
 373             break;
 374       }
 375       return ret;
 376    }
 377
 378    //collect terms in this expression separated by the binary operator op
 379    //e.g. separate x^2+3x+1 by plus into [x^2, 3x, 1]
 380    //Will separate (x^2+3x+1)/2 by plus into [(x^2+3x+1)/2]
 381    //If newMom is not null, all binary operator nodes involved in the array will be freed, and each node will be parented to newMom
 382    void CollectTerms(BinaryOperator op, Array<Expression> out, Expression newMom) {
 383       if (!this)
 384          return;
 385       if (type==binary && binary.op==op) {
 386          a.CollectTerms(op, out, newMom);
 387          b.CollectTerms(op, out, newMom);
 388          if (newMom) {
 389             a=null;
 390             b=null;
 391             delete this;
 392          }
 393       } else {
 394          if (newMom)
 395             mom = newMom;
 396          out.Add(this);
 397       }
 398    }
 399    //only reparents the top level
 400    void ReparentChildren(void) {
 401       ExprChildWalker w {this;
 402          bool On(Expression *e)
 403          {
 404             e->mom = expr;
 405             return true;
 406          }
 407       };
 408       w.Go();
 409       delete w;
 410    }
 411    //relinks the parent to this child
 412    //Old is the former pointer to the child
 413    void Rechild(Expression old) {
 414       SwapChild(mom, old, this);
 415    }
 416    //disconnects this from parent without deleting it, and sets in its place newChild
 417    void Elope(Expression newChild) {
 418       SwapChild(mom, this, newChild);
 419       if (newChild)
 420          newChild.mom = mom;
 421    }
 422    //disconnects this expression from its parent and relinks its children to the parent
 423    //Currently, this only works with unary (prefix/postfix/vallary) operators
 424    void Unlink(void) {
 425       if (!this) {
 426          fprintf(stderr, "BUG:  Attempted to unlink null node; ignoring.\n");
 427          return;
 428       }
 429       if (!mom) {
 430          fprintf(stderr, "BUG:  Attempted to unlink root node; ignoring.\n");
 431          return;
 432       }
 433       switch (ExprClass()) {
 434          case prefix:
 435          case vallary:
 436             Elope(b);
 437             Delete();
 438             break;
 439          case postfix:
 440             Elope(a);
 441             Delete();
 442             break;
 443          default:
 444             fprintf(stderr, "BUG:  Attempted to call Unlink on non-unary node.\n");
 445       }
 446    }
 447
 448    //Note that FromString likes to toy with the string, but anything done to the string will be undone.
 449    bool FromString(char *str, CASDictionary dictionary) {
 450       ExpressionFromString(this, str, dictionary);
 451       return Sanitize(this, dictionary);
 452    }
 453    char *ToString(void) {
 454
 455    }
 456    const char *OpString(void) {
 457       if (type==prefix && prefix.op<PrefixOperator::enumSize)
 458          return prefix_op_string[prefix.op];
 459       else if (type==postfix && postfix.op<PostfixOperator::enumSize)
 460          return postfix_op_string[postfix.op];
 461       else if (type==binary && binary.op<BinaryOperator::enumSize)
 462          return binary_op_string[binary.op];
 463       else if ((type==openparenthesis || type==parenthesis) && parenthesis.type<ParenthesisType::enumSize)
 464          return parenthesis_type_string[parenthesis.type];
 465       else
 466          return "??";
 467    }
 468    int OpOrder(void) {
 469       if (type==binary && binary.op<BinaryOperator::enumSize)
 470          return binary_op_order[binary.op];
 471       else if (type==prefix && prefix.op<PrefixOperator::enumSize)
 472          return prefix_op_order[prefix.op];
 473       else if (type==postfix && postfix.op<PostfixOperator::enumSize)
 474          return postfix_op_order[postfix.op];
 475       else if (type==openfunction) {
 476          if (b && b.type==parenthesis && b.parenthesis.type==parenthesis)
 477             return 1000; //arbitrary number larger than any other order
 478          else
 479             return binary_op_order[power];
 480       }
 481       else if (type==openparenthesis)
 482          return 0; //yes, this should be the lowest, not highest, operator
 483       else
 484          return -1; //error
 485    }
 486    ExpressionClass ExprClass(void) {
 487       if (type<ExpressionType::enumSize)
 488          return expression_class[type];
 489       else
 490          return nullary;
 491    }
 492    void Simplify(CASDictionary dict) {
 493
 494    }
 495 };
 496
 497 void SwapChild(Expression mom, Expression oldChild, Expression newChild) {
 498    ExprChildWalker w;
 499    if (!mom)
 500       return;
 501    w = {mom, user0=oldChild, user1=newChild;
 502       bool On(Expression *e) {
 503          if (*e==user0) {
 504             *e = user1;
 505             return false;
 506          }
 507          return true;
 508       }
 509    };
 510    w.Go();
 511    delete w;
 512 }
 513
 514 class ExpressionTree : struct {
 515 public:
 516    CASDictionary dict;
 517    Expression root {type=prefix, prefix.op=root};
 518    Expression p; //pointer to most recently added token
 519    File err {output=stderr};
 520    bool closeerrfiles;
 521
 522    p = root;
 523
 524    ~ExpressionTree() {
 525       if (!closeerrfiles) {
 526          err.input = null;
 527          err.output = null;
 528       }
 529    }
 530
 531    // e must be the string terminator, and the string must be zero-terminated as well
 532    void PushInteger(const char *s, const char *e) {
 533       ReadULLError rerror;
 534       Expression var {type=i};
 535       unsigned long long n = ReadULL_Valid(s, e, NB_Dec, &rerror);
 536       var.i = (long long)n;
 537       if (rerror==overflow || n>=(((unsigned long long)-1)>>1)+1)
 538          err.Printf("Number %s too big; using %lld\n", s, var.i);
 539       push(var, false);
 540    }
 541    void PushFloat(const char *s) {
 542       Expression var {type=f};
 543       long double n = (long double)atof(s); //TODO:  Use something that won't truncate the result
 544       var.f = n;
 545       push(var, false);
 546    }
 547    void PushConstant(CASConstant con) {
 548       Expression var {type=c, c=con};
 549       push(var, false);
 550    }
 551    void PushVariable(const char *s) {
 552       Expression var {type=v, v=dict.v.lookup(s, true)};
 553       push(var, false);
 554    }
 555    void PushFunction(CASFunction f) {
 556       Expression var {type=openfunction, function.func=f};
 557       push(var, false);
 558    }
 559    void PushOperator(const char *s) {
 560       Expression op {type=binary};
 561       Expression w;
 562       ExpressionClass pc;
 563       int order;
 564       if (s[1]==0) { //single-character operator
 565          switch (*s) {
 566             case '+':
 567             case '-':
 568                pc = p.ExprClass();
 569                if (pc==prefix || pc==binary) {
 570                   op.type = prefix;
 571                   op.prefix.op = *s=='+' ? positive : negative;
 572                } else {
 573                   op.binary.op = *s=='+' ? add : subtract;
 574                }
 575                break;
 576             case '*':
 577                op.binary.op = multiply;
 578                break;
 579             case '/':
 580                op.binary.op = divide;
 581                break;
 582             case '^':
 583                op.binary.op = power;
 584                break;
 585             case '=':
 586                op.binary.op = equals;
 587                break;
 588             case ',':
 589                op.binary.op = comma;
 590                break;
 591             case '(': //we will push a "prefix" openparenthesis like any other prefix op
 592                op.type = openparenthesis;
 593                op.parenthesis.type = parenthesis;
 594                break;
 595             case '[':
 596                op.type = openparenthesis;
 597                op.parenthesis.type = brackets;
 598                break;
 599             case '{':
 600                op.type = openparenthesis;
 601                op.parenthesis.type = braces;
 602                break;
 603             case ')': //we will close the soonest openparenthesis and continue from there
 604             case ']':
 605             case '}': {
 606                ParenthesisType type = (*s==')' ? parenthesis : *s==']' ? brackets : braces);
 607                delete op;
 608                w = p;
 609                for (;;) {
 610                   if (w.type==openfunction)
 611                      closeFunction(w);
 612                   else if (w.type==openparenthesis) {
 613                      if (w.parenthesis.type==type) {
 614                         p = w;
 615                         p.type = parenthesis;
 616                         return;
 617                      } else
 618                         err.Printf("End %c appeared after start %c; disregarding.\n", *s, w.OpString()[1]);
 619                   } else if (!w.mom || (w.type==prefix && w.prefix.op==root)) {
 620                      err.Printf("End parenthesis missing beginning parenthesis; ignoring.\n");
 621                      return;
 622                   }
 623                   w = w.mom;
 624                }
 625                break;
 626             }
 627             case '!':
 628                op.type = postfix;
 629                op.postfix.op = factorial;
 630                break;
 631             default:
 632                op.type = null;
 633          }
 634       } else
 635          op.type = null;
 636       if (op.type==null) {
 637          err.Printf("Operator '%s' unrecognized; ignoring.\n", s);
 638          delete op;
 639          return;
 640       }
 641       push(op, false);
 642    }
 643 private:
 644    void push(Expression expr, bool implicit) {
 645       ExpressionClass c = expr.ExprClass();
 646       ExpressionClass pc = p.ExprClass();
 647       if (c==nullary || c==prefix) {
 648          if (pc==nullary || pc==postfix || pc==vallary || pc==nary)
 649             push({type=binary, binary.op=multiply}, true); //implicit multiply (e.g. 7a -> 7*a)
 650          p.b = expr;
 651          expr.mom = p;
 652          p = expr;
 653       } else {
 654          int order;
 655          Expression w;
 656          if (pc==prefix || pc==binary) {
 657             err.Printf("%s operator %s following operator %s; ignoring.\n", c==postfix ? "Postfix" : "Binary", expr.OpString(), p.OpString());
 658             delete expr;
 659             return;
 660          }
 661          order = expr.OpOrder();
 662          if (order<0) {
 663             err.Printf("BUG:  %s operator has invalid order; ignoring.\n", c==postfix ? "Postfix" : "Binary");
 664             delete expr;
 665             return;
 666          }
 667          //An AB operator is defined as a postfix or binary operator
 668          //For any binary operators that associate right-to-left, increment order so they can overtake sooner
 669          //Believe it or not, equals associates right-to-left (at least in C it does)
 670          if (expr.type==binary && (expr.binary.op==power || expr.binary.op==equals))
 671             order++;
 672          //We will walk up the tree with this AB operator until we find a w such that w.mom.order < op.order
 673          //If we reach the root node, that's a bug because the root node should have an order of 0
 674          w = p;
 675          for (;;) {
 676             int worder;
 677             if (!w.mom) {
 678                err.Printf("BUG:  Expression tree ended too soon while handling binary operator; ignoring.\n");
 679                delete expr;
 680                return;
 681             }
 682             worder = w.mom.OpOrder();
 683             if (worder<0) {
 684                err.Printf("BUG:  Bad parent encountered while handling postfix/binary operator.\n");
 685                delete expr;
 686                return;
 687             }
 688             if (implicit && expr.type==binary && expr.binary.op==multiply && w.mom.type==openfunction) {
 689                //this makes it so sin 3x will be sin(3x), while sin 3*x will be (sin 3)*x
 690                if (worder == binary_op_order[power])
 691                   break;
 692             } else if (order > worder)
 693                break;
 694             w = w.mom;
 695             if (w.type==openfunction)
 696                closeFunction(w);
 697          }
 698          //We will take w, make it op's left child, and put op where w was.
 699          expr.a = w;
 700          expr.mom = w.mom;
 701          w.mom = expr;
 702          expr.mom.b = expr;
 703          p = expr;
 704       }
 705    }
 706    //closes f (should only be called if f is an openfunction)
 707    void closeFunction(Expression f) {
 708       Expression child = f.b;
 709       if (child && child.type==parenthesis && child.parenthesis.type==parenthesis) {
 710          //remove the first set of parenthesis
 711          //if more sets of parenthesis surround this, the user really meant to have them there
 712          Expression tmp = child.b;
 713          child.b = null;
 714          delete f.b;
 715          child = f.b = tmp;
 716       }
 717       //Turn this from an openfunction into a function
 718       f.b = null;
 719       f.Free();
 720       f.type = function;
 721       f.arg = {};
 722          //note that f.function.func persists because Free() did not clear that
 723       //Collect all comma-delimited arguments into the arg array
 724       child.CollectTerms(comma, f.arg, f);
 725    }
 726    void finalize(void) {
 727       Expression w = p;
 728       while (w) {
 729          if (w.type==openfunction)
 730             closeFunction(w);
 731          w = w.mom;
 732       }
 733    }
 734 };
 735
 736 void ExpressionFromString(Expression expr, char *str, CASDictionary dictionary) {
 737    ExpressionTree tree {dictionary};
 738    char *s, *p, *e; //token start and end
 739    CASCharFlag flag;
 740    CASCharFlags cf = cascharflags;
 741    char borrow;
 742
 743    expr.Free();
 744
 745    s = str;
 746    e = s;
 747    while (*s) {
 748       for (;;) //for loop is used so multiple character types that merge into one token can be implemented in the future
 749       { //grab the next token
 750          byte f = cf.flags[(byte)*e++];
 751          while (cf.flags[(byte)*e]==f) e++;
 752          flag = (CASCharFlag)f;
 753          break;
 754       }
 755       p = s;
 756       switch (flag) {
 757          case letter: {
 758             uint f;
 759             uint i;
 760             int charlen;
 761             char borrow2;
 762             borrow = *e;
 763             *e = 0;
 764             f = dictionary.f.lookup(s, false);
 765             if (f != (uint)-1)
 766                tree.PushFunction((CASFunction)f);
 767             else do {
 768                unsigned char c;
 769                uint con = (uint)-1;
 770                UTF8GetChar(p, &charlen);
 771                p += charlen;
 772                borrow2 = *p;
 773                *p = 0;
 774                for (i=0; i<CASConstant::enumSize; i++) {
 775                   if (!strcmp(s, constant_string[(CASConstant)i])) {
 776                      con = i;
 777                      break;
 778                   }
 779                }
 780                if (con != (uint)-1)
 781                   tree.PushConstant((CASConstant)con);
 782                else
 783                   tree.PushVariable(s);
 784                *p = borrow2;
 785                s = p;
 786             } while (s<e);
 787             *e = borrow;
 788          }
 789             break;
 790          case number:
 791             borrow = *e;
 792             *e = 0;
 793             if (strchr(s, '.'))
 794                tree.PushFloat(s);
 795             else
 796                tree.PushInteger(s, e);
 797             *e = borrow;
 798             break;
 799          case op:
 800             //This only lexes one-character operators
 801             do {
 802                borrow = p[1];
 803                p[1] = 0;
 804                tree.PushOperator(p);
 805                p[1] = borrow;
 806                p++;
 807             } while (p<e);
 808             break;
 809       }
 810       s = e;
 811    }
 812    tree.finalize();
 813    memcpy(expr, tree.root, sizeof(class Expression));
 814    if (expr.b)
 815       expr.b.mom = expr;
 816    tree.root = null;
 817    delete tree;
 818 }
 819
 820 //This function walks the tree to make sure it is valid:
 821 //    no null expressions
 822 //    no open parenthesis/functions
 823 //    correct number of arguments for core functions (TODO)
 824 //While it's at it, it tags every expression in the tree
 825 //It also converts exp(foo) to e^foo (TODO)
 826 //returns true if the expression is valid and not empty
 827 bool Expression::Sanitize(CASDictionary dict) {
 828    if (!this || this.type==null)
 829       return false;
 830    ClearTags();
 831    #define S(x) {if (!Sanitize(x, dict)) return false;}
 832    switch (ExprClass()) {
 833       case prefix:
 834          if (type==openparenthesis || type==openfunction)
 835             return false;
 836          S(b);
 837          if (b.constant)
 838             constant = true;
 839          if (b.approx)
 840             approx = true;
 841          break;
 842       case vallary:
 843          S(b);
 844          if (type==parenthesis && parenthesis.type==parenthesis)
 845             Unlink();
 846          else {
 847             if (b.constant)
 848                constant = true;
 849             if (b.approx)
 850                approx = true;
 851          }
 852          break;
 853       case postfix:
 854          S(a);
 855          if (a.constant)
 856             constant = true;
 857          if (a.approx)
 858             approx = true;
 859          break;
 860       case binary:
 861          S(a);
 862          S(b);
 863          if (a.constant && b.constant)
 864             constant = true;
 865          if (a.approx || b.approx)
 866             approx = true;
 867          break;
 868       case nary:
 869          constant = true;
 870          approx = false;
 871          for (iter:arg) {
 872             S(iter);
 873             if (!iter.constant)
 874                constant = false;
 875             if (iter.approx)
 876                approx = true;
 877          }
 878          if (!dict.f.Sanitize(this))
 879             return false;
 880          break;
 881       case nullary:
 882          if (type!=v)
 883             constant = true;
 884          if (type==f)
 885             approx = true;
 886          break;
 887    }
 888    #undef S
 889    return true;
 890 }