Thread: Binary Expression Tree

  1. #1

    Binary Expression Tree

    write a utility that allows users to enter expression in any of the 3 representation (infix, pre or postfix) and output the same expression in the other 2 formats. The program should accept input in the following format:
    "<" followed by a prefix expression
    "=" " by an infix exp
    ">" " by a postfix exp
    "Q" to quit

    Upon encountering any of the 1st 3 commands, the program should input the exp, build the internal tree, and then output the same exp in the other 2 formats. Upon encountering a line starting with "Q", it should quit. Ex of suitable input:
    < +BC
    = (x+y)*z
    < *-abc
    > abc+/

    In exp, it should be able to handle operators "+", "-", "*" and "/", and operands consisting of any single upper or lower case letter.

    You should use an expression tree as you internal representation, and you should use a recursive algorithm to manipulate it. Once you have built the ecpression tree, you can output th infix, prefix, postfix, by using in-order, pre-order and post-order traversals. Your only problem will be restoring the parentheses for the infix output. To do this, look at the left and right subtrees: if the left subtree has at its root an operator of lower priority than the operator at the current node, then it needs parentheses; if the right subtree has its root an operator of lower or equal priority than the operator at the current node, then it needs parentheses. To insert parentheses, output "(" before descending into the subtree, and output ")" after returning from the subtree.

  2. #2
    Join Date
    Aug 2001
    Groningen (NL)
    And what is your question about this?

  3. #3
    I had written some portion of the program, but the program can only convert prefix input into an expression tree and prints out the infix and postfix format. I can't get the solution to accept postfix expression and then convert it into another 2 format, and also cannot write the program to convert the infix input into the other 2 formats.

    my code compile without error and there is also no runtime error. But, it does not give the desired output.

  4. #4
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    You realize that you still have yet to ask a question, right?

    We aren't mind readers, and we typically don't like doing others homework, though we are usually pretty helpful with specific questions.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  5. #5
    Registered User
    Join Date
    Sep 2001
    Do you go to USQ? It does have relevance this question.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  2. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Tutorial review
    By Prelude in forum A Brief History of
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  5. Request for comments
    By Prelude in forum A Brief History of
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM