**Four modules**

I had to write 4 main modules for my code:

- Parser. It takes the input you type and transforms it into a tree
- Orderer. Re-arranges the tree to follow the order of operations
- Evaluator. Takes a tree as input and evaluates/solves it as much as it can.
- Simplifier. Evaluates the expression even further (more on this later)

Let’s see how they work without getting into the actual code part of it. The following bits are very simplified, but if you want the details, make sure to check out the code section.

**Parser**

It takes and expression like `a + b * c`

and has to convert it into:

graph TD; subgraph abc["Tree for a + b * c"]; add(+) --> a(a); add(+) --> mul("×"); mul --> b(b); mul --> c(c); end

We won’t look at the code in this section, but when programming, the tree is needed so that it can understand the input you typed in in.

Here’s the process when going character-by-character:

graph TD; subgraph s1["Step 1"]; a1(a); end; subgraph s2[Step 2]; add1(+) --> a2(a); end subgraph s2[Step 3]; add2(+) --> a3(a); add2 --> b3(b); end subgraph s3[Step 3]; mul("×") --> add3(+); add3 --> a4(a); add3 --> b4(b); end subgraph s4[Step 4] mul2(*) --> add4(+); mul2 --> c(c); add4 --> a5(a); add4 --> b5(b); end; s1 -.-> s2 -.-> s3 -.-> s4;

Nice! It’s pretty straightforward, it takes the first character, adds it to the tree, then the second, third, etc.

Although, you might notice that it doesn’t follow the operation precedence. Let’s take care of that now!

**Orderer**

Let’s use the same example:

graph TD; subgraph ab_c["Tree for a + b * c"] mul("×") --> add(+); mul --> c(c); add --> a(a); add --> b(b); end

If we add parentheses and translate it back to textual form, it would be `(a + b) * c`

. But, what we want is

graph TD; subgraph a_bc["a + b * c following operator precedence"] add(+) --> a(a) add --> mul("×") mul --> b(b) mul --> c(c) end

Which translates to `a + (b * c)`

. We need to write a function to do that ordering for us.

With the same example as before, let’s look at what exactly we need to do.

There are 3 scenarios in which we need to re-arrange the tree: `a + b * c`

, `a * b + c`

(normally this one works fine, but we still need to re-arrange it if it ends up like `a * (b + c)`

), and `a + b * c + d`

. Let’s go one by one, starting with `a + b * c`

:

**Precedence 1**

For `a + b * c`

:

graph TD; subgraph s1["Step 1"] mul("×") --> add(+); mul --> c(c); add --> a(a); add --> b(b); end subgraph s2["Step 2"] add2(+) --> a2(a); add2 --> b2(b); mul2("×") --> c2(c); end subgraph s3["Step 3"] add3(+) --> a3(a); mul3("×") --> b3(b); mul3 --> c3(c); end subgraph s4["Step 4"] add4(+) --> a4(a); add4 --> mul4("×"); mul4 --> b4(b); mul4 --> c4(c); end s1 -.-> s2 -.-> s3 -.-> s4

Since multiplication has higher precedence than addition, `b`

gets multiplied first.

**Precedence 2**

For `a * b + c`

graph TD; subgraph s1["Step 1"] mul("×") --> a(a) add(+) --> b(b) add --> c(c) mul --> add end subgraph s2["Step 2"] mul2("×") --> a2(a) add2(+) --> b2(b) add2 --> c2(c) end subgraph s3["Step 3"] mul3("×") --> a3(a) mul3("×") --> b3(b) add3(+) --> c3(c) end subgraph s4["Step 4"] mul4("×") --> a4(a) mul4("×") --> b4(b) add4(+) --> mul4 add4 --> c4(c) end s1 -.-> s2 -.-> s3 -.-> s4

**Precedence 3**

For `a + b * c + d`

graph TD; subgraph s1["Step 1"] mul("×") --> add1(+) mul("×") --> add2(+) add1 --> a(a) add1 --> b(b) add2 --> c(c) add2 --> d(d) end subgraph s2["Step 2"] mul2("×") --> add3(+) add3 --> a2(a) add3 --> b2(b) add4(+) --> c2(c) add4 --> d2(d) end subgraph s3["Step 3"] add5(+) --> a3(a) add5 --> b3(b) mul3("×") add6(+) --> c3(c) add6 --> d3(d) end subgraph s4["Step 4"] add7(+) --> a4(a) mul4("×") --> b4(b) add8(+) --> c4(c) add8 --> d4(d) end subgraph s5["Step 5"] add9(+) --> a5(a) mul5("×") --> b5(b) mul5 --> c5(c) add10(+) --> d5(d) end subgraph s6["Step 6"] add11(+) --> a6(a) add11(+) --> mul6 mul6("×") --> b6(b) mul6 --> c6(c) add12(+) --> d6(d) end subgraph s7["Step 7"] add14(+) --> add13 add14 --> d7(d) add13(+) --> a7(a) add13(+) --> mul7 mul7("×") --> b7(b) mul7 --> c7(c) end s1 -.-> s2 -.-> s3 -.-> s4 -.-> s5 -.-> s6 -.-> s7

That’s it! That’s basically what the orderer does!

**Evaluator**

The evaluator that *we* use when we’re calculating expressions, even if we use it subconsciously. It just calculates as much of the the expression (or tree, in this case) as it can.

Let’s look at the process of the evaluator with a simple example, `5 * 2 + a`

. Here’s how the tree looks after parsing it:

graph TD; subgraph 52a["(5 * 2) + a"] add(+) --> mul("×"); add --> a(a); mul --> 5(5); mul --> 2(2); end

We’ll go step by step and see how the evaluator works:

**Step 1**

First, it starts with the root, `add`

. It knows that there’s `a`

on the right, but what about the left? The left is an expression: `mul`

. It can’t evaluate an expression and a number, so it’ll evaluate left first, and then use the result to evaluate the whole thing:

**Step 2**

It’s focusing on *only* the left. So, what it sees is this:

graph TD; subgraph 52["5 * 2"] mul("×") --> 5(5) mul --> 2(2) end

Okay, this is the information it currently has:

- The left is
`5`

- The right is
`2`

- The operation is multiplication

That’s sufficient information for it to realize that `5`

and `2`

need to be multiplied! So, it multiplies `5 * 2`

and gets `10`

! Now, remember how in step 1 it couldn’t evaluate and expression and a number? If we give it `10`

, it has a number and a number!

**Step 3**

It now has some new information: The `mul`

on the evaluates to `10`

.

And combined with the old information, this is everything it knows:

- The left is
`10`

- The right is
`a`

- The operation is addition

It has all the information it needs to get the final result: `10 + a`

. It can’t be evaluated any further, so it’s done!

graph TD; subgraph 10a["10 + a"]; add(+) --> 10(10); add(+) --> a(a); end

**Simplifier**

And last but not least, the simplifier! The evaluator seems like it evaluates everything, *but* there are some instances when it doesn’t. That’s what the simplifier is for!

Let me give you an example:

graph TD; subgraph 10_a5["10 + (a + 5)"]; add(+) --> 10(10); add --> add2(+); add2 --> a(a); add2 --> 5(5); end

This translates to `10 + a + 5`

. The answer we want is `a + 15`

, but the evaluator can’t do that. Here’s the step-by-step process of the evaluator so that we can see why that happens:

- It looks at the root
- The left is
`10`

- The right is an
`add`

- The left is
- It can’t evaluate it right now, so it checks if it can evaluate the right
- The left is
`a`

- The right is
`5`

- The left is
- It can’t add a variable and a number, so it doesn’t do anything.
- Since the left of the root hasn’t been updated, it also doesn’t do anything

This is the problem here. The evaluator only focuses on *one* branch. When the evaluator is trying to evaluate `a + 5`

, it has completely forgotten about the `10`

. We could change the evaluator so that it does this, but that might get too complicated so let’s just make a simplifier!

What we need to do is bring the branches to the same level. Right now, `add`

always has only two branches. If we make it so that it can have more, we can move other branches down or up into one `add`

, re-arrange the elements and add them all up. Let’s try it out for `10 + a + 5`

:

graph TD; subgraph s1[Step 1] add(+) --> 10(10); add --> add2(+); add2 --> a(a); add2 --> 5(5); end subgraph s2[Step 2] add3(+) --> 10_2(10); add3 --> a2(a); add3 --> 5_2(5); end subgraph s3[Step 3] add4(+) --> a3(a); add4 --> 10_3(10); add4 --> 5_3(5); end subgraph s4[Step 4] add5(+) --> a4(a); add5 --> 15(15); end s1 -.-> s2; s2 -.-> s3; s3 -.-> s4;

And that’s all the simplifier does! The good thing about this is that it can bring any number of branches to the same level, not just three.

Go To: