Inserting infix into a binary tree

This is a discussion on Inserting infix into a binary tree within the C++ Programming forums, part of the General Programming Boards category; For example: (3 + 4) - (1 * 2) + 1 is Code: + / \ - 1 / \ ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    155

    Inserting infix into a binary tree

    For example:

    (3 + 4) - (1 * 2) + 1

    is

    Code:
                               +   
                          /          \
                         -            1
                   /          \    
                  +            *           
               /     \      /    \
              3      4    1       2
    precondition:
    The infix expression is being entered one character at a time.

    The expression is FULLY parenthesized, like (6-4) or (3+(4-2)) or ((2-1)*6) or (((2+1)-4)^2)

    postconditions:

    Each node will consist of an operator (root) with two children or a digit with no children (BTW no digits ever have children obviously. Children of operators are either digits or a new subtree).

    You can use pre-order and post-order traversal to output the tree in prefix and postfix, and use inorder traversal to evaluate the infix expression


    ____________

    My question is, how do I store the infix expression into a binary tree? I know how to do everything else

  2. #2
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    I tried it again and I still can't figure it out. How the heck am I supposed to do this?

  3. #3
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Hmmm, does this also work for nested parenthetical statements? You'd have to detect the first ), yes, but then the items before it and after the last (?
    Last edited by Nakeerb; 01-19-2003 at 02:13 AM.

  4. #4
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    The problem states there will always be parenthesis. Any operand-operator-operand statement has ( and ) around it


    Also the problem speaks of writing constructors for two types of nodes, one that will accept an operator and two digits, or a digit node containing a digit and has both left and right pointers NULL. You assume the input will always be correct.

    I just don't understand how that would work... a constructor for nodes? Na, how would this help

  5. #5
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    And what about nested parenthesis?

  6. #6
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Dangit, Salem what do you mean ;-;

  7. #7
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    No one can help? ;-; I am so dead

  8. #8
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Helllp!

  9. #9
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    If you keep bumping your thread someone's gonna delete it. Salem told you exactly how to solve your problem, read his post until it sinks in.
    *Cela*

  10. #10
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    You can search for recursive descent. You can pretty much ignore
    any of the technical sites. Left factoring and all of the
    complicated stuft isn't needed. Try to understand a recursive
    description of the language | stands for or and -> stands
    for "is defined as".

    expr-> term | term + expr | term - expr
    term-> factor * term | factor / term | factor
    factor-> (expr) | num
    num-> [0..N]

    The actual code will use a function called match(t) that
    will check the next token against t. If t equals the
    next token then it will read the next token and return true
    else it will just return false.

    Here is example of how expr could be coded
    Code:
    int expr()
    {
         int val = 0;
    
         val = term();
        
         switch(next_token.type) {
         case PLUS:
               match(PLUS);
               val += expr();
               break;
         case MINUS:
               match(MINUS);
               val -= expr();
               break;
         default:
               break;
         }
     
         return val;
    }
    A function such as factor could be coded
    Code:
    int factor()
    {
         int val = 0;
    
         switch(next_token.type) {
         case NUMBER:
                val = next_token.val;
                break;
         case LEFT_PARAN:
                match(LEFT_PARAN);
                val = expr();
                match(RIGHT_PARAN);
                break;
         default:
                break;
         }
    
         return val;
    }
    This preserves the structure of the expression but
    it evaluates it. Instead of doing that you could pass
    in the root of each subtree and have each function
    add a node to the tree.

  11. #11
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Ahh I see how it works. I need to modify it though, this does not work for expressions like "(((3+4)-3)-2)" because it only checks for numbers before and after, not when you have two parentheses next to each other

  12. #12
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    This also does not build the binary tree in terms of a node holding an operator as data, with two children being separate nodes with integers as the data

  13. #13
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    This is difficult ;-; must be careful

  14. #14
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    If you write a recursive descent parser that evaluates
    an expression then you can easily change it to generate
    an infix tree.

    It would handle all parens and expressions in the language
    automatically. For example

    (((3+4)-3)-2)
    This would
    be parsed like this
    expr
    term
    factor
    (expr)
    (term - expr)
    (factor - term)
    ((expr) - factor)
    ((term - expr) - num)
    ((factor - term) - num)
    (((expr) - factor) - num)
    (((term + expr) - num) - num)
    (((factor + term) - num) - num)
    (((num + factor) - num) - num)
    (((num + num) - num) - num)

  15. #15
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    I do not understand what that all meant, URG I am dead

Page 1 of 2 12 LastLast
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