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 False

openbracket = stack.pop()

if d[openbracket] == c:

continue

else:

return False

return len(stack) == 0