# Notation Visualizer

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

All these traversals use recursion, which is straightforward for a computer but often difficult for humans to grasp. Hence, I've provided buttons to help you visualize each traversal in action!
Preorder:
1. Put current node in result
2. Go to left child, repeat
3. Go to right child, repeat
Inorder:
1. Go to left child, repeat
2. Put current node in result
3. Go to right child, repeat
Postorder:
1. Go to left child, repeat
2. Go to right child, repeat
3. Put current node in result
Expression Tree Visualizer
it's interactive! (scroll to zoom / drag to pan)!
Result:
[]
Run Visualizer:

## How do you evaluate Prefix/Postfix notation?

### What is a Stack?

Stacks are an abstract data type with two primary operations:
1. Push: Add an element to the top of the stack
2. 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```
Stack Evaluation Visualizer
Input
Stack