C++ Notes: Expression Trees

There are a many ways to write expressions: normal infix notation using operator precedence and parentheses, prefix (function) notation, postfix (reverse Polish, named after the Polish mathematicial Lukasiewicz) notation, and as trees. Trees are hard to represent in text-based writing systems, however, they are easy to use in a computer. In computing diagrams of trees are most often written with the root at the top.

This example has +, -, and * operators and integer operands.

Normal infix notation: (7-5) * (3+(1-2))

Tree equivalent:
          *
         / \
        /   \
       -     +
      / \   / \
     #   # #   -
     7   5 3  / \
             #   #
             1   2

• The operator, which can be encoded as a char variable. We'll represent integers with the special operator '#' and a field that contains the integer value.
• The integer value. This field is always there, but is only used with the '#' operator.
• A pointer to the the left subtree if it's not the '#' operator (a terminal node).
• A pointer to the right subtree as above.

Processing trees can be done in a nice, compact, natural, recursive manner.

Two examples of how to declare this:

• Expression Tree Struct
• Expression Tree Class - 1