# Well-Formed Brackets: A Python Coding Challenge Explained

Written on

## Chapter 1 Introduction to Well-Formed Brackets

In 2019, I stumbled upon a seemingly straightforward interview question related to well-formed brackets at a major tech company. Here's how to tackle the problem effectively.

### Section 1.1 The Problem Statement

Create a function named wellformed(string) that checks if a given string of brackets is well-formed. The input string will only consist of the characters [], () and {}. A string is considered well-formed if every opening bracket has a corresponding closing bracket in the correct order. For instance, [(){[]}] is well-formed, whereas [(){[)}] fails due to mismatched brackets. Similarly, [(){[]}]) is incorrect because of an extra closing bracket.

Before reviewing the solution, take a moment to try solving it yourself!

### Section 1.2 Approaching the Solution

To solve this problem, we can utilize a stack data structure. We will traverse the string from left to right, pushing opening brackets onto the stack. When we encounter closing brackets, we will check if they match the most recent opening bracket on the stack.

If a closing bracket does not correspond to the expected opening bracket, we can immediately conclude that the string is not well-formed.

Here is a positive example: [(){[]}]

[ stack: [

( stack: [(

) stack: [ # ) cancels out (

{ stack: [{

[ stack: [{[

] stack: [{ # ] cancels out [

} stack: [ # } cancels out {

] stack: # ] cancels out [

At the end of this process, if our stack is empty, it confirms that every opening bracket had a corresponding closing bracket in the correct position, and we return True.

Conversely, consider this negative example: [(){[)}]

[ stack: [

( stack: [(

) stack: [ # ) cancels out (

{ stack: [{

[ stack: [{[

) return False as ) doesn't correspond to [

In this case, we encounter a mismatch, so we return False without needing to check the rest of the string.

Another negative example: [(){[]}])

[ stack: [

( stack: [(

) stack: [ # ) cancels out (

{ stack: [{

[ stack: [{[

] stack: [{ # ] cancels out [

} stack: [ # } cancels out {

return False as stack isn't empty

Since our stack is still populated at the end, we can conclude that there are unmatched opening brackets, prompting a return of False.

### The Correct Implementation

Here’s how the function can be implemented:

def wellformed(string):

stack = []

d = {'{': '}', '[': ']', '(': ')'}

for c in string:

if c in '[({':

stack.append(c)elif c in '])}':

if len(stack) == 0:

return Falseopenbracket = stack.pop()

if d[openbracket] == c:

continueelse:

return Falsereturn len(stack) == 0

## Conclusion

I hope this explanation was clear and straightforward!

If you wish to support me as a creator, please clap 50 times for this story, leave a comment with your thoughts, and share your favorite part of the content. Your support means a lot!

## Chapter 2 Video Resources

To further enhance your understanding, check out the following videos related to well-formed brackets:

The first video, "Well-formed Brackets (Difficult Python Practice Question 7)" dives deeper into this coding challenge, providing useful insights and tips.

The second video, "Well-Formed Brackets In ONE Line," challenges you to solve this problem in a single line of code, showcasing efficient coding practices.