Computer Science Canada

Equation solver
Author:  Raknarg [ Sat Jul 27, 2013 9:42 pm ]
Post subject:  Equation solver
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)")
Author:  Zren [ Sat Jul 27, 2013 10:11 pm ]
Post subject:  RE:Equation solver
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.
Author:  Raknarg [ Sat Jul 27, 2013 10:15 pm ]
Post subject:  RE:Equation solver
Oh right, I forgot about that, thanks. Ill throw that in.
Author:  Dreadnought [ Sun Jul 28, 2013 12:33 am ]
Post subject:  Re: Equation solver
It appears to have trouble with order of operations.

Turing:
% Passes "1+2" to strint() and produces an error
equationSolver("1+2*3")
Author:  Raknarg [ Sun Jul 28, 2013 12:47 am ]
Post subject:  RE:Equation solver
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
Author:  Raknarg [ Sun Jul 28, 2013 12:53 am ]
Post subject:  Re: Equation solver
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
Author:  Raknarg [ Sun Jul 28, 2013 1:12 am ]
Post subject:  RE:Equation solver
If anyone else has some input, thatd be great as well. Are there better ways to write this? Has anyone else done this?
Author:  Dreadnought [ Sun Jul 28, 2013 10:32 am ]
Post subject:  Re: Equation solver
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.
Author:  Raknarg [ Sun Jul 28, 2013 11:47 am ]
Post subject:  RE:Equation solver
The recursive evaluation was the only way I could figure out how to solve it.

And what do you mean by putting it everywhere?
Author:  Raknarg [ Sun Jul 28, 2013 12:01 pm ]
Post subject:  Re: Equation solver
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.
Author:  Dreadnought [ Sun Jul 28, 2013 1:17 pm ]
Post subject:  Re: Equation solver
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.
Author:  Raknarg [ Sun Jul 28, 2013 2:18 pm ]
Post subject:  RE:Equation solver
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
Author:  Dreadnought [ Sun Jul 28, 2013 3:10 pm ]
Post subject:  Re: Equation solver
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.
Author:  Raknarg [ Sun Jul 28, 2013 3:29 pm ]
Post subject:  RE:Equation solver
Yes thats true. Didn't think of that.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy