Go Parser for Linear Equation Solver
Tags: go, parser
Published: 2020-07-19 10:10:30

---
title: Go Parser for Linear Equation Solver
published: true
description: How to implement a linear equation solver with Go
tags: go, parser
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/fkxc38syk4z9vbfyqh6n.jpg
---
Linear equation belongs to a class of equations that have the basic form shown below.

{% katex %}
\tag{1} Ax + By = C
{% endkatex %}

where the *coefficients* {% katex inline%}A{% endkatex %}, {% katex inline%}B{% endkatex %} and {% katex inline%}C{% endkatex %} are real numbers.

It can be geometrically represented as a line on a two dimensional plane. One interesting situation arises when we put two lines on the plane and they cross each other at a point. The natural question (for the curious ones) to ask is - *where is that point on the plane?*

To find the answer, we can arrange each equation and solve for {% katex inline%}y{% endkatex %}. Here's one super simple example.

{% katex %}
y = 2x + 3 \newline
y = 3x + 2
{% endkatex %}

We can eliminate one variable - the {% katex inline%}y{% endkatex %} variable - by equating them and solve for {% katex inline%}x{% endkatex %} to find the point.

{% katex %}
2x + 3 = 3x + 2
{% endkatex %}

The value of {% katex inline%}x{% endkatex %} is obvious and we will not proceed any further because the purpose of this post is not to discuss about math but as the title suggests, is to solve equation such as the following with a little solver written in Go.

{% katex %}
\tag{2} 12x - 2 + 33x + 6 - 50x = 17x - 16 - 12x
{% endkatex %}

In fact this is one of the problems on [Leetcode](https://leetcode.com/problems/solve-the-equation/) where one is asked to write a function to compute and return the value of {% katex inline%}x{% endkatex %} as a string. Base on the value of {% katex inline%}x{% endkatex %}, the function returns one of the following strings.

- "x=n", when {% katex inline%}x{% endkatex %} can be evaluated into an integer, we return the value in this format where n can be any integer
- "No solution", when {% katex inline%}x{% endkatex %} cannot be evaluated into an integer or the equations do not cross each other
- "Infinite solutions", when {% katex inline%}x{% endkatex %} can take on any integer value

Notice that the problem statement says that {% katex inline%}x{% endkatex %} has to be an integer instead of real number.

The input to the function is an equation in the form of a string such as equation (2) in the example above and my approach is to parse the equation from left to right to reduce the equation into a term with {% katex inline%}x{% endkatex %} and an integer constant such as (3) below.

{% katex %}
\tag{3} 0 = 10x - 20
{% endkatex %}

How do we implement such a parser? One simple way to do it is to make the parser stateful and let the parser enters into different states base on each input symbol read from the string. The parser must begin in an initial state, we can call it the "START" state and if the first symbol read is a digit such as "1" then the parser enters into the "DIGIT" state. The parser can remain in the same state if it continues to read in digit symbols until the symbol "x" is read and the parser enters into the *accepted* state, we can called it "X-TERM".

![State machine](https://dev-to-uploads.s3.amazonaws.com/i/5q4v6ovey6dny1ukuhde.png)

At this point, we know that we have a term with {% katex inline%}x{% endkatex %} variable such as {% katex inline%}12x{% endkatex %} and we can use an accumulator variable in Go to hold the sum of the coefficients of all terms with {% katex inline%}x{% endkatex %}. We can also do the same for all constant integer terms. After handling the "X-TERM" state, we reset the parser back to "START" state.

The Go code snippet below read a symbol at index `i` from `eq` which is the equation string and set the `state` of the parser to `StateDigit` if the symbol in `eq[i]` is a digit symbol. If the next symbol `eq[i+1]` is still a digit then the parser remains in the `StateDigit` state.

```go
if eq[i] >= '0' && eq[i] <= '9' {
        state = StateDigit
}
```

Knowing that we have scanned a sequence of digits is all good, but how do we extract these digits and turn them into numeric value for arithmetic operations? To do that we need come out of `StateDigit` and that can only happen when the next symbol is an `'x'` or other arithmetic symbol such as `'+'`. As an example, if the current state is `StateDigit` and the next symbol is `'x'` then we convert those digits that we have scanned so far and assign the numeric result to a variable. The Go code uses the `Atoi` function from the `strconv` package and store the result in `xval`. This value is then added to the accumulator `xsum`. The code does not set the parser state to "X-TERM" explicitly because it's obvious that all we need to do here is to obtain the numeric value and we can immediately go back to `StateStart`, that makes the need to set to an intermediate state unnecessary.

```go
switch eq[i] {
case 'x':
        if state == StateDigit {
                // not handling error, Leetcode is
                // unlikely to fail the conversion
                xval, _ := strconv.Atoi(eq[s:i])
                if op == MinusOp {
                        xval = -xval
                }
                xsum += xval
        } else if state == StateStart {
                xval := 1
                if op == MinusOp {
                        xval = -xval
                }
                xsum += xval
        }
        i++
        s = i
        state = StateStart
case '+', '-', '=', '\n':
        // handle arithmetic symbols
default:
        // handle other cases
}
```

In both blocks of the `if` statement above, the parser also keeps track of the current sign of the term with `MinusOp` for `'-'` sign in front of a term and for `'+'` sign it is `PlusOp`. This takes care of the sign of the coefficients and contants before they are added to their corresponding accumulators. The sign `op` of a term is set when the parser is handling the arithmetic symbols as shown in the Go code below.

```go
switch eq[i] {
case 'x':
        // handle 'x'
case '+', '-', '=', '\n':
        if state == StateDigit {
                kval, _ := strconv.Atoi(eq[s:i])
                if op == MinusOp {
                        kval = -kval
                }
                ksum += kval
        }
        switch eq[i] {
        case '+':
                op = PlusOp
        case '-':
                op = MinusOp
        case '=', '\n':
                xsum = -xsum
                ksum = -ksum
                op = PlusOp
        }
        i++
        s = i
        state = StateStart
default:
        if eq[i] >= '0' && eq[i] <= '9' {
                state = StateDigit
        }
        i++
}
```
By the time the parser starts handling the `'='` symbol, we have already reduced the left hand side of the equation to just a term with {% katex inline%}x{% endkatex %} variable and an integer constant. For example equation (2) will become (4) as shown below.

{% katex %}
\tag{4} -5x + 4 = 17x - 16 - 12x
{% endkatex %}

Now all we need to do is to repeat the reduction of the equation by flipping the signs of the left hand side and move everything to the right hand side.

{% katex %}
\tag{5} 0 = 17x - 16 - 12x + 5x - 4
{% endkatex %}

After the handling of the symbol `'='`, the parser repeats the whole process again until it reaches the `'\n'` symbol at the end of the equation string. At this point, the parser does the final flipping of the sign of each term and move them back to the left hand side.

{% katex %}
\tag{6} -10x + 20 = 0
{% endkatex %}

Now We have done parsing the whole equation string. The final stage of the parser is to compute the value for {% katex inline%}x{% endkatex %} and return the result as a string base on the value of {% katex inline%}x{% endkatex %}.

```go
k := ksum
x := xsum
if x == 0 {
        if k == x {
                return "Infinite solutions"
        } else {
                return "No solution"
        }
}
remainder := k % x
if remainder != 0 {
        return "No solution"
} else {
        rval := k / x
        return "x=" + strconv.Itoa(-rval)
}
```
A few scenarios can happen depending on the value of the coefficient and integer contant. When the coefficient and the integer constant are both 0 then we have "Infinite solutions".

{% katex %}
\tag{7} 0x = 0
{% endkatex %}

When the cofficient is 0 but the integer constant is not, then we have "No solution".

{% katex %}
\tag{8} 0x = C
{% endkatex %}

It is also a "No solution" if the integer constant is not divisible by the coefficient. Recall that this is mentioned in the problem statement that the value of {% katex inline%}x{% endkatex %} must be an integer.

{% katex %}
\tag{9} 3x = -10
{% endkatex %}

Finally, if we are not in any of the scenarios above, we have a solution. We just need to divide all terms by the coefficient, flip the sign of the integer constant and move it to the right hand side and we are done. Try do this on equation (6) and we have the below answer.

{% katex %}
\tag{10} x = 2
{% endkatex %}

Is this the only approach to parse the equation string? No, there are other ways such as splitting the string with delimiters. But the advantage of the approach described in this post is that the parser only needs to do a single parse one symbol at a time until the end of the string. By the time the parser reaches the end of the string, the answer is ready. 

The complete Go code can be found here at [my Github repo](https://github.com/dt3zr/leetcode/blob/master/solveq/solveq.go). Cheers!