Thread: Newbie expression tree question

  1. #1
    Registered User
    Join Date
    Nov 2010

    Newbie expression tree question

    Hi there,

    I have a basic question on the 'point' of expression trees.

    I have created one, using the code example from HERE.

    After creating 3 nodes, lets say two containing integers and one containing ^U to represent a union operator.

    Now, I then use an std::stack and push these nodes onto the stack in postfix order, resulting in:

    1 [1]
    2 [2]
    3 [^U]

    So as I run through the stack, I end up with 1 2 ^U, ie: postfix notation.

    My question is then this, why would I use the expression tree in the first place, am I missing the point with this?

    My understanding is that yes, I have 3 nodes on the heap, and I need to use a stack in order to put them into postfix order, so where does the expression tree come into play?

    I'm clearly not understanding the overall concept of their 'point', so I'm hoping someone could tell me, perhaps I don't need a stack at all? But my thoughts are that I do, in order to create the postfix ordering of the expression.

    Thanks for any help in helping me to understand the concept.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    The edge of the known universe
    1 + 2 * 3
    ( 1 + 2 ) * 3

    The first is
    1 2 3 * +

    The second is
    1 2 + 3 *

    The "tree" is when you parse the in-fix expression to begin with. The left and right operands of any dyadic operator may be an expression. If it is, a tree is a convenient way of parsing it.

    The "stack" is all you need to evaluate the expression when you're done parsing.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Thanks Salem,

    so am I correct in saying that I build the tree first, then parse the tree, and the order in which I parse the tree stipulates whether I am using post/in/prefix, and so I build my stack during the parsing of the tree?

    So the 'point' of the tree is that it allows me to parse the expression in the order of my choosing, allowing to to then go on and build the stack in that order (pre/in/postfix).

    Thanks for your advice, I know it's a basic question, but I just gotta get my head around it first.
    Last edited by Orange Lozenge; 02-18-2011 at 11:47 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 234 Tree question
    By dudeomanodude in forum C++ Programming
    Replies: 0
    Last Post: 04-03-2008, 03:34 PM
  2. reading command line or text file...expression tree (sort of)
    By mathwork orange in forum C++ Programming
    Replies: 2
    Last Post: 02-13-2008, 09:52 AM
  3. C++ Tree Calculator
    By MercFh in forum C++ Programming
    Replies: 33
    Last Post: 12-03-2007, 09:34 PM
  4. Replies: 5
    Last Post: 11-17-2007, 03:47 PM
  5. Binary Search Tree - one last question
    By tms43 in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2006, 03:58 AM