øAslickproductions.org/forum/index.php?PHPSESSID=5f0fck550j2m4m2fpbtkj2vkm1&action=printpage;topic=457.0e:/My Web Sites/Slick Productions - FFIV Message Board/slickproductions.org/forum/index6b86.htmlslickproductions.org/forum/index.php?PHPSESSID=5f0fck550j2m4m2fpbtkj2vkm1&topic=457.0e:/My Web Sites/Slick Productions - FFIV Message Board/slickproductions.org/forum/index6b86.html.zx¡dh^ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÈÐô[ e"OKtext/htmlISO-8859-1gzip0|Öe"ÿÿÿÿÿÿÿÿWed, 11 Mar 2020 04:26:34 GMT0ó°° ®0®P®€§²ð®¡dh^ù e" Print Page - Wrote the expression parser last night.

Board of Slick

Original Fantasy => General Discussion => Topic started by: Entroper on March 27, 2008, 10:32:03 AM

Title: Wrote the expression parser last night.
Post by: Entroper on March 27, 2008, 10:32:03 AM
I love trees, recursion, and polymorphism.   :happy:
Title: Re: Wrote the expression parser last night.
Post by: JCE3000GT on March 27, 2008, 07:02:32 PM
I love trees, recursion, and polymorphism.   :happy:

You know what's coming...































 :picsorstfu:
Title: Re: Wrote the expression parser last night.
Post by: Lenophis on March 27, 2008, 09:21:50 PM
I'm more wondering what that post was about in the first place. Give explanation! Or I may send the :cookie: after you...
Title: Re: Wrote the expression parser last night.
Post by: Odbarc on March 27, 2008, 11:29:14 PM
I love trees, recursion, and polymorphism.   :happy:

I have no idea what your talking about, but I'm excited!
Title: Re: Wrote the expression parser last night.
Post by: Entroper on March 29, 2008, 04:59:34 PM
Well, for those who don't know programming, you won't understand.  For those who do...

The expression system is a tree data structure, where each node in the tree is a class derived from the Expression abstract base class.  Leaf nodes are literals or variable names, and non-leaf nodes are operators like +, -, AND, OR, >, <, etc.  So when your expression contains a +, there's a node in the tree for the + which has two expressions as children.  That's the trees.

The recursion comes as a natural result of working with trees.  To evaluate an operator like +, you simply evaluate its sub-expressions, add the results together, and return the answer.  The recursion stops when you evaluate a literal or variable node (which just returns the value).  And the polymorphism comes in with the Evaluate() function being a pure virtual function in the Expression class.
Title: Re: Wrote the expression parser last night.
Post by: Entroper on March 29, 2008, 06:44:11 PM
I'm working on ways to display the expressions as strings and write them to files for the script editor now.

Can you guys deal with prefix notation?  It's definitely going to be that way in the file, and I think it'll be viewable as a tree in the editor.  But it would be nice to collapse the tree down to a single line, and I don't want people to be horribly confused by prefix notation.  Prefix notation is where you write + 2 3 instead of 2 + 3, or * 5 + 2 3 instead of 5*(2+3) for example.
Title: Re: Wrote the expression parser last night.
Post by: Deathlike2 on March 29, 2008, 07:06:00 PM
Notation that follows the order of (math/algebraic) operations would be preferred.
Title: Re: Wrote the expression parser last night.
Post by: Entroper on March 29, 2008, 11:11:55 PM
Yeah, I should NOT have written that code after driving back down from DC last night.  I just now got it to pass my tests after spending the last hour fixing a huge number of errors.  :bah:
Title: Re: Wrote the expression parser last night.
Post by: Entroper on March 30, 2008, 12:21:12 AM
Note for future reference:

Code: [Select]
return new ExprBinaryOp(op, BuildExpression(in), BuildExpression(in));
Seems like a simple line of code.  Interestingly enough, in testing, it turns out that the second call to BuildExpression() actually executes first!  Since it is important that expressions are read from files in the same order as they are written to files, this resulted in the order of operations being reversed.  I had to change the above to:

Code: [Select]
Expression *lhs = BuildExpression();
Expression *rhs = BuildExpression();
return new ExprBinaryOp(op, lhs, rhs);
This ensured the order was correct.  Pretty strange if you ask me... I had no idea that function parameters were not always evaluated left-to-right.