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

Postfix expression tree builder code: https://git.charlesreid1.com/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
if operator:
make new node
left = pop
right = pop

new tree( pop stack )
```

The corresponding infix expression builder pseudocode follows.

Infix expression builder code: https://git.charlesreid1.com/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:
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

```