Bracket Validator

The aim of this Python Challenge is to write a script to validate an arithmetic expression by checking that it has a valid sequence of opening and closing brackets.

Let’s consider the following arithmetic expressions to decide whether they contain a valid or invalid combination of brackets:

Opening & Closing Brackets Count

In order to validate whether an expression is valid or not, we could count the number of opening brackets and the number of closing brackets and see if both numbers are the same. Though this would detect a lot of invalid expressions, not all invalid expressions would be detected. For instance, using this approach, the expression (5+2)*)3+4( would appear valid as it contains 2 opening brackets and 2 closing brackets.

Using a stack

A more effective approach is to parse the expression one character at a time and every time an opening bracket is met, the bracket is pushed into a stack. Every time a closing bracket is found, we pop the last opening bracket from the stack (if when a closing bracket is met, the stack is empty then the expression is invalid). Once all characters of the expression have been checked, the stack should be empty. If not the expression is invalid.

Here is the implementation of this approach in Python:

Using multiple types of brackets

More complex expressions may use different types of brackets such as square brackets [], curly brackets {} and parentheses (). We can adapt our script to validate an expression by making sure that when a closing bracket is found, the algorithm checks that it is of the same type as the last bracket that has been pushed into the stack.