# Expression Trees

### From charlesreid1

## Contents

# 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

# Flags

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
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 OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |