1. Binary Tree HELP

I have this task and i dont know how to do it, any help will be appreciated
I want to do it in C language under linux
Evaluate Boolean expression given by the user by using tree data structure. An example of the Boolean expression is ((X1 * X2 * X3) + (X2 * X4) + (X5))

Where * and + is not static, i mean they can be any operator.

2. Well, work on a tree structure first.

3. the problem i face is that to construct the tree i need an array containing characters and integers, how can i make 1 array that contain both?

4. A number of ways, although you were somewhat ambiguous as to what it means to contain both ints and chars. No matter what you decide, you'll most likely need to make the tree reference void *'s. What you put into the tree will most likely be a struct of some sort that you will need to create.

Some examples: If you need each element to contain both chars and an int, then you make a custom struct with such elements. If you need chars or an int but you won't be sure which you need for each element, you could create a custom struct that contains an int (that tells you if it's an int or a set of chars) and a union of the chars and int. That last option might be a bit confusing if you're new to C, but it's not that complicated if you're very familiar with structs and unions.

You should have some guidelines and specifications to go for if this is homework. Consult the assignment and figure out what you need for this.

5. Okay, i get your suggestion is to make a struct with 2 arrays one for chars and one for ints.
Now after the user input for exaple:
2+3
I want 2 and 3 to be put in the ints array and the '+' in the char array.

After that how can I excute this operation?

6. I think you're confusing yourself here. All you need to do is evaluate a boolean expression. You can have only a few things possible in reading. Parenthesis, numbers, and operations. That is it.

So I would imagine all you want to do is develop a struct that can contain all of those. Then implement your tree to contain objects of your struct (or void *'s).

7. You want boolean expresion, so no 2+3. Only variables and operators. So you don't need an int.

Have done something similar recently. More complex (type checking a lambda expression) but the idea is the same I suppose.

First of all the user gives a string right? You have to decide if the user will always give you the parenthesis or not.
For example can he give: x + a + (a * b)?
Or would he have to give: (x + (a + (a*b)))
The second approach is much easier.

Lets say he has to give you the parenthesis. Then I suppose you want a tree in order to get "pairs". First thing to do is create your tree. A tree will be like a list, but you will have a next_right, next_left pointer at your struct. Each pointer will be pointing a node-struct, that you will create. Each node struct will also have three char variables. One for the possible variables (max 2) for the boolean expression and one for the operator.

In the above example the tree will be created like this:
Node1: bool_var1 = x, bool_var2 = 0, operator = +, next_right = Node2, next_left = NULL, parent_node = NULL
Node2: bool_var1 = a, bool_var2 = 0, operator = +, next_right = Node3, next_left = NULL, parent_node = Node1
Node3 = bool_var1 = a, bool_var2 = b, operator = *, next_right = NULL, next_left = NULL, parent_node = Node3

So you will first evaluate Node3 which will give a*b. Then the reult will be writen on the parent_node. On bool_var2 that is empty. Then Node2 will be evalutated (since it has non-zero variables) and its value will be given on Node1 and Node1 will evaluate the final expression.
Note, that you could have (a+b)*(c+d) so you will have a node with zero bool_var and two next pointers pointing on two nodes.
Also, you will put && for *, || for + etc etc

Ok, maybe I am complicating things, just had the idea ready that is why I posted it

In the end though, the boolean variables have to have values right? So it will be like:
(1 +0 ) * (1 +1)
If that is true, you have to have int instead of char and use strtol or atoi to convert the characters to integers.

EDIT: how you are going to read and convert the string is your biggest problem, so make sure it is correct before doing the rest

8. * and + mean AND and OR in case you hadn't realised.

The first thing you need to do is come up with the regular expression grammar of the boolean expression. Hunt around, as many things should include the grammar you need as a subset of theirs.
Then you need to write an LL(1) parser to validate an expression of that grammar, and build a parse tree from it.

9. if you have this expression a+(b*c) how can construct a binary tree for this expression.

10. Originally Posted by petermichael
if you have this expression a+(b*c) how can construct a binary tree for this expression.
The shunting yard algorithm.