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)
Programming question: Write a program that can parse a complex parentheses-based infix expression like,
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 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 + * -
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
TreesPart of Computer Science Notes
Series on Data Structures
Abstract data type: Trees/ADT
Preorder traversal: Trees/Preorder
Postorder traversal: Trees/Postorder
In-Order traversal: Binary Trees/Inorder
Breadth-First Search: BFS
Breadth-First Traversal: BFT
Depth-First Search: DFS
Depth-First Traversal: DFT
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT
Flags · Template:TreesFlagBase · e