Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Expression Trees


Algebraic expressions such as


have an inherent tree-like structure. For example, Figure gif is a representation of the expression in Equation gif. This kind of tree is called an expression tree  .

The terminal nodes (leaves) of an expression tree are the variables or constants in the expression (a, b, c, d, and e). The non-terminal nodes of an expression tree are the operators (+, -, tex2html_wrap_inline61394, and tex2html_wrap_inline61564). Notice that the parentheses which appear in Equation gif do not appear in the tree. Nevertheless, the tree representation has captured the intent of the parentheses since the subtraction is lower in the tree than the multiplication.

Figure: Tree representing the expression a/b+(c-d)e

The common algebraic operators are either unary or binary. E.g., addition, subtraction, multiplication and division are all binary operations and negation is a unary operation. Therefore, the non-terminal nodes of the corresponding expression trees have either one or two non-empty subtrees. I.e., expression trees are usually binary trees.

What can we do with an expression tree? Perhaps the simplest thing to do is to print the expression represented by the tree. Notice that an inorder traversal of the tree in Figure gif visits the nodes in the order


Except for the missing parentheses, this is precisely the order in which the symbols appear in Equation gif!

This suggests that an inorder traversal should be used to print the expression. Consider an inorder traversal which, when it encounters a terminal node simply prints it out; and when it encounters a non-terminal node, does the following:

  1. Print a left parenthesis; and then
  2. traverse the left subtree; and then
  3. print the root; and then
  4. traverse the right subtree; and then
  5. print a right parenthesis.
Applying this procedure to the tree given in Figure gif we get


which, despite the redundant parentheses, represents exactly the same expression as Equation gif.