C++ Binary Search Tree: Infix Exp. & Tree Traversal

[veron]

c++ data structures! please help!

i want to write a c++ program that implements a binary search tree from an infix expression. the program should perform the following:
-the expression should be saved and read from a file.
-use a stack to check if the expression is well formed in terms of brackets, '([{', and their counterparts.
-construct an expression tree from the expression.
-if there is a problem in the expression tree then the program should tell exactly where the imbalance is.
-validate your input to accept only numbers and operators.
-evaluate the expression tree.(Not the infix expression)
-traverse the expression tree with the three traversal strategies to produce the appropriate expressions.
-print the tree.
-use a linked approach for your solution

 

[fleem]

This is a decent-sized project. I wrote this exact thing many years ago (and still have the code, but I'm keeping it to myself), so I can probably help as my time permits (I get sudden bursts of work). But there is obviously a lot to this so I don't want to compose a big post only to find you already knew most of what I wrote. I'll be glad to ramble, though, if you assure me you have no idea where to start--or did you have any specific questions?

 

[veron]

thanx for the reply and your time! i do very much appreciate your help. the problem is that i have to submit the assignment before the 5th of november and i don't have a clue where to start. can you kindly help me with the code

 

[veron]

thanx for the reply and your time! i do very much appreciate your help. the problem is that i have to submit the assignment before the 5th of november and i don't have a clue where to start. can you kindly help me with the code

 

[D H]

We are here to help you. Giving out the answers does not help you learn anything. You must have been taught something regarding this problem. I will help a bit by asking some leading questions:

• What rules of arithmetic does your parser have to be able to handle? In other words, does it have to handle associativity (1+2+3=6) and precedence (1+2*3=7)?
• What operators does your parser have to be able to handle?
• Does your parser have to be able to handle negative numbers?
• Do you have to be able to detect ill-formed expressions such as "* 2", or just problems with imbalanced parentheses?
• Have you been taught what BNF means? If so, have you written a BNF for your parser? (This is a very good place to start).

 

[fleem]

This is a several-step process. I've included the basics here:

(Note that if you are familiar with regular expressions and have some regex code, that can help simplify some code. If you aren't familiar with regex, don't bother learning it now--it isn't all that necessary)

First, preprocess the infix for unary operators. A unary operator is a minus or plus that is NOT preceded by a close parentheses or a value. When you find a term preceded by a unary operator, insert a '0' in front of it and then enclose the term with parentheses. For example, change...

(3 + -4 + 5)
to
(3 + (0-4) + 5)

For another example, convert

(5 + -(3+2))
to
(5 + (0-(3+2)))

As you can see, when you do find a unary operator, you must go forward to find the end of the term--even if the term is a parenthetical expression. Generally you do this by moving forward through the characters and incrementing a variable each time you pass a '(' and decrementing it when you pass a ')'.

Of course, unary +'s can simply be removed or replaced with a space.

Next, compile the infix expression to a postfix (reverse Polish) program. For example, the postfix program for the infix expression...

(3 * (4 - sin(5)))

...is this:

Push a 4
Push a 5
Sin (this pulls one number off the stack and pushes its sine)
Subtract (this pulls two numbers off the stack and pushes their difference)
Push a 3
Multiply (this pulls two numbers off the stack and pushes their product)

Your compiler would be a recursive function call that takes a pointer (or index) to the beginning of a (sub)expression, appends the reverse Polish instructions to the current program, and then returns.

Let's say the function is called "CompileExpression". So CompileExpression does the following:

1. Find the end of the expression (by counting open & close parentheses)

2. If the incoming expression is just a value, append a 'push value' instruction to the current program and return.

3. If the incoming expression is a function call (like 'tan(3+4)'), call CompileExpression for the parameter, append to the program the instruction for the function, and then return.

4. Find the character positions of the main binary operator and its two terms. For example, in the expression (3 * (4 - sin(5))), the first term is '3', the main operator is '*', and the second term is '(4-sin(5))'

5. Call CompileExpression recursively to compile each term.

6. Append the reverse Polish instruction for the main operator onto the current program.

7. Return

To write your reverse Polish interpreter, you need simply create a stack, and execute the instructions sequentially (they'll push & pop things on that stack). Make sure your stack pointer==1 after the program runs. After the program executes, the single value on the stack is your answer.

 

[fleem]

I forgot to make clear in the previous post: You do not execute the reverse Polish instructions as you discover them. you put the instructions in an instruction buffer so that you can execute them later (with the interpreter). One advantage of this is that when you eventually support variables, you can execute the same program using different variables.

By the way, if you want to add variable support in the future, convert all values into variables (even the constants in the expression) and push their addresses onto the stack instead of the actual values. That way the interpreter need simply consider everything a variable--it always knows stack contents are addresses.