Problem Solving with a Stack

Problem Solving with a Stack

Because a stack gives back its elements in reverse order, it solves every "most recent first" problem. Two classics:

Reversing: push every character of a string, then pop them all.

def reverse(text):
    stack = []
    for ch in text:
        stack.append(ch)
    out = ""
    while stack:
        out += stack.pop()
    return out

print(reverse("STACK"))   # KCATS

Balanced brackets: scan the expression; push every opening bracket; at a closing bracket, the top of the stack must be the matching opening bracket, so pop it. The expression is balanced if no check fails and the stack is empty at the end.

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

print(balanced("{a*(b+c)}"), balanced("(a+b]"))   # True False

Board questions often combine a list and a stack: "push the elements of a list that satisfy a condition, then pop and display them".

nums = list(map(int, input().split()))
stack = []
for n in nums:
    pass  # push n if it is divisible by 3 or by 5
popped = []
while stack:
    popped.append(stack.pop())
print(*popped if popped else ["Stack empty"])