How-To Bracket all Possible Evaluations of a Binary Operator for an Arbitrary Input Length

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.

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.

Python Circle

Do you know what the 5 key success factors every programmer must have?

How is it possible that some people become programmer so fast?

While others struggle for years and still fail.

Not only do they learn python 10 times faster they solve complex problems with ease.

What separates them from the rest?

I identified these 5 success factors that every programmer must have to succeed:

1. Collaboration: sharing your work with others and receiving help with any questions or challenges you may have.
2. Networking: the ability to connect with the right people and leverage their knowledge, experience, and resources.
3. Support: receive feedback on your work and ask questions without feeling intimidated or judged.
4. Accountability: stay motivated and accountable to your learning goals by surrounding yourself with others who are also committed to learning Python.
5. Feedback from the instructor: receiving feedback and support from an instructor with years of experience in the field.

I know how important these success factors are for growth and progress in mastering Python.

That is why I want to make them available to anyone struggling to learn or who just wants to improve faster.

With the Python Circle community, you can take advantage of 5 key success factors every programmer must have.

Be part of something bigger and join the Python Circle community.