What does it mean with infix

[Andre Caldas]

Hello!

You obviously never had a HP pocket calculator

No... I think they must be pretty usefull for engineers, though.

preorder: the node first, then left subtree, right subtree
inorder: left subtree first, node, right subtree
postoder: left subtree first, right subtree, node

This was enlightening, thank you.
By the way, is there anything good about preorder? I tryied to think of
a machine to execute it is much more complicated then postorder: that
is, I need one stack for the operands, and one "buffer" to store the
result. (well, the words on the operand stack could have only 2 bits
each - +,-,/,* -, and thats good! - you cannot use this reason ;-))

Parsing is not the problem. Evaluating is!
With inorder notation, you need to incorporate the arithmetic rules
of precedence. It is not uncommon for compilers to first build
an expression tree from an infix notation, traverse that expression
tree in postorder and emit the code from that postorder traversel.
Why? Because arithmetic precedence has already been dealt with during
parsing and the tree has organized the opertions already correctly.

That's what I ment, sorry. Actually I guess it would be harder to
construct a tree from "postfix" or "prefix", since you would have to
start from the leaves.

in a more functional approach (as eg. in Lisp) the whole expression
can be written as:

add( 1, times( add( 2, 3 ), 4 ) )

I guess this was what it was all about. If the "functional" thing was
"infix" or "postfix".

Thank you.

 

[Andre Caldas]

I guess this was what it was all about. If the "functional" thing was

"infix" or "postfix".

Yes, I know, I know... (you guys are picky!)
"postfix" or "prefix" (nobody thinks it is "infix")

 

[Risto Lankinen]

I don't know if [infix] is "superior", but it is much easier to parse
since there are no recursions.

Parsing is not the problem. Evaluating is!
With inorder notation, you need to incorporate the arithmetic rules
of precedence. It is not uncommon for compilers to first build
an expression tree from an infix notation, traverse that expression
tree in postorder and emit the code from that postorder traversel.
Why? Because arithmetic precedence has already been dealt with during
parsing and the tree has organized the opertions already correctly.

Even easier way (yet quite neglected by the common "grammar
driven" parser development) is to use object-orientation and put
the intelligence into the parse tree nodes themselves:

class BinaryExpression
{
Expression *my_lhs;
Expression *my_lhs;

Expression *Plus( Expression * ) = 0;
Expression *Times( Expression * ) = 0;
}

class AdditionNode : public BinaryExpression ...
class MultiplicationNode : public BinaryExpression ...

// Showing just these to illustrate how precedence is dealt with:

Expression *AdditionNode::Times( Expression *operand )
{
return new AdditionNode( my_lhs,my_rhs->Times(operand) );
}

Expression *MultiplicationNode:lus( Expression *operand )
{
return new AdditionNode( this,operand );
}

.... etc...

Now, the expression grammar can be [basically] as simple as...

Expression : Operand | Operand Binary_op Expression

.... instead of being a set of gazillion expression rules in different
precedence levels for arithmetic operator alone. Also, all of the
intermediate expressions are evaluable and type-deducible which
allows for "real-time" calculation, syntax coloring, etc. neat tricks.

- Risto -

P.S. Note how a similar distinction in the implementation of
AdditionNode:lus() or MultiplicationNode::Times() can be
used to control the associativity of each operator respectively.

 

[Andre Caldas]

Andre Kaldas wrote:

Andre Caldas

I don't know if [infix] is "superior", but it is much easier to parse
since there are no recursions.

*snip*

It is not uncommon for compilers to first build
an expression tree from an infix notation, traverse that expression
tree in postorder and emit the code from that postorder traversel.

*snip*

Even easier way (yet quite neglected by the common "grammar
driven" parser development) is to use object-orientation and put
the intelligence into the parse tree nodes themselves:

class BinaryExpression
{
Expression *my_lhs;
Expression *my_lhs;

Expression *Plus( Expression * ) = 0;
Expression *Times( Expression * ) = 0;
}

class AdditionNode : public BinaryExpression ...
class MultiplicationNode : public BinaryExpression ...

// Showing just these to illustrate how precedence is dealt with:

Expression *AdditionNode::Times( Expression *operand )
{
return new AdditionNode( my_lhs,my_rhs->Times(operand) );
}

Expression *MultiplicationNode:lus( Expression *operand )
{
return new AdditionNode( this,operand );
}

... etc...

So, you are going to "parse" the expression and construct a tree just
like Karl said.

 

[Karl Heinz Buchegger]

Hello!


No... I think they must be pretty usefull for engineers, though.


This was enlightening, thank you.
By the way, is there anything good about preorder? I tryied to think of
a machine to execute it is much more complicated then postorder: that
is, I need one stack for the operands, and one "buffer" to store the
result. (well, the words on the operand stack could have only 2 bits
each - +,-,/,* -, and thats good! - you cannot use this reason ;-))

I could be wrong or remember incorrectly.
But I think that the maximum number stack size is little bit lower with
preorder then with postorder.

That's what I ment, sorry. Actually I guess it would be harder to
construct a tree from "postfix" or "prefix", since you would have to
start from the leaves.

Not really.
Consider 'evaluation' as 'building the tree'.
As has been shown evaluation of preorder or postorder expressions
is simpler (because you don't need some () and the arithmetic
precedence rules have to be dealt with already ), the construction
of such a tree is simpler too.

postorder:
All you need is a stack of trees.

algorithm:
if the next input is a number: create a 'tree' from it and
push it on the stack
if the next input is an operation (binary assumed): pop
2 trees from the stack, form a new tree combining the operation
with those 2 trees and push it on the stack.

1 2 3 + 4 * +


1 -> push on stack +--------+
| 1 |
+--------+

2 -> push on stack +--------+
| 1 |
+--------+
| 2 |
+--------+

3 -> push on stack +--------+
| 1 |
+--------+
| 2 |
+--------+
| 3 |
+--------+

+ -> pop 2 times, new tree, push +--------+
| 1 |
+--------+
| + |
| / \ |
| 2 3 |
+--------+

4 -> push on stack +--------+
| 1 |
+--------+
| + |
| / \ |
| 2 3 |
+--------+
| 4 |
+--------+

* -> pop 2 times, new tree, push +-------------+
| 1 |
+-------------+
| * |
| / \ |
| + 4 |
| / \ |
| 2 3 |
+-------------+

+ -> pop 2 times, new tree, push +-------------+
| + |
| / \ |
| 1 * |
| / \ |
| + 4 |
| / \ |
| 2 3 |
+-------------+

Finished, the stack contains the tree.

I am sure you can figure out how the same thing works with
a preorder tree.

Hint: Where else is this usefull besides evaluation of expressions.
Well. Think of storing a tree in a file and reconstructing
it from the file. Or: sending a tree through a network. Or ....
In other words: Whenever you need to serialize a tree.

 

[Andre Caldas]

Hello!

I hope you had a nice weekend...

I could be wrong or remember incorrectly.
But I think that the maximum number stack size is little bit lower with
preorder then with postorder.

You cannot use this... anything else?

Not really.
Consider 'evaluation' as 'building the tree'.

You where so picky about the difference between "parsing" and
"evaluating"... I am getting confused.

For me (no formal education on the subject), "parsing" is like 'building
the tree'. While evaluating is like 'running through it'.

As has been shown evaluation of preorder or postorder expressions
is simpler (because you don't need some () and the arithmetic
precedence rules have to be dealt with already ), the construction
of such a tree is simpler too.

postorder:
All you need is a stack of trees.

algorithm:
if the next input is a number: create a 'tree' from it and
push it on the stack
if the next input is an operation (binary assumed): pop
2 trees from the stack, form a new tree combining the operation
with those 2 trees and push it on the stack.

1 2 3 + 4 * +


1 -> push on stack +--------+
| 1 |
+--------+

2 -> push on stack +--------+
| 1 |
+--------+
| 2 |
+--------+

3 -> push on stack +--------+
| 1 |
+--------+
| 2 |
+--------+
| 3 |
+--------+

+ -> pop 2 times, new tree, push +--------+
| 1 |
+--------+
| + |
| / \ |
| 2 3 |
+--------+

4 -> push on stack +--------+
| 1 |
+--------+
| + |
| / \ |
| 2 3 |
+--------+
| 4 |
+--------+

* -> pop 2 times, new tree, push +-------------+
| 1 |
+-------------+
| * |
| / \ |
| + 4 |
| / \ |
| 2 3 |
+-------------+

+ -> pop 2 times, new tree, push +-------------+
| + |
| / \ |
| 1 * |
| / \ |
| + 4 |
| / \ |
| 2 3 |
+-------------+

Finished, the stack contains the tree.

Actually, I dreamed about this on the friday night, and thought: "S*it!
He got me again!" (but I guess 'I got my self' because I didn't really
think before writing;-)).

I am sure you can figure out how the same thing works with
a preorder tree.

Thank you for not underestimating me too much!

Hint: Where else is this usefull besides evaluation of expressions.
Well. Think of storing a tree in a file and reconstructing
it from the file. Or: sending a tree through a network. Or ....
In other words: Whenever you need to serialize a tree.

That's a good hint!

Thank you,
Andre Caldas.