Building Binary Expression Trees

What kind of structure can be used to store a binary expression tree?

The first problem that arises in this context is the fact that although we only have one tree, the kind of data is not the same in each node of that tree. This is because the leaves contain operands, while the internal nodes contain operators. This is a classic situation in which we need (for our tree nodes, in this case) a structure that can hold two different types of data but will never contain more than one of those types at any given time.

How do we get a binary expression into a binary expression tree of such nodes?

The first question here is, "From where?". We could, in theory, read our expressions from the command line and construct the tree from the input, but a problem arises here in that some operators might be considered meta characters by our programming language. We could overcome this problem by substituting other non-meta characters for any such troublesome characters (substitute x for *, for example). However, we can also prompt the user for expression input from the keyboard, and in this case it is probably best to enter a complete line of input (a complete expression) as a single string and then process the expression in that string as the expression tree is built.

However, we get our input, for simplicity we make the following assumptions about our expressions:

• First, it will not matter whether any, or how much, whitespace separates the operands, operators and/or parentheses of the expression on the command line.
• Second, the expression will either be a single positive integer value, or will be fully parenthesized. More explicitly, and more helpfully, this means we shall only require our calculator to be able to deal with expressions that may be defined recursively as follows: A valid expression is either
  • A positive integer value
  • An expression of the form (valid_expression1 op valid_expression2), where op is one of +, -, *, / or % (in the case of a five-function arithmetic calculator).

Here is some pseudocode for a recursive input-and-build routine that is given a node and attempts to find something to place into it, and in so doing reads the entire expression and builds the corresponding tree:

Algorithm expressionFound
-------------------------
Input: an empty tree node
Output: if the read is successful, tree node contains either a positive integer,
         or valid sub-tree information (operator plus two pointers)
Return value: true if successful, false otherwise
---------------------------------------------------------------
if a positive integer is the next thing to be read
    Put that integer into the node and return true
else //we must treat the node as a "sub node" so ...
    Try to read a left parenthesis
    If successful
        Create a new left-child node and make a recursive call on that node
    if successful try to read an operator and put that into the node
    if successful
        Create a new right-child node and make a recursive call on that node
    if successful
        Try to read a right parenthesis
    if still successful return true, otherwise return false