Algorithm - solving linear equation in one variable

Question

Given an expression in the form of a string, solve for x. The highest power of x in the expression will be equal to 1. Operators allowed are +, * and -. These are all binary operators. So, 2x would be written as 2*x. Every operator will be followed by a single term or a constant.

For example, consider the following equation:

2*x+5-(4*x-7+(4-2))=10*x-9

This is a perfectly valid equation. Expressions of the form 1*2*3 are invalid, but 1*(2*3) is valid.

Given such an equation, we need to find a solution to x. If the equation is invalid, the program should display an error message.

Can someone give any idea about how this problem can be solved? The only thing that is coming to my mind right now is Lexical Analysis and Parsing using Context Free Grammars. But I have a feeling there is a much easier solution than that. Can someone throw some light on it ?

Parsing sounds like the right way to go, as a first step. – Xymostech Dec 02 '12 at 17:31 — Xymostech, Dec 02 '12 at 17:31

score 5 · Accepted Answer · answered Dec 03 '12 at 00:59

(1) Convert e1 = e2 into e = 0 where e = e1 - e2.

(2) Convert e into ax + b, for some a and b.

(3) Solve, x = -b/a.

Step (2) can be handled recursively, like this:

F(k)     = 0x + k    // For any constant k.
F(x)     = 1x + 0
F(p + q) = let a_1x + b_1 = F(p)
           and a_2x + b_2 = F(q) 
           in  (a_1 + a_2)x + (b_1 + b_2)
    // Similarly for subtraction.
F(p * q) = let a_1x + b_1 = F(p)
           and a_2x + b_2 = F(q) // At least one of a_1 and a_2 must be zero.
           in  (a_1*b_2 + a_2*b_1)x + (b_1*b_2)

Algorithm - solving linear equation in one variable

1 Answers1