loading...
Cover image for Go Parser for Linear Equation Solver

Go Parser for Linear Equation Solver

dt3zr profile image Derrick ・6 min read

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

Ax+By=C(1) \tag{1} Ax + By = C

where the coefficients AA , BB and CC 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 yy . Here's one super simple example.

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

We can eliminate one variable - the yy variable - by equating them and solve for xx to find the point.

2x+3=3x+2 2x + 3 = 3x + 2

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

12x2+33x+650x=17x1612x(2) \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 xx as a string. Base on the value of xx , the function returns one of the following strings.

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

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

0=10x20(3) \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".

State machine

At this point, we know that we have a term with xx variable such as 12x12x and we can use an accumulator variable in Go to hold the sum of the coefficients of all terms with xx . 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 xx variable and an integer constant. For example equation (2) will become (4) as shown below.

5x+4=17x1612x(4) \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.

0=17x1612x+5x4(5) \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.

10x+20=0(6) \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 xx and return the result as a string base on the value of xx .

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

0x=0(7) \tag{7} 0x = 0

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

0x=C(8) \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 xx must be an integer.

3x=10(9) \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.

x=2(10) \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!

Posted on by:

dt3zr profile

Derrick

@dt3zr

Passionate coder. Be ployglot for fun. Believe technology makes life better.

Discussion

pic
Editor guide