Expression Trees

What Are Expression Trees

Expression trees are trees that represent expressions - pretty general definition.

More specifically and narrowly, we can think of expression trees as BINARY trees (see Binary Trees) representing arithmetical or syntax expressions. A few examples of syntax that can be assembled into expression trees:

• Postfix (reverse polish) notation
• Infix (normal human-readable operator) notation
• Nested parentheses (e.g., LISP)

Challenge Question

Programming question: Write a program that can parse a complex parentheses-based infix expression like,

"(a+b)/(c+(d*e))"

and turn it into its equivalent expression tree.

Converting Expressions to Trees

Strategy to processing expressions is to create your nested definition of an expression (or, a tree node) and simply go with it.

Keep the interface simple, use simple data structures like stacks, only implement the functionality you need.

Turn it into a tree when you're finished.

Postfix Expressions

Postfix expressions are a bit easier to turn into expression trees. Here's the basic idea:

For simple expressions like 3 5 +

while input queue has tokens:
    read a token
    if number, 
        create single-node expression and push onto stack
    if operator, 
        create three-node expression with operator at parent, left = pop from stack, right = pop from stack

Not handling more complicated syntax like 4 5 8 2 + * -

Infix Expressions

Complication here is not with multiple operators and operands, complication here is with parentheses

String/substring based method would iterate through the expression starting with innermost parentheses,

but this quickly gets complicated - multiple front/back pointers, non-sequential gaps, longer strings would be even worse

Strategy here is to process things as you see them, but be able to push things onto stack when only half-finished, for example 4 + (3 + (5 + (7 + 9)))

The algorithm looks like this:

while there are still tokens left in input queue:
    read a token
    if number, 
        create single-node expression
        if prior item in stack is unbalanced operator, and prior char was not (
            add to operator.right and push finished expression onto stack
    if operator
        create three-node expression with operator as parent
        operator.left = pop from stack
        push entire expression onto stack
    if close parentheses,
        if top of stack is unfinished operator, throw exception
        otherwise do nothing
    if open parentheses
        start single-node expression

When open parentheses, take whatever you were currently working on and push it on the stack

Shunting Yard Algorithm

Algorithm by Dijsktra, helps convert infix notation like 3+5 into postfiix notation like 3 5 +

Called the shunting yard because algorithm has structure of three data structures that work in tandem like a railroad shunting yard.

Input queue, processed one token at a time.

Operator stack, holds the operators that will be attached to the end of the expression

Output queue assembles the final expression