# Designing A Calculator with FSM Logic

--

As far as I can tell, making a calculator is a classic first time programmer’s challenge. So, as I was helping some of my fellow underclassmen learn web dev, I suggested making a calculator! For best practice purposes, I also suggested starting off with brainstorming:

- first, we design how this calculator is going to work,
- then we can implement code for this,
- and finally, we can make it pretty

As we were brainstorming, we naturally through that a coherent design logic for our calculator would be a *finite state machine (FSM)**!*

# WAIT 👊. What’s a Finite State Machine (FSM)?

*NOTE: **If you’re familiar with FSMs, you can skip this section entirely 💁.*

An FSM is a mathematical objects made of states, state transitions, and inputs. FSMs are widely used in computer science and engineering to model the behaviors of machines. At any given time, an FSM has one state and can receive inputs. Based on those inputs, the FSM can change both state (through state transitions) and interval variables of the FSM.

## HERE’S AN EXAMPLE: The state machine of the human body.

A very simplified human body has 2 states: `hungry`

and `full`

. When humans are `hungry`

, they need `food`

in order to move back to the being in the`full`

state, and at the same time, they may become `happy :D`

when they get food. Becoming happy in this case would be an **internal** **variable** of the state machine, and eating would be an **input**.

Then, humans `use all their energy`

(the other input) which makes them `hungry`

again. They could become **SAD 😔 **too.

So, *inputs essentially lead to state change in a state machine*. Here’s what this simple human body state machine would look like when graphically represented:

## Ok, let me show you another example!

You’re about to see an FSM that you’re very familiar with but that was just never called an FSM: the *state of matter*.

Right, isn’t that cool? We learn this in high school, but they never call it that way. Anyway, this state machine has 4 states: PLASMA, GAS, SOLID, LIQUID. There are transitions from states to states, which are inputs that are either caused by nature or by humans. Internal states of this state machines could be, for example, the boiling temperature of the given matter, the name of the given matter, etc.

## Why Are (Finite) State Machines Important? 🐍

They provide us with a very systematic way of modelling anything that can happen in real life (such as state of matter). Based on state machines, we can easily use mathematics to derive both properties of those machines. State machines are widely used in probabilistic applications, such as modelling the motion of a robot looking for a reward located somewhere the robot does not know using Markov Random Process (which is also a subset of state machines). State machines also allow to naturally and easily expand our model (both through the design and through code). For example, in the human body, we could add another state, `not full / not hungry`

, where the human person could be feeling `meh`

. To add that, we simple create a new state and add some transitions to it.

Of course, there are times when other models are better, but state machines work best for certain kinds of applications.

Finally, if you’re more interested, here’s an article on embeddedrelated.com by Jason Sacks that goes over a lot more details that I did. If you find this interesting, you will love that article.

# Back to Calculators

Later on, we decided to use the iPhone’s calculator to identify all the possible states in our calculator state machine simply by playing around doing multiple arithmetic computations. And…

**It quickly turned out to be much more complicated than I thought.**

Here’s some thought to not using a state machine:

- Designing a calculator without thinking about all the state machine’s logic is very simple. It works well for most operations, and noticing the imperfections in it can be subtle. However, there are operations that simply do not work well, such as
`2 + 4 * 2`

, which in reality is`2 + (4 * 2) = 10`

and can be erroneously evaluated as`(2 + 4) * 2 = 12`

. - Another way to design a calculator is one where the user can input expressions, such as
`3 * 4`

, which can be easily evaluated with functions like

. Not that I am*eval**not*suggesting using`eval`

(*it’s know to be a bad practice**)*; it’s just a quick solution that could help quickly get down to implementing all the UI for the calculator.

However, nicely designing a calculator with a correct finite state machine is not that easy. Nevertheless, I decided to pursue this interesting challenge, and this is what I came up with:

**😧 That looks quite complicated. Let me explain. 😤**

*Note:** if you’d like to skip to the end, I posted JavaScript gist code snippet that implements this.*

The main idea behind a *simple* calculator is that we receive inputs, and based on those inputs, we make some operations, and if needed, we change the output display on the screen.

Inputs may be:

- numbers (one of
`0,1,2,3,4,5,6,7,8,9,.`

. note that I included the`.`

as a “number”), - operations (one of
`+,-,*,/`

), - equality (i.e.
`=`

), or - reset (could be
`C`

or`AC`

on iPhone. One of them is`clear`

which is same as`clear entry`

and the other is`clear all`

).

Then, we can denote the inputs as follow:

- Operations are
`OP`

for`+,-,*,/`

,`OPS`

for`+,-`

, and`OPC`

for`*,/`

.`C`

for complex,`S`

for simple. - Equality is just
`=`

. - Input numbers may be one of
`fk`

,`sk`

, or`tk`

.`k`

actually stands for the new input’s index for numbers such that a number is a sequence of digit characters`f0,f1,f2,...,fk-1`

, and the input makes the number become`f0,f1,...,fk`

. For example, in`123`

,`f0=1, f1=2, f2=3`

and`k-1=2`

. The input`f3=4`

will change that number into`1234`

. - The reset button is
`RES`

. This is like pressing`AC`

or`C`

on your iPhone’s calculator.

Next, I designed the underlying structure of the calculator as blocks of the form:

`|---|-----|---|-----|---|`

| F | OP1 | S | OP2 | T |

|---|-----|---|-----|---|

`F`

stands for “first” as in “first number”`OP1`

is the first operation`S`

is stands for “second” as in “second number”`OP2`

is the second operation, and finally`T`

stands for “trailing” as in “trailing number”.

By now, you can probably imagine that we’d be doing operations against the first and second number and against the second number against the trailing number, **but how are the operations actually made, what do each of those blocks actually mean, and where does the result get stored? Let me explain all of it!**

# The State Logic 😋

What we need is to identify all the possible states for this FSM. This is the difficult part. I learned here that this type of calculators try to make the most logical assumption while respecting the rules of mathematics, and it can be beautifully describes with only 7 states! Before diving into these 7 states, first, here’s what the state parameters in a state represent:

`F <- the value of the first number`

OP1 <- the operation between the first and second number

S <- the value of the second number

OP2 <- the operation between the second number and trailing number

T <- the value of the trailing number

D <- what is displayed on the screen; it can be one of F, S, and T

The inputs that I listed above are what will lead to various state transitions. Now, onto the states:

## State 1: INITIAL State

So, the initial state looks like:

`F: 0`

OP1: +

S: 0

OP2: +

T: 0

D: F

This is the state we start off with. There’s nothing interesting, and the values that we start with are just zeros and `+`

operations.

Pressing `RES`

will take us back to the initial state: it essentially has no effect. **YES**, self loops are allowed in FSMs. 😈

Pressing `=`

take us to the **EQUAL** state, which I will get to.

Pressing any number, denoted by `fk`

(which must be equal to `f0`

for this input coming from the **INITIAL** state) will take us to the **TRANSITION FROM INITIAL **state. I will talk about that state next. The number is denoted with lowercase `f`

because it will be filled into the first number `F`

. Note that adding numbers into other blocks will then have to either be `sk`

or `tk`

for block `S`

and block `T`

respectively.

Finally, pressing any operation `OP`

will take us to the **TRANSITION** state. Note that this will change `OP1`

to become `OP`

, whatever `OP`

may be among `+,-,*,/`

. This state is upcoming as well.

## STATE 2: TRANSITION FROM INITIAL

Let me point out that my naming convention here is a bit weird, but I tried my best to give these states meaningful names. 👽

Without further ado, this state looks like this:

`F: f0...fk-1`

OP1: ~OP1

S: ~S

OP2: ~OP2

T: ~T

D: F

Some things to note: I use the `~`

notation to denote that the value of this key is whatever the given state key was before (not that it could be that the state key does not match state key, e.g.: `S: ~F`

). Some later states will cause these values to change and not be `+`

or `0`

as in the initial state.

So, anyway:

Pressing `RES`

will take us to **TRANSITION FROM INITIAL **state (i.e. back to here) if `F`

is not equal to `0`

. It will clear `F`

(i.e. set it to `0`

). Pressing `RES`

will take us back to **INITIAL** state if `F = 0`

. This means all parameters become what they used to be. i.e. `F=0, OP1=+, S=0, D=F, OP2=+, T=0`

. I will show why this is important at the end.

Pressing any number `fk`

will take us back to this same state, **TRANSITION FROM INITIAL** and simply append `fk`

to `f0...fk-1`

.

Pressing the `=`

sign will take us to the **EQUAL **state. Through this, it will make the evaluation `(F) OP1 (S)`

and place the result in the `F`

block when it reaches the equal state.

Finally, pressing any operation `OP`

will take us to the **TRANSITION **state. Note that this will change `OP1`

to become `OP`

, whatever `OP`

may be among `+,-,*,/`

. This will also duplicate `F`

into `S`

.

## STATE 3: TRANSITION

If you go back to the visual, you will notice that this state is the most frequented state (i.e. has the most arrows coming into it). **EQUAL** is the second most frequented. Anyway, this state looks like:

`F: ~F`

OP1: OP

S: ~F

OP2: ~OP2

T: ~T

D: F

Note that to reach this state, one must press an operation `OP`

; that is the value that `OP1`

takes! There’s also something funny that happens here: the value of `F`

gets duplicated into `S`

. This is an optimization that was made by the iPhone. It’s a design decision that did not have to happen but works very well. Let’s say you press `3`

then `*`

. Then, what happens if you press `=`

? Do you get a zero because you didn’t type the second number? With this design decision, you’d get a `9`

because we assume that you meant `3 * 3`

. I think it’s cool that they thought of this!

Then, pressing any `OP`

leads us back to this state. It simply changes the operation to the new one.

Pressing `=`

evaluates `(F) OP1 (S)`

and places the result in `F`

. Then, it takes us to the **EQUAL **state. Note that when it takes us to the equal state, both `OP`

and `S`

and every other parameters of the state remain unchanged. This is also cool. Do you see why? Maybe it’ll be more obvious once we get into the **EQUAL** state.

Pressing `RES`

takes us back to **TRANSITION FROM INITIAL**. On the way to it, it removes all the values in `F`

and replaces it with `0`

. All the other parameters remain unchanged.

Finally, pressing another number `sk`

takes us to the **TRANSITION FROM TRANSITION **state. As you can imagine, this changes the value of `S`

. Note that as coming from **TRANSITION**, `sk = s0`

(the very first index of the second number regardless of what `S `

currently is, it will overwrite it).

## STATE 4: TRANSITION FROM TRANSITION

(That naming though… Sigh) 😞

This state is interesting. It looks like this:

`F: ~F`

OP1: ~OP1

S: s0...sk-1

OP2: ~OP2

T: ~T

D: S

You can probably note that the display has now changed from `F`

to `S`

. *Now, we’re displaying the second number*!

Pressing `sk`

takes us back to this same state, it just appends `sk`

to `S`

so that it now becomes `s0...sk`

.

Pressing `=`

takes us to the **EQUAL **state. Again, it will evaluate `(F) OP1 (S)`

and place the result in `F`

and also keep all other parameters unchanged.

Pressing `RES`

takes us back to **TRANSITION FROM TRANSITION** if `S`

is not equal to `0`

. This will clear `S`

and replaces it with `0`

.

Pressing `RES`

when `S = 0`

will take us back to **INITIAL**. This means that everything will get back to what it started off with.

Finally, pressing `OP`

is the interesting case. There is actually two possible cases here:

- If we press
`OPS`

, we evaluate the expression`(F) OP1 (S)`

and place its result on`F`

. It will also place that same result on`S`

as well. This is because we’re doing a simple`+`

or`-`

operation, so we can just evaluate the pression.`OP1`

will become`OPS`

, whatever it may be. Then, it will take us back to the**TRANSITION**state. - If we press
`OPC`

and`OP1 = OPC`

, then we do the same as when we press`OPS`

except it’s`OPC`

. of course. - Finally, if we press
`OPC`

, we will be taken to the**TRAILING**state if`OP1 is OPS`

(i.e. if`OP1`

is one of`+`

or`-`

). In this state,`OP2`

is always and becomes`OPC`

(i.e. one of`*`

or`/`

) and`OP1`

is always an`OPS`

.`S`

remains what it was, which is`s0...sk-1`

, but`T`

will now get the value of`S`

. The display`D`

and`S`

remain unchanged.

## STATE 5: TRAILING

** Why do we have a trailing state?** 👀

Imagine the expression `9+5*2`

, should it evaluate to `14*2=28`

or should it evaluate to `9+10=19`

? If you care about Mathematics, you know that multiplication takes precedence. That is why we have both the **TRAILING** state and the **TRANSITION FROM TRAILING** state!

Note that in this state, `OP1`

is always `OPS`

and `OP2`

is always `OPC`

.

The **TRAILING** state looks like:

`F: ~F`

OP1: ~OP1=OPC

S: ~S

OP2: OPC

T: ~S

D: S

Pressing `=`

takes us to the **EQUAL** state. The evaluation is different however. First, we evaluate `(S) OP2 (T)`

, place the result into `S`

(note that we make this evaluation *before* moving to the equal state), then we evaluate `(F) OP1 (S)`

, which places the result into `F`

(note that we make this evaluation after moving *into* the equal state). So, now, `F`

is essentially `(F) OP1 ((S) OP2 (T))`

. All other expressions remain unchanged.

Pressing `RES`

will take us to the **TRANSITION FROM TRAILING **state. This will immediately set `T = 0`

and all parameters will remain unchanged. The display will become `T`

. Someone pressing `tk = t0`

is essentially equivalent to pressing `RES`

from the **TRAILING** state.

Pressing `OPC`

leads us back to the **TRAILING** state and simply change the `OPC`

on `OP2`

.

Pressing `OPS`

will run the same evaluation done with pressing `=`

, i.e. it will place `(F) OP1 ((S) OP2 (T))`

into `F`

but also on place it on `S`

. `OP1`

will be `OPS`

, whatever it may be, and the display will be `F`

. Other keys will remain unchanged.

Finally, pressing `tk`

will take us to the **TRANSITION FROM TRAILING** state. In this case (i.e. coming from **TRAILING**), `tk = t0`

. The display also changes to `D=T`

.

## STATE 6: TRANSITION FROM TRAILING

This state looks like:

`F: ~F`

OP1: ~OPS

S: ~S

OP2: ~OPC

T: t0...tk-1

D: T

Pressing `RES`

if `T = 0`

will take us back to **INITIAL **state. Everything will be cleared. However, if `T`

is not equal to `0`

, pressing `RES`

will just clear `T`

(i.e. set it to `0`

) and remain in this state.

Pressing `tk`

will just append `tk`

into the current value of `T`

.

Pressing `=`

will evaluate the expression just as evaluated when pressing `=`

during the **TRAILING** state, and it will take us to the **EQUAL** state.

Pressing `OPC`

will take us to the **TRAILING** state. This will evaluate `(S) OP2 (T)`

and place the result in both `S`

and `T`

. Then, it will change `OP2`

to be the new input `OPC`

. The display will change back to `S`

.

Pressing `OPS`

will take us to the **TRANSITION** state. This will evaluate the expression similar to how it’s evaluated in the **TRAILING** state.

## STATE 7: EQUAL STATE

Whew! Finally, the **EQUAL **state. This state looks like:

`F: (F) OP1 (S)`

OP1: ~OP1

S: ~S

OP2: ~OP2

T: ~T

D: F

Note that the display in the equal state is always `F`

.

Pressing `=`

re-evaluates `(F) OP1 (S)`

and places the result into `F`

. Note that `S`

will remain the same in this case.

Pressing `OP`

will take us to the **TRANSITION** state. Then, it will make a copy of `F`

and place it into `S`

. Then, `OP1`

will be the newly received operation.

Pressing `fk`

will take us to the **TRANSITION FROM INITIAL **state. In this case, `fk = f0`

. Everything else will remain unchanged.

Pressing `RES`

will also take us back to the **TRANSITION FROM INITIAL **state. However, it will delete `F`

and replace it with `0`

.

# The Calculator (an example!)

# Parting Notes

This is the calculator shown in the photo above. It’s a really nice state machine that works well for these simple operations, and the design is great because it can be easily expanded to more complicated operations such as `sin`

or `floor`

.

I wanted to point out that I didn’t really talk about how we are appending to the numbers. In case `fk`

(or equivalently `sk`

and `tk`

) is `.`

, we only append when there is no `.`

in the number. For example, pressing `.`

when `F=243`

will make `F=243.`

. However, pressing `.`

when `F=23.5`

will have no effects! Also, pressing any number other than `0`

when `F=0`

needs to change `F`

into that number (equivalently for `S`

and `T`

).

This is definitely not crazy difficult, but I’d say it’s more complicated that it looks, and it’s been a rewarding exercise to actually design this calculator. Here’s code that I wrote that does this in JavaScript (which is meant to be used for a calculator website):

*Or, check it out on Github:*

*Thanks for reading!*