Thread: Binary Tree HELP

  1. #1
    Registered User
    Join Date
    Jun 2008
    Posts
    4

    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. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Well, work on a tree structure first.

  3. #3
    Registered User
    Join Date
    Jun 2008
    Posts
    4
    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. #4
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    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. #5
    Registered User
    Join Date
    Jun 2008
    Posts
    4
    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. #6
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    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. #7
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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
    Last edited by C_ntua; 06-21-2008 at 07:50 AM.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    * 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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Jun 2008
    Posts
    4
    if you have this expression a+(b*c) how can construct a binary tree for this expression.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by petermichael View Post
    if you have this expression a+(b*c) how can construct a binary tree for this expression.
    The shunting yard algorithm.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM