解析括號

堆疊通常用於解析。一個簡單的解析任務是檢查一串括號是否匹配。

例如,字串 ([]) 是匹配的,因為外部和內部括號形成對。()<>) 不匹配,因為最後一個 ) 沒有夥伴。([)] 也不匹配,因為對必須完全位於其他對內或外。

def checkParenth(str):
    stack = Stack()
    pushChars, popChars = "<({[", ">)}]"
    for c in str:
        if c in pushChars:
            stack.push(c)
        elif c in popChars:
            if stack.isEmpty():
                return False
            else:
                stackTop = stack.pop()
                # Checks to see whether the opening bracket matches the closing one
                balancingBracket = pushChars[popChars.index(c)]
                if stackTop != balancingBracket:
                    return False
        else:
            return False

    return not stack.isEmpty()