A stack is the natural tool wherever "the last item in comes out first". This lesson covers five classic uses: brackets, RPN, undo/redo, DFS and a monotonic stack. The stack itself was built in the previous lesson (stack implementation); here a plain list is enough.

Bracket checking
Bracket checking

Checking brackets

An opening bracket is pushed. On a closing one we pop the top and check the pair. Three kinds of failure: the pair does not match, a closer meets an empty stack, openers remain at the end. The string is balanced only if none of these happened and the stack is empty. Time O(n), memory O(n).

python
PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(s):
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack.pop() != PAIRS[ch]:
                return False
    return not stack

for s in ["{[()]}", "([)]", "((", ")("]:
    print(s, balanced(s))
text
{[()]} True
([)] False
(( False
)( False

Postfix notation (RPN)