Go Parser for Linear Equation Solver

Linear equation belongs to a class of equations that have the basic form shown below.

$\tag{1} Ax + By = C$

where the coefficients $A$ , $B$ and $C$ 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 $y$ . Here's one super simple example.

$y = 2x + 3 \newline y = 3x + 2$

We can eliminate one variable - the $y$ variable - by equating them and solve for $x$ to find the point.

$2x + 3 = 3x + 2$

The value of $x$ 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.

$\tag{2} 12x - 2 + 33x + 6 - 50x = 17x - 16 - 12x$

In fact this is one of the problems on Leetcode where one is asked to write a function to compute and return the value of $x$ as a string. Base on the value of $x$ , the function returns one of the following strings.

• "x=n", when $x$ can be evaluated into an integer, we return the value in this format where n can be any integer
• "No solution", when $x$ cannot be evaluated into an integer or the equations do not cross each other
• "Infinite solutions", when $x$ can take on any integer value

Notice that the problem statement says that $x$ 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 $x$ and an integer constant such as (3) below.

$\tag{3} 0 = 10x - 20$

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

At this point, we know that we have a term with $x$ variable such as $12x$ and we can use an accumulator variable in Go to hold the sum of the coefficients of all terms with $x$ . 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.

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.

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.

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 $x$ variable and an integer constant. For example equation (2) will become (4) as shown below.

$\tag{4} -5x + 4 = 17x - 16 - 12x$

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.

$\tag{5} 0 = 17x - 16 - 12x + 5x - 4$

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.

$\tag{6} -10x + 20 = 0$

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

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

$\tag{7} 0x = 0$

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

$\tag{8} 0x = C$

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 $x$ must be an integer.

$\tag{9} 3x = -10$

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.

$\tag{10} x = 2$

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. Cheers!