**What is calculator**

So basically, calculator is used to calculate the result after apply different operations on numbers.

**The things that made up the calculation expression**

assume we have an calculation expression: `(1+2)*(10 / 5) - 3`

we can see that there are serveral kinds of things:

- left parenthesis
- right parenthesis
- numbers
- operators, like
`+, *, -, /`

we can call these things the tokens. these tokens made up the calculation expressions.

**The Precedence of operators**

When we calculate, must consider the precedence of operators, the precedence will affect the final result of the expression.

for `(1+2)*(10 / 5) - 3`

the calculation process is:

- scan the expression from left to right. when we meet the right parenthesis then will calculate
`(1+2)`

first, because right parenthesis has the highest precedence in calculation. - calculate the
`(10 / 5) = 2`

- calculate the result of
`3 * 2`

, because`*`

has higher precedence than`-`

- calculate
`6 - 3 = 3`

, get the final result. - when there are 2 operator has the same precedence, we calculate from left to right.

So we have a table of precedence of operators we will support.

operator | precedence |

) | 3 |

* | 2 |

/ | 2 |

+ | 1 |

– | 1 |

( | 0 |

**The stack**

We will use 2 stack to store the operators and operands.

let’s go through the calculation process with the operator and operands stack.

**expression**: `(1+2)*(10 / 5) - 3`

init state of expression

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

( | 1 | + | 2 | ) | * | ( | 10 | / | 5 | ) | – | 3 |

operator stack and operands stack:

```
operator: []
operands: []
```

read at expression index `0`

:

( is an operator with the lowest precedence, So put it to the operator stack.

```
operator: ['(']
operands: []
```

read expression index `1`

:, encounter number 1, so put it to operands stack.

```
operator: ['(']
operands: [1]
```

read expression index `2`

: `+`

has higher precedence than `(`

, so put it to operator stack.

```
operator: ['(', '+']
operands: [1]
```

read expression index `3`

: value 2 is number so, put it to operands stack.

```
operator: ['(', '+']
operands: [1, 2]
```

read expression index 4:

we meet right parenthesis, So we will pop operator util meet the left parenthesis.

`4.1`

pop + from operator stack, and pop 2 numbers from operands stack.

```
operator: ['(']
operands: []
```

`4.2`

calculate the + result and push the result to operands stack.

```
operator: ['(']
operands: [3]
```

`4.3`

pop left parenthesis

```
operator: []
operands: [3]
```

read index `5`

value: `*`

```
operator: ['*']
operands: [3]
```

read index `6`

value: `(`

```
operator: ['*', '(']
operands: [3]
```

read index `7`

value: `10`

```
operator: ['*', '(']
operands: [3, 10]
```

read index `8`

value: `/`

, since / has higher precedence, So push it to operator stack.

```
operator: ['*', '(', '/']
operands: [3, 10]
```

read index `9`

value: `5`

```
operator: ['*', '(', '/']
operands: [3, 10, 5]
```

read index `10`

value: `)`

, pop operator stack util meet left parenthesis.

`10.1`

pop `/`

, and pop number `10, 5`

```
operator: ['*', '(']
operands: [3]
```

`10.2`

push the value of` 10 / 5=2`

to operands stack

```
operator: ['*', '(']
operands: [3, 2]
```

`10.3`

pop the left parenthesis.

```
operator: ['*']
operands: [3, 2]
```

read expression value at index: `11`

, – has lower precedence , pop` *`

from the operator stack, pop `3 and 2`

from operands stack.

```
operator: []
operands: []
```

and push the result of `3 * 2`

back to operands stack.

```
operator: []
operands: [6]
```

push` - `

to operator stack back.

```
operator: ['-']
operands: [6]
```

**read expression value at index**: `12`

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

( | 1 | + | 2 | ) | * | ( | 10 | / | 5 | ) | – | 3 |

```
operator: ['-']
operands: [6, 3]
```

Finally, pop the last ‘-‘ operator from operator stack, and calculate the final result.

```
operator: []
operands: [3]
```

**So finally we get the calculation result: 3**