CODEWITHSUNDEEP
algorithm
Zia Ul Rehman
Zia Ul Rehman

Reputation: 2264

Algorithm to find all possible answers of a given mathematical expression

This problem is on my head for some days now, and am wondering what could be the easiest and the best way to solve this problem. Decided to discuss it with the SO community.

Problem states that, we have a string which has some numbers and some operations(valid operations are only +,- and *), now find all possible answers of this mathematical expression by placing braces on all possible places.

For example, if input string is "1+2-3*4"
Answers can be

(((1+2)-3)*4) = 0
(((1+2)-(3*4)) = -9
(1+((2-3)*4) = -3
(1+(2-(3*4))) = -9
((1+(2-3))*4) = 0

Like this, (i might be missing some cases or have wrong calculations, but you got the idea :D ), and assuming we have always valid input in string, and only 1 digit numbers initially, and we have to print all possible combinations with answers, what can be the easiest and/or best algorithms for this.

PS: I don't know if this community is right place for such questions, but i see many questions like these around so i posted this, if this is not the right community for such questions, please guide me about which one is. Thankyou.

Upvotes: 0

Views: 363

Answers (2)

Ron.B.I
Ron.B.I

Reputation: 2766

So this appears as a simple recursion question, whereas your recursion step should be (I'll leave the coding to you):

"Open a pair of brackets here and continue"

and also, if applicable (you have open brackets behind you):

"Close a pair of brackets here and continue"

Wrapping things up - make sure you take into consideration the legality of the expression while you code this:

  1. Your recursion step is preformed after each operation and not after a number.
  2. You close the same amount of brackets as you open.
  3. You don't close a pair of brackets if it's not legal (number of opened brackets >= number of closed brackets at every step of the way).

When you reach the end of the expression, calculate and print out a value.

Edit:

Pseudo code would be something like (Wrote it on the fly, didn't take into consideration corner cases and such, but just enough for you to get the general idea):

public void Solve(string expression,int positions, int currentPosition, int numberOfOpened ,int[] brackets){ if (currentPosition == positions){ // We are done, this method can be implemented by using a stack and // various solutions can be found across StackOverflow. PrintSolution(expression,brackets); return; } // Close and continue recursion if (numberOfOpened > 0){ int[] newBrackets = CloneAndAddClosingBracket(brackets); Solve(expression,positions,currentPosition++,numberOfOpened-1,newBrackets); } // Open and continue recursion int[] newBrackets = CloneAndAddOpeningBracket(brackets); Solve(expression,positions,currentPosition++,numberOfOpened+1,newBrackets); }

Upvotes: 2

JohnnyAW
JohnnyAW

Reputation: 2876

hmm, brackets simply give you priority on functions, so I would create all possible function-trees at parsing:

((1+2)x3): ------------------------- (1+(2x3)):

           x                        +
          / \                      / \
         +   3                    1   x
        / \                          / \
       1   2                        2   3

for printing the results, simply put brackets around every function in the tree

Upvotes: 1

Related Questions