Equation solver

Raknarg · **Posted:** Sat Jul 27, 2013 9:42 pm

So i made a function here that takes in an equation as a string and solves it. So far it works perfectly, it can take in the basic operations and brackets and performs integer calculations. It seems really big to me and I think I might be doing it a bad way, so any comments would be appreciated.

Turing:

fcn simplify (s : string) : string
var i := 1
var newS := s
loop
if newS (i) = "+" then
if newS (i + 1) = "+" then
newS := newS (1 .. i - 1) + "+" + newS (i + 2 .. *)
elsif newS (i + 1) = "-" then
newS := newS (1 .. i - 1) + "-" + newS (i + 2 .. *)
else
i += 1
end if
elsif newS (i) = "-" then
if newS (i + 1) = "+" then
newS := newS (1 .. i - 1) + "-" + newS (i + 2 .. *)
elsif newS (i + 1) = "-" then
newS := newS (1 .. i - 1) + "+" + newS (i + 2 .. *)
else
i += 1
end if
else
i += 1
end if
exit when i >= length (newS)
end loop
result newS
end simplify

fcn format (s : string) : string
%removes all spaces
var newS := s
var i : int := 1
loop
if newS (1) = " " then
newS := newS (2 .. *)
else
exit
end if
end loop
loop
if newS (*) = " " then
newS := newS (1 .. * -1)
else
exit
end if
end loop

loop
if newS (i) = " " then
newS := newS (1 .. i - 1) + newS (i + 1 .. *)
else
i += 1
end if
exit when i >= length (newS)
end loop

newS := simplify (newS)
result newS
end format

fcn equationSolver (eq : string) : int
var num := "1234567890."
var sym := "+-*/\^"

var firstBracket : int
var firstSign : int
var lastNum, firstNum : int
var newEq := eq
var numBrackets := 1

newEq := format (newEq)

%Splits the equation into bracket section, passes them as equation
loop
numBrackets := 1
firstBracket := index (newEq, "(")
if firstBracket > 0 then
var i : int := firstBracket + 1
loop
%Searches for the right bracket matching the first left bracket
if newEq (i) = "(" then
numBrackets += 1
elsif newEq (i) = ")" then
numBrackets -= 1
end if
if numBrackets = 0 then
newEq := newEq (1 .. firstBracket - 1) + intstr (equationSolver (newEq (firstBracket + 1 .. i - 1))) + newEq (i + 1 .. *)
exit
end if
i += 1
exit when i > length (newEq)
end loop
else
exit
end if
end loop

newEq := simplify (newEq)

% Checks for multiplications/divion.
loop
if index (newEq, "*") < index (newEq, "/") then
firstSign := index (newEq, "*")
if firstSign = 0 then
firstSign := index (newEq, "/")
end if
else
firstSign := index (newEq, "/")
if firstSign = 0 then
firstSign := index (newEq, "*")
end if
end if

var newNum : int

if firstSign > 0 then
%Finds where the first number begins
for decreasing i : firstSign - 1 .. 1
if i - 1 <= length (newEq) then
firstNum := 1
exit
elsif index (num, newEq (i - 1)) = 0 and newEq (i - 1) not= "-" then
firstNum := i
exit
end if
end for
%Finds where the second number stops
for i : firstSign + 1 .. length (newEq)
if i + 1 >= length (newEq) then
lastNum := length (newEq)
exit
elsif index (num, newEq (i + 1)) = 0 then
lastNum := i
exit
end if
end for

if newEq (firstSign) = "*" then
newNum := strint (newEq (firstNum .. firstSign - 1)) * strint (newEq (firstSign + 1 .. lastNum))
else
%Integer division
newNum := floor (strint (newEq (firstNum .. firstSign - 1)) / strint (newEq (firstSign + 1 .. lastNum)))
end if

if lastNum not= length (newEq) then
newEq := intstr (newNum) + newEq (lastNum + 1 .. *)
else
newEq := intstr (newNum)
end if
else
exit
end if
end loop

%Checks for addition and subtraction
loop
%handles cases for negative numbers. Subraction and negative numbers are handled differently.
if newEq (1) = "-" then
if index (newEq (2 .. *), "+") < index (newEq (2 .. *), "-") then
firstSign := index (newEq (2 .. *), "+")
if firstSign = 0 then
firstSign := index (newEq (2 .. *), "-")
end if
else
firstSign := index (newEq (2 .. *), "-")
if firstSign = 0 then
firstSign := index (newEq (2 .. *), "+")
end if
end if
if firstSign not= 0 then
firstSign += 1
end if
else
if index (newEq, "+") < index (newEq, "-") then
firstSign := index (newEq, "+")
if firstSign = 0 then
firstSign := index (newEq, "-")
end if
else
firstSign := index (newEq, "-")
if firstSign = 0 then
firstSign := index (newEq, "+")
end if
end if
end if

var newNum : int

if firstSign > 0 then
for i : firstSign + 1 .. length (newEq)
if i + 1 >= length (newEq) then
lastNum := length (newEq)
exit
elsif index (num, newEq (i + 1)) = 0 then
lastNum := i
exit
end if
end for

if newEq (firstSign) = "+" then
newNum := strint (newEq (1 .. firstSign - 1)) + strint (newEq (firstSign + 1 .. lastNum))
else
newNum := strint (newEq (1 .. firstSign - 1)) - strint (newEq (firstSign + 1 .. lastNum))
end if

if lastNum not= length (newEq) then
newEq := intstr (newNum) + newEq (lastNum + 1 .. *)
else
newEq := intstr (newNum)
end if
else
exit
end if
end loop

result strint (newEq)
end equationSolver

put equationSolver ("2/-(5-7)")

Zren · **Posted:** Sat Jul 27, 2013 10:11 pm

format(s) could be rewritten as:

Python:

def removeWhitespace(s):
s2 = ""
for s_char in s:
if s_char != " ":
s2 += s_char
return s2

Basically filter out all whitespace when you reconstruct the string.

Raknarg · **Posted:** Sat Jul 27, 2013 10:15 pm

Oh right, I forgot about that, thanks. Ill throw that in.

Dreadnought · **Posted:** Sun Jul 28, 2013 12:33 am

It appears to have trouble with order of operations.

Turing:

% Passes "1+2" to strint() and produces an error
equationSolver("1+2*3")

Raknarg · **Posted:** Sun Jul 28, 2013 12:47 am

No it passes the 2*3, just on line 99 it should have a 1 instead of length (newS). Copy and paste issues.

But it's still being weird so i'll look into that

Raknarg · **Posted:** Sun Jul 28, 2013 12:53 am

Fixed, replace the if on line 126 with this: newEq := newEq (1 .. firstNum - 1) + intstr (newNum) + newEq (lastNum + 1 .. *)

I'll just post the whole thing again

Raknarg · **Posted:** Sun Jul 28, 2013 1:12 am

If anyone else has some input, thatd be great as well. Are there better ways to write this? Has anyone else done this?

Dreadnought · **Posted:** Sun Jul 28, 2013 10:32 am

A few other things I noticed (note I'm using your new version).

Turing:

equationSolver("1-1*1") % gives another strint error

% Your division floor's the result of floating point division rather than using integer division (which truncates)
% Maybe you intended to do this, but it can give weird results
equationSolver("1/2+1/-2") >> -1 % instead of 1 div 2 + 1 div -2

As for the design, I personally would have maybe the parsing and evaluating separate.
I like the recursive evaluation style you used for brackets, I probably would have used it everywhere, but that's my opinion.

Raknarg · **Posted:** Sun Jul 28, 2013 11:47 am

The recursive evaluation was the only way I could figure out how to solve it.

And what do you mean by putting it everywhere?

Raknarg · **Posted:** Sun Jul 28, 2013 12:01 pm

I knew Id run into an issue with those... The second one it's because I always floor the value when I should be rounding towards zero, I just threw in the function and replaced floor with it:

Turing:

fcn roundToZero (x : real) : int
if x > 0 then
result floor (x)
else
result ceil (x)
end if
end roundToZero

Fixed the second problem by fixing how it searches for the first number in the dividing/multiplying pair.

Dreadnought · **Posted:** Sun Jul 28, 2013 1:17 pm

Raknarg wrote:

I just threw in the function and replaced floor with it:

Why not just use div?

Raknarg wrote:

The recursive evaluation was the only way I could figure out how to solve it.
And what do you mean by putting it everywhere?

I meant that if you could also use it to evaluate what is to the arguments of binary operations (+, -, *, /).
Basically an expression like 1 + 2 * 3 - 4 / 5 can be rewritten as (((1) + ((2) * (3))) - ((4) / (5))). Clearly we want to evaluate inner braces first and then outer braces. We simply begin with the outer braces and recursively apply our equationSolver to inner braces.

Raknarg · **Posted:** Sun Jul 28, 2013 2:18 pm

Lol I thought of that after I made my function, oh well

Oh yeah, that makes sense, so that way order of operations happens naturally

Dreadnought · **Posted:** Sun Jul 28, 2013 3:10 pm

Of course I don't mean that you should always give equation solver expressions with braces everywhere, but that you can parse expressions in this way and recursively evaluate them naturally.

Raknarg · **Posted:** Sun Jul 28, 2013 3:29 pm

Yes thats true. Didn't think of that.

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members