## What is Infix, Prefix, and Postfix Notation?

### Operators vs Operands

**Operators** are symbols like +, -, *, /, ^, anything that operates on... **Operands**, which are values like 8, 21; things to be operated on.

### The Three Notations

**Infix:**When we say 9+10, that is

**infix notation**- that is, the operator is

*in*between the operands. It's the one we're all familiar with.

Ex:

- 24 / 7
- 8 - 2 * 3 + 7

**Prefix:**also known as

**Polish notation**- is where the operator sits

*before*the operands.

Ex:

- / 24 7
- + - 8 * 2 3 7

**Postfix:**also known as

**Reverse Polish Notation**or RPN- is where the operator sits

*after*the operands.

Ex:

- 24 7 /
- 8 2 3 * - 7 +

### Why not stick with Infix notation?

Notice how in the second example, 8 - 2 * 3 + 7, we had to evaluate the multiplication before the subtraction and finally the addition? This is inconvenient for computers to evaluate as parentheses need to be applied according to the order of operations. However, prefix and postfix notation don't suffer from this ambiguity and follow an easy and consistent set of instructions to evaluate, making it very suitable for computers!

## What's an Expression Tree?

### Expression Tree

**Expression Trees** are binary trees whose parent nodes are operators and children nodes are operands of which the operators will execute on. Refer to the Expression Tree Visualizer for the Expression Tree representation of the expression (8 - 2 * 3 + 7).

### What's so special about it?

There are three basic ways to traverse binary trees:** Preorder, Inorder, and Postorder.** Sound familiar? Yup, for expression trees, preorder traversal outputs prefix notation, inorder outputs infix, postorder outputs postfix!

### How do these three traversals work?

**Preorder:**

- Put current node in result
- Go to left child, repeat
- Go to right child, repeat

**Inorder:**

- Go to left child, repeat
- Put current node in result
- Go to right child, repeat

**Postorder:**

- Go to left child, repeat
- Go to right child, repeat
- Put current node in result

*it's interactive! (scroll to zoom / drag to pan)!*

## How do you evaluate Prefix/Postfix notation?

### What is a Stack?

**Stacks**are an abstract data type with two primary operations:

**Push**: Add an element to the top of the stack**Pop**Remove an element from the top of the stack

A stack behaves just like a stack of plates: you *push* plates to the top and also *pop* plates from the top.

A stack follows **LIFO**, or Last in First Out.

### How to evaluate Postfix and Prefix expressions with a stack?

**Note: **Prefix is basically evaluated the same way as Postfix but backwards! Just reverse the input expression or read it backwards! Also note that since it is reversed, the left and right operands are flipped too!

Postfix Pseudocode:

```
1
2
3
4
5
6
7
8
9
10
11
```

```
for each token in input {
if token is operand
push to stack
else if token is operator
pop two operands from stack
(first popped is right operand)
(second popped is left operand)
perform operation on the operands
push result of operation to stack
}
stack should only have one item: answer
```

Prefix Pseudocode:

```
1
2
3
4
5
6
7
8
9
10
11
```

```
for each token in reversed input {
if token is operand
push to stack
else if token is operator
pop two operands from stack
(first popped is left operand)
(second popped is right operand)
perform operation on the operands
push result of operation to stack
}
stack should only have one item: answer
```

## For more information

While reviewing information about this topic, I primarily used UCSB Lecturer Mike Costanza's slides for CS12 linked below. Sadly he retired in 2018 so I won't be able to meet him in college :(