Parsing and Sorting

The first part of this series explained basic tree terminology and showed how to build a simple binary tree in Visual Basic or C#. It also explained how to perform traversals of trees but the only really practical application it showed was how to make a tree draw itself. That’s pretty handy if you need to display a tree, but trees can do so much more.
Evaluating Expressions
You can represent an arithmetic expression such as -2*(8+7)/-10 with an expression tree or parse tree. Interior nodes in the tree represent operands such as *, ( ), and /. Leaf nodes represent numbers such as 2, 80, and 3.14159265.
The value of a leaf node is simply the value of its number. To get the value of a non-leaf node, you calculate the values of its children and then combine them by using the appropriate operation.

For example, Figure 1 shows the parse tree for the expression -2*(8+7)/-10. The values of the two lowest nodes are 8 and 7. The value of their parent node is 8 + 7. If you work through the entire tree, you’ll find that the value of the root node is 3.

Making a parse tree evaluate itself is easy. The node class’s Evaluate function simply calls its children’s Evaluate function and then combines the results by using the appropriate operand. (More on this later.)

The tricky part is building the parse tree; you need to pick apart the expression and figure out what nodes to build to represent the expression’s pieces.

The example program EvaluateExpressions, which is available for download in Visual Basic and C# versions, uses an ExpressionNode class to represent the pieces of an expression. This class uses four variables to keep track of the sub-expression that it represents. Expression stores a string representing the node’s sub-expression. LeftChild and RightChild are references to ExpressionNode objects, which represent the node’s children in the tree. Op holds the node’s operand.

For example, the root node in Figure 1 has Expression = “-2*(8+7)/-10” and Op = “/”. The following code shows the ExpressionNode class's constructor. The code saves the node’s expression and sets its children to Nothing. It then calls the ParseExpression method to do all of the fun work.

' Constructor.
Public Sub New(ByVal new_expression As String)
  ' Build the expression's parse tree.
  Expression = new_expression
  LeftChild = Nothing
  RightChild = Nothing
  ParseExpression()
End Sub