Binary Expression Tree with an infix expression

Binary Expression Tree with an infix expression

Post by Ryan » Sat, 23 Nov 2002 11:35:29



I have to write a program to put an infix expression into a binary
expression tree. I cannot convert it to prefix or postfix first. Ive
converted infix to postfix before.

Im having trouble when it comes to an expression like the following:

(A+B*(C-D))/E

where C-D will be at the bottom of the tree.

Im not looking for code. Im looking for help in designing an algorithm.
Should I use a stack to store nodes to climb back up the tree?

Im having trouble getting started with my algorithm.

 
 
 

Binary Expression Tree with an infix expression

Post by Victor Bazaro » Sat, 23 Nov 2002 14:01:22



> I have to write a program to put an infix expression into a binary
> expression tree. I cannot convert it to prefix or postfix first. Ive
> converted infix to postfix before.

> Im having trouble when it comes to an expression like the following:

> (A+B*(C-D))/E

> where C-D will be at the bottom of the tree.

> Im not looking for code. Im looking for help in designing an algorithm.
> Should I use a stack to store nodes to climb back up the tree?

Stack sounds good.

Quote:> Im having trouble getting started with my algorithm.

Well, this newsgroup is not about algorithms.  It's about the C++
_language_.  You by your own admission don't have a language issue.
You should probably consider visiting comp.programming.

Incidentally, "The C++ Programming Language" by Stroustrup has
expression parsing in its 6th chapter, "Expressions" (IIRC).  Take
a look...

Victor
--
Please remove capital A's from my address when replying by mail

 
 
 

Binary Expression Tree with an infix expression

Post by John Harriso » Sat, 23 Nov 2002 17:22:30



Quote:> I have to write a program to put an infix expression into a binary
> expression tree. I cannot convert it to prefix or postfix first. Ive
> converted infix to postfix before.

> Im having trouble when it comes to an expression like the following:

> (A+B*(C-D))/E

> where C-D will be at the bottom of the tree.

> Im not looking for code. Im looking for help in designing an algorithm.
> Should I use a stack to store nodes to climb back up the tree?

> Im having trouble getting started with my algorithm.

You can use recursive descent, look it up in a book on grammars. There's no
need for a stack of nodes, the normal stack that the compiler uses will be
fine.

john

 
 
 

Binary Expression Tree with an infix expression

Post by Ryan » Sat, 23 Nov 2002 20:24:39





> > I have to write a program to put an infix expression into a binary
> > expression tree. I cannot convert it to prefix or postfix first. Ive
> > converted infix to postfix before.

> > Im having trouble when it comes to an expression like the following:

> > (A+B*(C-D))/E

> > where C-D will be at the bottom of the tree.

> > Im not looking for code. Im looking for help in designing an algorithm.
> > Should I use a stack to store nodes to climb back up the tree?

> > Im having trouble getting started with my algorithm.

> You can use recursive descent, look it up in a book on grammars. There's
no
> need for a stack of nodes, the normal stack that the compiler uses will be
> fine.

> john

sorry about the off topic post. I thought about using recursion, but Im get
lost on how to do it.

could youi get me started? I dont want it done for me, but Im just having
trouble seeing it.

 
 
 

Binary Expression Tree with an infix expression

Post by Karl Heinz Buchegge » Sat, 23 Nov 2002 21:30:10



> sorry about the off topic post. I thought about using recursion, but Im get
> lost on how to do it.

> could youi get me started? I dont want it done for me, but Im just having
> trouble seeing it.

Check you mailbox. I have sent personal mail with an explanation.

--
Karl Heinz Buchegger

 
 
 

1. Does an expression-list contain expressions?

Hello.

1.6 para 2 states that X-list is "one or more X's [ugh, an apostrophe for a
plural] separated by intervening commas (e.g. expression-list is a sequence of
expressions separated by commas).

However, expression-list is defined in 5.2 para 1 as:
expression-list:
 assignment-expression
 expression-list, assignment-expression

which -isn't- one or more expressions separated by commas.

Does 1.6 supercede 5.2?  That is, is there an implicit "expression-list,
expresssion" in the description of expression-list?

I can't see any definition of an expression, either, other than the note at
the beginning of chapter 5; is that it?  How do they fit into the grammar?

--
Now Playing:  J. Geils Band - Centerfold


      [ about comp.lang.c++.moderated. First time posters: do this! ]

2. Lock Scroll Position on return

3. Defect Report: throw-expression in a constant expression

4. FS Piles of Amiga SW and a little HW

5. With Void Expressions, All are expressions, Another Fantasy!

6. Five Choices!

7. Is an empty expression a constant expression?

8. Windows users get ANOTHER virus...

9. Expression Tree

10. Help - Overloading functions for expression tree

11. Object-oriented expression tree implementation

12. Parsing expression trees

13. infix to postfix or a way to evaluate infix