## What will we cover in this tutorial?

Consider addition of the following expression. **5 + 7 + 3**. As addition is associative, the order of evaluation does not matter. Hence, we have that **(5 + 7) + 3 = 5 + (7 + 3)**.

For an arbitrary binary operator **op(x_1, x_2) -> y**, you cannot assume that **op(x_1, op(x_2, x_3)) = op(op(x_1, x_2), x_3)**. Hence, the order of evaluation of a binary operator matters.

The brackets give the order of how the expression is evaluated. Hence, if an operator takes three different inputs, **a, b**, or **c**, then we can write** a(ab),** to symbol it evaluated **ab** first, then the result of **ab** with **a**.

This tutorial will show you how to get all possible evaluations of an arbitrary length input. That is, given an input, e.g., **abab**, how to find a list of all possible evaluations of the input,** [(a(b(ab)), (a((ba)b), (ab)(ab), ((a(ba))b), (((ab)a)b)]**.

Consider that for a moment. How do you program that in Python?

## Step 1: Define the problem

For simplicity we assume we have a binary operator **op: [a, b, c] x [a, b, c] -> [a, b, c]**. The operator can take arguments **op(a, b)** and evaluate it and give, say, **c**.

To make that notation more efficient, we will write **op(ab) = c**. If we make an evaluation table of the operator, say, we will have the following.

op | a | b | c |

a | c | c | b |

b | a | c | b |

c | b | a | a |

**op**.

Hence, we have that **op(aa) = c, op(ab) = c, …, op(cc) = a**.

Now notice, that this operator is not associative or commutative.

It is not commutative, as **op(ab) ≠ op(ba)**.

And it is not associative, as **op(a op(ac)) = op(ab) = c ≠ op(op(aa) c) = op(cc) = a**.

Now we understand why a binary operator needs an order of evaluation. Because, the final output will depend on it.

What we want now, is given an input, e.g., **aac**, how many ways can you set brackets to get a different evaluation of a binary operator, **[(a(ac), ((aa)c)]**.

## Step 2: Breaking the problem down

Now we understand why the problem is important. But how do we solve it?

Breaking it down and think like a programmer.

The base case is a string of length 2, e.g., **aa**, which only has one possible way **(aa)**.

Then we have the case of length 3, e.g. **aac**, which can be broken down into two ways **((aa)c), (a(ac)**. Another way to think of it, is you can break a string of length 3, into a string of length 2 + 1 or 1 + 2.

Then the case of length 4, say, **aaab**, that can be broken down into **(((aa)a)b), ((a(aa))b), ((aa)(ab)), (a((aa)b)), (a(a(ab)))**. Or you could think of it like, 3 + 1, 2 + 2, 1 + 3. Wait, what does that mean?

A drawing might come in handy now.

See, a string of length 4 can be broken down into an instance of length 1 (as the first argument to the operator) and length 3, an instance of length 2 and 2 (each as input to the operator), or of length 3 and 1 (each as input to the operator).

Hence, you break the problem recursively down.

For a string of length 5 you have the following diagram.

Amazing. Now we just need to turn that into code.

## Step 3: How to create a list of all possible brackets for a binary operator

Consider the diagram from last step. Then think about recursion. How do they all add up together?

Recursion, you need a base case. It could be for a string of length 2, but let’s do it for length 1 instead, as you see you want to call for length 1.

```
def get_all_variations(x):
if len(x) == 1:
return [x]
solutions = []
for i in range(1, len(x)):
x1 = x[:i]
x2 = x[i:]
res1 = get_all_variations(x1)
res2 = get_all_variations(x2)
for r1 in res1:
for r2 in res2:
solutions.append('(' + r1 + r2 + ')')
return solutions
res = get_all_variations('aaabc')
for r in res:
print(r)
```

This shows how to create it simple with an example. The function has the base case, where it just returns the element in a string. In the general case, it breaks the string down into two non-zero length string. Then it calls recursively.

For each of the results, it appends all possible solutions together in all possible ways.

The above code gives the following output.

```
(a(a(a(bc))))
(a(a((ab)c)))
(a((aa)(bc)))
(a((a(ab))c))
(a(((aa)b)c))
((aa)(a(bc)))
((aa)((ab)c))
((a(aa))(bc))
(((aa)a)(bc))
((a(a(ab)))c)
((a((aa)b))c)
(((aa)(ab))c)
(((a(aa))b)c)
((((aa)a)b)c)
```

## Conclusion

This is an amazing example of how to solve a computer science problem. The method is a general way to break down into a recursive function. Learning the skills in this tutorial is crucial to become a good problem solver in computer science.