Python Algorithms: Balanced Logic Brackets

At Least One in Many

An OR logic gate. Arturo Urquizo assumed (based on copyright claims). / CC BY-SA (https://creativecommons.org/licenses/by-sa/4.0)

Python with its highly readable syntax is perfect for solving analytical problems, especially if they are unlikely to become more complicated with scale.

One of the recent problems that I completed recently was a coding challenge that required me to write a short program to evaluate if a mathematical formula or has valid brackets. So, if we strip out all the variables and operator to leave just the brackets, they should balance properly without any unclosed bracket encased in another bracket. For instance, {[()]} and [(){}<>] would be considered valid but [(]) would not.

The Edabit challenge that inspired this post is here, so if you want to attempt to solve the problem on your own, do not read any further.

The function accepts a mathematical formula in the form of a string as input. We call it s. In the example below, there are four possible types of brackets — (), [], {}, and <>.

First, we filter out the rest of the characters since we are solely interested in the brackets. More accurately, we are interested in the individual characters that make up the brackets, which fit into the string ‘()[]{}<>’.

A key observation for any valid permutation of brackets is that we would always be able to remove a complete set of brackets in each iteration. These would be the same as removing substrings representing the individual pairs of brackets within the formula. For example, we could remove the substring representing () followed by [] in [()], ()[], and []().

Since we are unsure what brackets are in the example and in what order they should be removed, we write a general boolean while test that cycles through all four possibilities. As long as at least one of the bracket types appear as a substring within the formula, we would keep searching through the possibilities and remove valid brackets. As we continue looping, the formula string would progressively collapse and shorten, exposing yet more valid pairs.

A formula with valid brackets would eventually be completely collapsed into an empty string.

To illustrate, imagine we wanted to figure out if the formula below is valid?

‘[(x + y * ( <a> — <b>))]’

We feed it through the function, and this is what happens to the formula:

[(x + y * ( <a> - <b>))]
[((<><>))]
[(())]
[()]
[]
    # empty!

The last row in the example above is empty — which is done on purpose as this would mean that the formula has a valid arrangement of brackets. In fact, we could set the boolean statement — of the length of the remaining formula is 0 — as the return value.

What if we meddled with the formula and introduced inconsistencies into it?

‘[(x + y * {( <a}> — <b>))]’

We feed the altered formula above into the function and we get:

[(x + y * {( <a}> - <b>))]
[({(<}><>))]
[({(<}>))] # while loop terminates here

The while test fails to detect a proper pair of brackets in the remaining formula and promptly terminates. Since the length of the remaining formula is more than 0, we determine that the formula does not contain valid brackets by returning False.

I found this challenge inspiring as I was agonising over how to keep the program looping as long as there is one valid pair of brackets. There were four possibilities, but only one is needed.

After some thought, I found the solution in embedding a list or generator using comprehension — with the for loop to cycle through each bracket type, checking if the bracket pair is in the formula — into the any function, which only requires one true case to return true overall. Grasping this mechanism was key to solving the problem.