## Four modules

I had to write 4 main modules for my code:

1. Parser. It takes the input you type and transforms it into a tree
2. Orderer. Re-arranges the tree to follow the order of operations
3. Evaluator. Takes a tree as input and evaluates/solves it as much as it can.
4. 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"];

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];

end

subgraph s2[Step 3];

end

subgraph s3[Step 3];

end

subgraph s4[Step 4]

mul2 --> c(c);

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 --> c(c);
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"]
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 --> c(c);

end

subgraph s2["Step 2"]

mul2("×") --> c2(c);

end

subgraph s3["Step 3"]

mul3("×") --> b3(b);
mul3 --> c3(c);

end

subgraph s4["Step 4"]

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)

end

subgraph s2["Step 2"]

mul2("×") --> a2(a)

end

subgraph s3["Step 3"]

mul3("×") --> a3(a)
mul3("×") --> b3(b)

end

subgraph s4["Step 4"]

mul4("×") --> a4(a)
mul4("×") --> b4(b)

end

s1 -.-> s2 -.-> s3 -.-> s4

```

#### Precedence 3

For `a + b * c + d`

```
graph TD;
subgraph s1["Step 1"]

end

subgraph s2["Step 2"]

end

subgraph s3["Step 3"]

mul3("×")

end

subgraph s4["Step 4"]

mul4("×") --> b4(b)

end

subgraph s5["Step 5"]

mul5("×") --> b5(b)
mul5 --> c5(c)

end

subgraph s6["Step 6"]

mul6("×") --> b6(b)
mul6 --> c6(c)

end

subgraph s7["Step 7"]

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"]

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`

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"];

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)"];

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:

1. It looks at the root
• The left is `10`
• The right is an `add`
2. It can’t evaluate it right now, so it checks if it can evaluate the right
• The left is `a`
• The right is `5`
3. It can’t add a variable and a number, so it doesn’t do anything.
4. 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]

end

subgraph s2[Step 2]

end

subgraph s3[Step 3]

end

subgraph s4[Step 4]

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:

Visualization

Code