Teaching Kids Programming – Enhanced Valid Parenthese String Algorithm using a Stack

Teaching Kids Programming: Videos on Data Structures and Algorithms

We talk about the algorithm to check if a string is a valid Parenthese. How about if the string can also contain curly braces {}, or square brackets []? In this case, we use a stack to push all the opening brackets/curly brakces/square brackets. And when we meet a closing one, we need to check if it matches the opening one.

Be careful also not to access an element form an empty stack – which we need to invalidate it immediately. At last, we also need to check if the stack is empty, as a valid Parenthese string should not have un-closed parentheses.

def validParenthese(s):
    st = []
    for i in s:
        if i in ["(", "[", "{"]:
            st.append(i)
        elif i in [")", "]", "}"]:
            if (len(st) == 0) or (not st[-1] + i in ["()", "[]", "{}"]):
                return False
            st.pop()
    return len(st) == 0

–EOF (The Ultimate Computing & Technology Blog) —