// Expression Tree // // The Copyright for this file is shared equally by the // Contributors listed below // // Contributors: Alan Hadley // // You may use, modify and distribute this file as you see // fit, so long as this notice remains intact, you // may add your name to the contributors if you wish if you // distribute modified versions of the file // // The Copyright holder(s) do not guarantee that the software // is fit for any purpose, nor will they accept responsibility // for any consequences of its use. #ifndef EXPCLASS_H #define EXPCLASS_H #include "math.h" #include "qstring.h" #include "qhash.h" #define MAX_LINKS 32 #define FREE -1 #ifdef QT_DEBUG #define VALID_NODE(n) (n>-1 && n-1) #define VALID_LINK(n,l) (l>-1 && l Less, // < Colon, // : // logic Or, // left for user to impliment And, // arithmetoc Plus, // + each term can be minus Times, // * can be negative Devide, // / can be negative Power, // ^ can be negative, as can child 1 // note '-' is not an operator, it is a property of a node // is not signed but its children are MultiOp, // formed from other op symbols, use spaces to disambiguate MultiEq, // MultiOp with <, =, > or : arguments not simplified // pre and postfix group // prefix can be negative, postfix the child can Excl, // ! SQuote, // ' Not, // ` also used in Fracs At, // @ Tilda, // ~ Question, // ? Dot, // . also decimal point // leaves or atoms Number, // double precision, large and small 1.5e+100 etc. Frac, // (1`1/2) is one and a half Symbol, // name formed from a-z, A-Z, _ and 0-9 after start PlaceHolder, // not printed Back // backslash escape characters }; // The Main Class // You can use 0,0 for the arguments if you are not // going to manage Symbols. // Or you can set 1 or 2 static Call Back functions // 1. bool Unknown(Exp *E,int node) // 2. bool Sym(Exp *E,int node,int key,bool eval) // E - is a reference to this instance of the parser // node - is the current instance of the symbol // key - is an int which is managed by the user and // is the same in all instances of this symbol // eval - is a flag indicating whether the Callback was // called while Evaluating or Simplifying an expression. // Unknown is called every time the parser encounters an // unregistered symbol or function. It is your opertunity to // AddSym(name,key), the key value is for your use // e.g. as flags or an index into an array etc. // Use node to Get information about the symbol // e.g. QString name=E.GetText(node). // When evaluating you can replace this instance with // a value e.g. E.ToNumber(node,value). Remember to // return true if you modify anything, but return // false if you make no change. You will get in an // infinite loop if you always return true. Exp(bool(*nv)(Exp *E,int),bool(*v)(Exp *E,int,int,bool)); ~Exp(); // For new expression Start will be its Parent // it returns the number of the node at the root // of this expressions tree. // e.g. int e1=E.NewExp("3*5"); followed by // QString result=E.GetText(e1); will return "15". // Remember to E.Free(e1); when you no longer need it, // or destroy the class. int NewExp(QString e); // replace exp, keep same Root node // returns true for success. // QString E.ERROR will contain any error message. bool ReplaceExp(int node,QString exp); // Copy node and decendants // returns node number of new expression tree root int Copy(int node); // convert to standard internal format // this expands where it can and sorts the result void Simplify(int node); // Free a node and its decendants for reuse // do not try to use a node once you have Freed it. bool Free(int node); // how many links node has // e.g. if you have e1=NewExp("a+b+c"); // then LinksCount(e1) will return 3, e1 is a Plus // node and this is linked to a, b, and c int LinksCount(int node); // swap positions of two child nodes in Links list // in the example above SwapLinks(node,0,1) followed // by ExpText(e1) will return "b+a+c". void SwapLinks(int node,int pos1,int pos2); // gets Link at pos in Link list // the first node link is always at position 0 int GetLink(int node,int pos); // get and remove link at pos // remember to Free it if you no longer need it int TakeLink(int from,int pos); // access to parents properties; NodeType ParentType(int node); // member of Exp::NodeType QString ParentText(int node); // e.g op symbol or fun name double ParentValue(int node); // Node Value, without sign etc. int ParentA(int node); // numerator of Frac, lower half key for Symbol int ParentB(int node); // numerator of Frac, lower half key for Symbol int ParentSign(int node); // of Op or Leaf int ParentPos(int node); // position in parents links list // access to a nodes data double ValueOf(int node); // Full value including sign, and Frac parts double ValueOf(int node,int l); // Same for a child node double GetValue(int node); // Node Value, without sign etc. double GetValue(int node,int link); void SetValue(int node,double value); void SetValue(int node,double value,int link); NodeType GetType(int node); // member of Exp::NodeType NodeType GetType(int node,int pos); // same for a nodes child QString GetText(int node); // e.g op symbol or fun name QString GetText(int node,int pos); void SetText(int node,QString s); void SetText(int node,QString s,int link); int GetA(int node); // numerator of Frac, lower half key for Symbol int GetA(int node,int link); void SetA(int node,int a); void SetA(int node,int a,int link); int GetB(int node,int link); int GetB(int node); // denominator of Frac, upper half key for Symbol void SetB(int node,int b); void SetB(int node,int b,int link); int GetSign(int node); // of Op or Leaf int GetSign(int node,int link); void SetSign(int node,int sign); void SetSign(int node,int sign,int link); // if a quantity is not used by the parser you are free to // use it. Remember setting something only sets it for // one instance of that node type. // Reform expression text from root onwards QString ExpText(int root); // calls user functions, to substitute symbols etc. void Evaluate(int node); // sort all node and decendants Links void Sort(int Node); // sort nodes Links only bool SortLinks(int node); // make x+y into 1*x+1*y+0 so it looks like a*x+b*y+c // group non init items in brackets in +, so + has one constant // make x*y into 1*x*y so it looks like a*x*y, and group as above // copy Number values to their Text, so they work as inits void Consts(int node,QList &parts); // Signature // $ marks where initial parts are // # where non initial parts are, these are grouped // two digit numbers refer to index of part in list // condensed signature is next to last in parts // full sig with numbers is last // # values are left to right starting after inits void Signature(int node,QList &parts); // fill a QList with the text from the children of a node // used to get the entries from a vector etc. // this function can also get entries from chains of a binary operator, // e.g. (a<<(b<<(c<<(d< &parts); // fill a Qlist with the text from the childrens children provided the children // are of type type. used to get the entries from a matrix etc. e.g if a node // is type Semicolon E->PartsText(node,EXP::Comma,parts,counts) would retreave // the entries from a,b;c,d as four entries in parts, counts would have two entries // 2 and 2. The return value is true if all sublists are the same length, i.e. a rectangular array. // counts.count() is how many rows there are, i.e. children of node, if the type of any of these // does not match type the corresponding count entry is zero. bool PartsText(int node,int type,QList &parts,QList &counts); // similar to above but for values int PartsValues(int node,QList &values); bool PartsValues(int node,int type,QList &values,QList &counts); // check that all decendants of node are the same type e.g. LinksAllType(node,Exp::Number) // tip make sure to evaluate node if inside {} for numbers bool LinksAllType(int node,int type); // as above but two types e.g. LinksAllType(node,Exp::Comma,Exp::Number) bool LinksAllType(int node,int type1,int type2); // Move link to start in Plus and Times etc. int MoveText(int node,QString text); // Move children with type to pos 0 // return count of how many moved. // If node is type, count is -ve, // abs(count) is count+1 in this case // count= count<0? abs(count+1) : count int MoveType(int node,int type); // Move links with children that match, // also move matching child, if allowed. // Count is in hex 0x12 would mean, no zeros, // link[0].link[0] matches and, // link[1].link[0] and link[1].link[1] match too // return unpridictable with too many links i.e. >15 // if primary link is leaf might return 1, // so check number of links if this is possible // you can detect a in a+b+c and in a*n+b+c etc. unsigned int MoveTText(int node,QString text); unsigned int MoveTType(int node,int type); // Fracs use a and b, leave alone // A symbols Key is split in two and stored in a,b // a=key & 0xffff and b=key & 0xffff0000 // so you can group symbols as you like // otherwise use as you will, remember different // instances of something can have different values int MoveA(int node,int a); int MoveB(int node,int b); unsigned int MoveAA(int node,int a); unsigned int MoveBB(int node,int b); // Symbol management // add a symbol with a key of your choice // if you try to get a sym not in list unknown_key is returned // unknown_key value will change if it clashes static int unknown_key; bool AddSym(QString name,int key); int GetSym(QString); void DeleteSym(QString name); // Please note I use Symbol loosly, it includes // symbols that stand for constants. Also a variables // need not be numeric it all depends how you treet it // in your callback functions {s1+s2} could concatenate // strings, note the {} brackets which tell the parser // to leave their contents alone. You could issue a // string of commands as a comma seperated list. // list all symbols keys that are decendants of node void ListSyms(int node,QList &syms); // checks that text does not match the text of any decendant bool FreeOf(int node,QString text,int depth); // same for type bool FreeOf(int node,int type,int depth); // useful in callbacks to decide if change worth it int GetRoot(int node); int GetSize(int node); // register callback functions // these are called at two times // first from Simplify with eval set to false // then from Evaluate with eval set to true // use first to validate/modify function // use second to provide numeric values etc. // In a callback you can modify the function and // its decendants, do not modify it's parent, though // you may check its type etc. // For direct modifications use Insert, Adopt, To and // Over, as well as setting node parameters and using // Free, GetLink, SwapLinks, Move and Sort etc. // For more drastic changes use Replace which takes a // QString as input to replace a whole expression or // sub-expression. // Collect information using the Get functions. // Compare parts of, or the whole expression using // Signature, to reduce the number of variations you // may need to check use Const first. // -, # and $ are reserved // !, `, ., @, ~, ? are pre- or postfix void addPrePostFun(QString name,bool (*f)(Exp *E,int n,bool pre,int arg,NodeType t,bool eval)); void ResetPrePostFuns(){PPFuns.clear();} // +, *, /, ^, &, |, \, :, <, =, > // and combinations of these and - and pre- and postfix // compound operaters are all binary, but they can behave // like pre- and postfix by including a PlaceHolder // Node last or first respectively. // the only operators that can have more than two children // are Plus +, Times *, And &, and Or |. void addOpperatorFun(QString name,bool (*f)(Exp *E,int n,bool eval)); void ResetOpperatorFuns(){OPFuns.clear();} // syms start with letter or _ then letters _ or digits void addSymFun(QString name,bool (*f)(Exp *E,int n,bool eval)); void ResetSymFuns(){Symbols.clear();} // convert a Number to a Frac bool MakeFrac(int n); // The Bracket Functions come in various combinations. // Seperate their arguments with Comma lists, these // can be grouped into semicolon superlists // You can register a function without a name using // (), {}, [], (){}, ()[], {}(), {}[], [](), []{} // and {}(){}. Add a name in front of any of these to // get a named function. Each function can have one // child node corresponding to each pair of brackets, // either an atom, operator or a comma or semicolon list etc. // () can be removed by Simplify if it does not contain a // list. Simplify can also modify the arguments in the list, // but not their order. // {} protects its contents from modification by the // parser though the user can initiate it. // [] The system cannot remove these brackets but it // can modify their contents. // suggested usages sin(x) use () in the usual way. // D(x^2){x} use curley brackets to indicate symbols // of interest this is my derivative function, {x} can be // interprited as dx. I{0,1}(x^2){x} could be a definite // integral with the limits 0 and 1. // [] brackets can be used for Matrices, arrays, vectors, // coordinates etc. M[1,0,0;0,1,0;0,0,1] would be a // 3x3 identity matrix, or you could use I[3]. // Remove a function using AddRFun(name,0) etc. // name() void addRFun(QString name,bool (*f)(Exp *E,int n, int arg,NodeType t, bool eval)); void ResetRFuns(){RFuns.clear();} // name(){} void addRCFun(QString name,bool (*f)(Exp *E,int n, int arg1,NodeType t1, int arg2,NodeType t2, bool eval)); void ResetRCFuns(){RCFuns.clear();} // name()[] void addRSFun(QString name,bool (*f)(Exp *E,int n, int arg1,NodeType t1, int arg2,NodeType t2, bool eval)); void ResetRSFuns(){RSFuns.clear();} // name{} void addCFun(QString name,bool (*f)(Exp *E,int n, int arg,NodeType t, bool eval)); void ResetCFuns(){CFuns.clear();} // name{}() void addCRFun(QString name,bool (*f)(Exp *E,int n, int arg1,NodeType t1, int arg2,NodeType t2, bool eval)); void ResetCRFuns(){CRFuns.clear();} // name{}(){} void addCRCFun(QString name,bool (*f)(Exp *E,int n, int arg1,NodeType t1, int arg2,NodeType t2, int arg3,NodeType t3, bool eval)); void ResetCRCFuns(){CRCFuns.clear();} // name{}[] void addCSFun(QString name,bool (*f)(Exp *E,int n, int arg1,NodeType t1, int arg2,NodeType t2, bool eval)); void ResetCSFuns(){CSFuns.clear();} // name[] void addSFun(QString name,bool (*f)(Exp *E,int n, int arg,NodeType t, bool eval)); void ResetSFuns(){SFuns.clear();} // name[]() void addSRFun(QString name,bool (*f)(Exp *E,int n, int arg1,NodeType t1, int arg2,NodeType t2, bool eval)); void ResetSRFuns(){SRFuns.clear();} // name[]{} void addSCFun(QString name,bool (*f)(Exp *E,int n, int arg1,NodeType t1, int arg2,NodeType t2, bool eval)); void ResetSCFuns(){SCFuns.clear();} // from N[grand]->N[child] // to N[grand]->N[parent]->N[child] // return child, which has moved int InsertPlus(int orig); int InsertTimes(int orig,int sign); int InsertDevide(int orig,int sign); int InsertPower(int orig,int sign); int InsertComma(int orig); int InsertSemi(int orig); int InsertPrefix(int orig,NodeType t,int sign); int InsertPostfix(int orig,NodeType t); int InsertEqual(int orig,NodeType t); int InsertRBracket(int orig,int sign); int InsertRCBracket(int orig,int sign); int InsertRSBracket(int orig,int sign); int InsertCBracket(int orig,int sign); int InsertCRBracket(int orig,int sign); int InsertCRCBracket(int orig,int sign); int InsertCSBracket(int orig,int sign); int InsertSBracket(int orig,int sign); int InsertSRBracket(int orig,int sign); int InsertSCBracket(int orig,int sign); int InsertRFun(int orig,int sign,QString name); int InsertRCFun(int orig,int sign,QString name); int InsertRSFun(int orig,int sign,QString name); int InsertCFun(int orig,int sign,QString name); int InsertCRFun(int orig,int sign,QString name); int InsertCRCFun(int orig,int sign,QString name); int InsertCSFun(int orig,int sign,QString name); int InsertSFun(int orig,int sign,QString name); int InsertSRFun(int orig,int sign,QString name); int InsertSCFun(int orig,int sign,QString name); void Adopt(int parent,int child); // from N[parent] // to N[parent]->N[child] // returns child int AdoptNumber(int parent,double value); int AdoptFrac(int parent,int Int,int a,int b); int AdoptSym(int parent,QString name,int sign); int AdoptPlaceHolder(int node1); int AdoptPlus(int parent); int AdoptTimes(int parent,int sign); int AdoptDevide(int parent,int sign); int AdoptPower(int parent,int sign); int AdoptComma(int parent); int AdoptSemi(int parent); int AdoptPrefix(int parent,NodeType t,int sign); int AdoptPostfix(int parent,NodeType t); int AdoptEqual(int parent,NodeType t); int AdoptRBracket(int parent,int sign); int AdoptRCBracket(int parent,int sign); int AdoptRSBracket(int parent,int sign); int AdoptCBracket(int parent,int sign); int AdoptCRBracket(int parent,int sign); int AdoptCRCBracket(int parent,int sign); int AdoptCSBracket(int parent,int sign); int AdoptSBracket(int parent,int sign); int AdoptSRBracket(int parent,int sign); int AdoptSCBracket(int parent,int sign); int AdoptRFun(int parent,int sign,QString name); int AdoptRCFun(int parent,int sign,QString name); int AdoptRSFun(int parent,int sign,QString name); int AdoptCFun(int parent,int sign,QString name); int AdoptCRFun(int parent,int sign,QString name); int AdoptCRCFun(int parent,int sign,QString name); int AdoptCSFun(int parent,int sign,QString name); int AdoptSFun(int parent,int sign,QString name); int AdoptSRFun(int parent,int sign,QString name); int AdoptSCFun(int parent,int sign,QString name); // overwrite old node with new // free new node, but not its Links // old nodes links replaced by new links // you need to look after old nodes Links void Over(int dest,int src); // from N[node(old)] // to N[node(new)] // Frees olds Links void ToNumber(int dest,double value); void ToSymbol(int dest,QString name); void ToFrac(int dest,int Int,int a,int b); void ToPlus(int dest); void ToPlaceHolder(int dest); void ToTimes(int dest,int sign); void ToDevide(int dest,int sign); void ToPower(int dest,int sign); void ToComma(int dest); void ToSemi(int dest); void ToPrefix(int dest,NodeType type,int sign); void ToPostfix(int dest,NodeType type); void ToEqual(int dest,NodeType type); void ToRBracket(int dest,int sign); void ToRCBracket(int dest,int sign); void ToRSBracket(int dest,int sign); void ToCBracket(int dest,int sign); void ToCRBracket(int dest,int sign); void ToCRCBracket(int dest,int sign); void ToCSBracket(int dest,int sign); void ToSBracket(int dest,int sign); void ToSRBracket(int dest,int sign); void ToSCBracket(int dest,int sign); void ToRFun(int dest,int sign,QString name); void ToRCFun(int dest,int sign,QString name); void ToRSFun(int dest,int sign,QString name); void ToCFun(int dest,int sign,QString name); void ToCRFun(int dest,int sign,QString name); void ToCRCFun(int dest,int sign,QString name); void ToCSFun(int dest,int sign,QString name); void ToSFun(int dest,int sign,QString name); void ToSRFun(int dest,int sign,QString name); void ToSCFun(int dest,int sign,QString name); private: int MyRoot,YourRoot; bool IsMinus; int close_bracket; int last_added; bool hasnumbers; bool hasbrackets; bool hasquotes; bool(*Unknown)(Exp *E,int); bool(*Sym)(Exp *E,int,int,bool); QHash RFuns; QHash RCFuns; QHash RSFuns; QHash CFuns; QHash CRFuns; QHash CRCFuns; QHash CSFuns; QHash SFuns; QHash SRFuns; QHash SCFuns; QHash PPFuns; QHash OPFuns; enum TokenType { tNothing, tStop, tError, tInt, tNumber, tFrac, tQuote, tPlaceHolder, tWord, tMultiOp, tMultiEq, tEscape, tSpace=' ', tPlus='+', tMinus='-', tTimes='*', tDevide='/', tPower='^', tExcl='!', tLess='<', tEqual='=', tMore='>', tAnd='&', tOr='|', tBack='\\', tNot='`', tComma=',', tDot='.', tSemi=';', tColon=':', tDollar='$', tORB='(', tCRB=')', tOCB='{', tCCB='}', tOSB='[', tCSB=']', tDQuote='\"', tSQuote='\'', tAt='@', tTilda='~', tHash='#', tQuestion='?' }; struct Token { QString s; double v; TokenType typ; }; QList tokens; bool MultiOps_test(int i); void FindMultiOps(); // and multieq void FindQuotes(); void FindNumbers(); void CheckBrackets(); void Tokenize(QString exp); enum Level { LRoot, LBracket, LSemi, LComma, LEqual, LBack, LOr, LAnd, LSQuote, LPlus, LTimes, LDevide, LPower, LMultiOp, LPrefix, LPostfix, LLeaf }; enum Fix { Nofix, Prefix, Postfix, Infix, Groupfix, Rootfix }; struct Item { NodeType type; int root,parent; int me; QList links; int min,max; Level level; Fix fix; double value; int a,b,sign; QString text; }; int NsCount; // allocated nodes QList N; // all nodes QList AN; // active node stack int an; // active node QList POS; // position since start or last bracket int pos; // current position QList FreeNs; QList UsedNs; QHash Symbols; int NewN( NodeType type, int min, int max, Level level, int sign, double value, int a, int b, QString text, Fix fix); bool AddN(int node); bool LeafN(NodeType t, QString text, double value, int a, int b); bool PrePostN(int &i,NodeType t, QString text); bool GroupN(int &i,int nt,NodeType t,QString text,double value); bool DoubleGroupN(TokenType t,TokenType tt); bool InfixN(int i,NodeType t,int maxch,Level level,QString text,double value); int BuildTree(); bool IsInt(double d); bool IsInt(int node); int CompareNs(int n1,int n2,bool Abs); bool CancelFrac(int node); double FracToDouble(int n); bool CancelInt(int &a,int &b); bool CancelDbl(double &a,double &b); bool SimplyDefault(int node); bool SimplyStop(int node); bool SimplyNumber(int n); bool SimplyFrac(int n); bool SimplySym(int node); bool SimplyBracket(int node); void AddEr(int n1,int n2); bool SimplyPlus(int node); void MulEr(int n1,int n2); bool SimplyTimes(int node); void DevEr(int n1,int n2); bool SimplyDevide(int node); void PowEr(int n1,int n2); bool SimplyPower(int node); bool SimplyMulti(int node); bool simplifyN(int node); QList FoundNs; void FindNodes(int node); bool DoCallbacks(); int Insert(int orig,int insert); bool evaluate(int node); int CopyTo(int node); bool free(int node); void signature(int node,QString &s,QString &sig,QList &parts,int ninit); // Build strings for output QString BuildPrePostText(int root); QString BuildInfixText(int root,QString text); QString BuildFracText(int root); QString exptext(int root); bool linksalltype(int node,int type); bool linksalltype(int node,int type1,int type2); int root; int parent; void UpdateNodes(int node); void updatenodes(int node); }; #endif // EXPCLASS_H