Unclosed Tag Finder Algorithm

Hi everyone!

I would like to share with you a very simple but interesting algorithm that you could one day use or could be just as interesting to you as it was to me at that time.

We were discussing about lists one day at my first boot camp and then we were given a coding exercise on how we would validate a string if it was properly closed.

Properly Closed String

valid = "(I (a(m)) a String)"

Improperly Closed String

invalid = "(I (a(m) a String)"

At that time we were just talking about parenthesis and brackets. We could still apply this to HTML tags (we’ll see that later).

When our instructor showed us one way of doing this. He told us

“You can use the idea of STACKS to check if the string is properly closed or not”

So here we go!

The Algorithm

---

Create a list the will act as our STACK

---

I think this is pretty straightforward. Let’s create a list called.. stack. Let’s put it inside a checkTag function that receives a string called myString and also create a string to pass for this function

def checkTag(myString):
    stack = []
myString = "[[1,2,3],[a,b,c],[8,9,10],[x,y,z]"

---

Iterate over the string to be checked for opening and closing tags

---

Here we can use a for loop to iterate the string

def checkTag(myString):
    stack = []
    for i in myString:
        #pass
myString = "[[1,2,3],[a,b,c],[8,9,10],[x,y,z]"

---

For every opening tag detected, push it to the stack

---

Let us start the logic of using stacks here. So everytime we see an opening tag, in this case the square bracket “[” we append it to the stack.

    for i in myString:
        if i == '[':
            stack.append(i)

---

For every closing tag detected, pop an opening tag from the stack

---

If we see a closing tag, we then have to pop out an opening tag from the stack since our stack will only be containing opening tags.

    for i in myString:
        if i == '[':
            stack.append(i)
        elif i == ']':
           stack.pop()

But what if we detect a closing tag when there’s no opening tag in the stack? This would mean that the string is already invalid and must return False.

Notice the order in which the line of code was inserted. This is to prevent popping from the stack when there is no value to pop.

    for i in myString:
        if i == '[':
            stack.append(i)
        elif i == ']' and len(stack) is 0:
            return False
        elif i == ']':
            stack.pop()

---

Check stack for string validity

---

Now all we have to do is to check the stack if it contains anything or not using the len() function. If it is empty, the string is properly closed, if it is not then it is invalid.

    return len(stack) is 0

So with an input of
"[[1,2,3],[a,b,c],[8,9,10],[x,y,z]"
The function will return:
False

Try it out!

We can tweak the code a little bit so we can use it to check HTML codes or different tags in the same string. I guess that’s for another post.

See ya!

Here’s the full code:

def checkTag(myString):
    stack = []
    result = ""
    for i in myString:
        if i == '[':
            stack.append(i)
        elif i == ']' and len(stack) is 0:
return False
        elif i == ']':
            stack.pop()

    return len(stack) is 0

myString = "[[1,2,3],[a,b,c],[8,9,10],[x,y,z]"
print(checkTag(myString))