@Dave solution is perfect. I prefer it over mind.
However, here is an alternate solution.
We know that this is an equation in 'x' with a degree of 1. It means it is
a straight line and root is guaranteed unless of course the equation is of
the form y = c. That is not the case here as it would make the equation
with a degree of 0..
Now, say if root is 't' and 'delta1' and 'delta2' being positive values, we
know f(t - delta1) * f (t - delta2) < 0.
Why ?
f (t) = 0
All f (t - delta1) will share a common sign (either positive or negative).
Same for all f (t - delta2), however the sign here will be reverse. It
depends upon m (slope) but the product of both is guaranteed to be negative.
The graph will be strictly increasing or decreasing. This provides an
ideal use case for *binary search. *
*
*
We take two extreme values assuming root should lie between them, and do a
binary search over it.
To do that, first of all we bring both side of expression to one side.
This is not hard even programmatically, can be done in one line of code.
In [1]: s = "2*x+5-(4*x-7+(4-2))=10*x-9"
In [2]: s.split ('=')[0] + "-1*(" + s.split ('=')[-1] + ")"
Out[2]: '2*x+5-(4*x-7+(4-2))-1*(10*x-9)'
Now, we do a binary search over the expression.
Below is the python code and codepad link [1] since some mail client don't
like indentations.
#!/usr/bin/env python
#-*- coding: utf-8 -*-
def bsearch (exp, lo, hi):
EPS = 0.000001
ret = lo + (hi - lo) / 2
while (lo < hi):
mid = lo + (hi - lo) / 2.0
val_mid = eval (exp.replace ('x', str (mid)))
val_lo = eval (exp.replace ('x', str (lo)))
val_hi = eval (exp.replace ('x', str (hi)))
if (val_mid == 0):
return mid
elif (val_lo * val_mid < 0): // Root lies in between lo and mid.
ret = mid
hi = mid - EPS
else: // Root lies in between mid
and hi.
ret = mid
lo = mid + EPS
return ret
s = "2*x+5-(4*x-7+(4-2))-10*x+9"
print bsearch (s, -1000000, 1000000)
The output,
% python solve.py
1.58333386935
Just like Newton bisection method used to calculate roots, we can use
Epsilon to take care of the fact that root does not vary by Epsilon. The
caveat here however is if we want the answer in the form of
numerator/denominator as in "19/12", it is tough (unless of course we use
fraction module and try some clever optimization, none of which strikes me
so far).
[1] http://codepad.org/85HJj0Eg
On Fri, Apr 5, 2013 at 2:51 AM, Don <dondod...@gmail.com> wrote:
> I like that solution better than the one I suggested.
> Don
>
> On Apr 4, 4:45 pm, Dave <dave_and_da...@juno.com> wrote:
> > @Kumar0746: Technically, you can't solve an _expression_; you can solve
> an
> > _equation_, which is a statement of the form expression = expression,
> which
> > is what you have.
> >
> > Don's suggestion is a good one. Another way is to call the expression on
> > the left side of the equation f(x) and the expression on the right side
> of
> > the equation g(x), and calculate f(0), g(0), f(1), and g(1). Then
> >
> > x = (f(0) -g(0)) / (f(0) - g(0) - f(1) + g(1))
> >
> > In the original poster's example, f(0) = 10, f(1) = 8, g(0) = -9, and
> g(1)
> > = 1, so x = 19/12. Presuming that you want the exact answer, leave it in
> > fractional form, and if the denominator is negative, then negate both
> > numerator and denominator. Then divide both numerator and denominator by
> > their gcd. Finally, if the denominator is 1, report the numerator as the
> > answer; otherwise report the fraction numerator/denominator as the
> answer.
> >
> > Dave
> >
> >
> >
> >
> >
> >
> >
> > On Thursday, April 4, 2013 11:43:20 AM UTC-5, Don wrote:
> > > Simplify the expression by evaluating expressions inside parenthesis
> > > first. Follow the order of evaluation, doing multiplications first and
> > > then addition and subtraction. It should be possible to reduce any
> > > expression to the form
> > > ax+b=0. Then x=-b/a.
> > > Don
> >
> > > On Apr 4, 11:18 am, arun kumar <kumar0...@gmail.com> wrote:
> > > > 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 Given such an equation, we need to find a
> > > > solution to x
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
