# Expressions

### From charlesreid1

## Expression Trees

Two main kinds of expressions that you see:

- postfix expressions (a.k.a. reverse polish notation)
- infix expressions (a.k.a. what we use all the time)

A postfix expression looks like:

5 4 + 8 3 - * 15 /

which, when analyzed left to right, means take 5 and 4 and add them, to get 9, then take 8 and 3 and subtract them, to get 5, and then take the 9 and the 5 and multiply them, to get 45, and then take the 45 and the 15, and divide them to get 3.

This same expression would be written with infix notation, with parentheses, like so:

((5+4)*(8-3))/15

### Algorithms

To analyze and evaluate thees kinds of expressions, we often want to build an expression tree. Here is some pseudocode for two algorithms for building postfix and infix expression trees, plus a link to Java code that does this:

Expression trees git.charlesreid1.com link: https://charlesreid1.com:3000/cs/java/src/master/trees/expressions

Postfix expression tree builder code: https://charlesreid1.com:3000/cs/java/src/master/trees/expressions/PostfixExpressionTree.java

**Postfix expression tree builder:**

create tree node stack /* the last pop of this stack will be our root node */ while next char in expression: take next char if numeric: make new node add node to stack if operator: make new node left = pop right = pop add node to stack new tree( pop stack )

The corresponding infix expression builder pseudocode follows.

Infix expression builder code: https://charlesreid1.com:3000/cs/java/src/master/trees/expressions/InfixExpressionTree.java

**Infix expression tree builder:**

create new node stack set start new expression to true while next char in expression: take next char if numeric: make new node if start new expression: push node onto stack set start new expression to false else if expression on stack: peek at top of stack if top of stack is operator: if top of stack has 1 child: add right child else: error else: error if operator: new node pop stack set node left to popped item push node onto stack if (: set start new expression to true if ): if stack size > 1: pop top of stack peek top of stack set popped item to peek's right while stack size > 1: pop top peek top of stack set popped item to peek's right

# 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 |