parsing a binary tree

This is a discussion on parsing a binary tree within the C Programming forums, part of the General Programming Boards category; Hi everyone, I'm writing a program to parse an expression into a binary tree. The expression is like this Code: ...

  1. #1
    Unregistered
    Guest

    parsing a binary tree

    Hi everyone, I'm writing a program to parse an expression into a binary tree. The expression is like this
    Code:
    char expr[]={'6','7','+','8','/','3','*','1','-','7'};
    and I just realized that there is no way I can represent a tree on here, but you probably know how it goes: each node has a value and two pointers, one going down to the left and the other down to the right. I'm working on the algorithm and I have 5 sheets covered with trees, but I can't seem to figure out a good one. Right now it goes:

    create nodes for each high_op('/' and '*')
    if there is not any low_op('+' and '-') between two high_ops then
    link from right to left so that the left pointer of the right high_op points to the high_op that is to the left of it
    else each high_op pointer links to the numbers on either side.
    ditto for the low_ops

    My problem is that I cant figure out how to connect the low_ops and the high_ops together. Is it practical to rearrange the string so that the ablove becomes 83*1-7+67? I would appreciate any tips, better procedures, insults, flames, etc. No code, though. You dont have to write it for me. Thank you very much.

    PS I do have code but every time I stop to think I realize that there is a (seemingly) better way to do it and it all becomes useless.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Build the tree so that the operators with higher precedence are further along in the tree so that they are evaluated first:
    Code:
    expression: 2 * 5 + 30 * 2 * 4
    
    tree:
           +
      *        *
    2   5   30   *
               2   4
    Assuming you are using right to left evaluation, the program would traverse the tree until it reached a value instead of an operator and then evaluate that expression. Then do the same thing for the next level up using the result, and so on. So this tree would be evaluated like so:
    ( ( 2 * 5 ) + ( 30 * ( 2 * 4 ) ) )

    -Prelude
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Okay, you have two kinds of expressions here. I will call them expr1, and expr2.

    an expr1 is a left assosiative bunch of expr2s that are added or subtracted. Your entire equation is going to be an expr1...

    An expr2 is a left associative bunch of numbers that are multiplied or divided...

    expr1:
    expr2
    expr1 + expr2
    expr1 - expr2

    expr2:
    number
    expr2 * number
    expr2 / number

    The only good way I really know to process something like this is with a for loop for each one. (Incidentally, I suggest first writing a program that will calculate the expression, and then later modify it to produce a postfix representation.)

    2 * 5 + 30 * 2 * 4

    Code:
    Process entire statement as expr1
     Grab the first expr2 in the expr1
      Grab the first number in the expr2 (it's a 2) // Make a 2 node
      Grab the operator (it's a *) // Make a * node
      Use * operator with next number (5) // Make a 5 node
      2 * 5 = 10  // Put nodes together
      Grab next operator (it's a +)
      Can't process +, this expr2 is over.  Return 10. // Return the tree
     The first expr2 was a 10. // Result is really a tree
     Grab the next operator (it's a +).  // Make a + node
     Grab the next expr2
      Grab the first number in the expr2 (it's a 30) // Make a 30 node
      Grab the operator (it's a *) // Make a * node
      Grab the next number (it's a 2) // Make a 2 node
      30 * 2 = 60 // Put the nodes together
      Grab the next operator (it's a *) // Make a * node
      Grab the next number (it's a 4) // Make a 4 node
      60 * 4 = 240 // Connect the nodes.  The left child will be the 30 * 2 tree
      Grab the next operator.  (It's end of input)
      Can't process, this expr2 is over.  Return 240. // Return the tree
     The second expr is 240. // Result is the tree we just made
     10 + 240 = 250 // Connect the 2 expr2s using the + node as parent
     Grab the next operator (It's end of input)
     Can't process.  This expr1 is over.  Return 250 // Return the tree
    Result is 250 // Result is tree
    And finally the tree we get looks like this
    Code:
             +
      *             *
    2   5      *      4
             30  2
    Callou collei we'll code the way
    Of prime numbers and pings!

  4. #4
    Unregistered
    Guest
    thank you all for your help. I've been working on it when I have free time. I've decided to do a recursive sort of thingy that goes like this:

    Code:
    function parse(str[],int k
    if the array element k is high_op, call parse again, start at k+1 
    if element is low_op, call parse again, start at k+1
    if element is digit, return element
    the problem i am having is trying to deal with the recursion concept. I just can't seem to get a handle on it. Will the above handle the order of operations correctly, since high_op is checked for low_op? About the linking: Does each successive parse result become a parent of the previous result?

    Code:
    int parse(char fstr[],int start)
    {
        int i;
        int val;
        char c;
        for (i=start+1;i<length;i++){
            c=fstr[i];
            if (pri_op(c)) {array[i]->data=parse(fstr,i);}
            else if (sec_op(c)) {array[i]->data=parse(fstr,i);}
            else if (isdigit(c)) {array[i]->data=c-'0';}
            /*not sure about where to go from here*/
    I would appreciate as always any help. Is there an easy way to write out a Backus Naur Form specification type of thingie in C?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10: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, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21