I think code says thing clearer, here I pasted
a simplified version of my implementation with
depth-tranverse. Note: this simplified version cannot
handle unary computation. To read the real version,
please read one source file of Yuan at:
http://cvs.sourceforge.net/viewcvs.py/yuan-language/yuan_devel/source/yn_expression.cpp?view=markup
I just mention a few points in the following codes:
1. evaluation is done during traverse.
2. no need to store "node"s or temporary variables in
a list/queue/stack.
3. when eval() is called, it knows the exact type of
the object.
class node{
// booleans to tell the type of node:
bool isVariable,isSomethingElse;
char oper; // operator
double value; // temporary value
something *tempVarForSomething;
node *left,*right; // pointers to its sons
node *parent; // pointer to its parent
void eval();
void trav();
};
void node::eval()
{
if(oper=='+')
value=left->value+right->value;
else if ....
}
void node::trav()
{
node *p=this;
while(1){
// go along "right" to reach a leaf:
while(p->right) p=p->right;
if(p->isVariable){
// get the value:
p->value=...;
}else if(p->isSomethingElse){
// do something else
}
if(!p->parent) break;
// if "p" is a "left" son:
if(p==p->parent->left){
// go back to "parent"
p=p->parent;
// evaluation:
p->eval();
if(p==this) break;
}
if(p==this) break;
// Now "p" must be a "right" son,
// jump to the "left"
p=p->parent->left;
}
}
--- "Diez B. Roggisch" <[EMAIL PROTECTED]> wrote:
> > No, in the depth-traversal implementation, a
> function
> > can avoid calling itself (at least in my
> > implementation it's like this).
>
> How so? It has to keep state of which nodes to visit
> - so instead of calling
> trav, you call functions to store and fetch nodes in
> a container like a
> stl-list. That's the same cost, function-call is
> function call.
>
> There is no difference - you simply decoupled the
> tree traversal from the
> evaluation - but combined, its the same effort. It's
> like in my second
> example with bytecodes - the traversal is done
> beforehand (and only once),
> and then the eval is only done on the nodes in a
> row.
>
> > Because you can write seperate functions: a
> function
> > for depth-traversal (say trav()) and another
> function
> > for evaluation (say eval()). trav() may call
> eval().
> > And eval() NEVER call other functions. For one
> > arithmetic tree, trav() is called once, and eval()
> is
> > called by trav() at each node. So it is not
> recursive.
> >> Now apart from that, I still fail to see where
> your
> >> method of evaluation has
> >> any speed gains.
> >
> > And if you inplement eval() as an "inline"
> function,
> > there will be no cost for function calls for
> eval().
> > In this way it can gain some speeds.
>
> No. Inlining works only when the actual type of your
> node is known, e.g.
> like this (Constant and Variable are both of type :
>
> {
> Constant left;
> Variable right;
>
> left.eval();
> right.eval();
> }
>
> Here the compiler can take advantage from the fact
> that it knows at
> compiletime which eval to inline
>
> But if you have
>
> {
> list<Node> nodes;
> for(nodes::iterator it = nodes.begin(); it !=
> nodes.end(); it++) {
> (*exp).eval();
> }
> }
>
> the compiler can't possibly know which node is in
> exp- so it has to resort
> to a vtable-lookup and a method call on the result.
>
> --
> Regards,
>
> Diez B. Roggisch
> --
> http://mail.python.org/mailman/listinfo/python-list
>
__________________________________
Do you Yahoo!?
Yahoo! Mail - Easier than ever with enhanced search. Learn more.
http://info.mail.yahoo.com/mail_250
--
http://mail.python.org/mailman/listinfo/python-list
