Skip to content

Valid Parentheses

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def is_valid(s: str):
    stack = []
    pairs = {
        ")":"(",
        "}":"{",
        "]":"["
    }
    for char in s:
        print(f"{'char':<15} {char}")

        if char in pairs.values():
            stack.append(char)

            print(f"{'append':<15} {char}")
            print(f"{'stack':<15} {stack}")
        else:
            if not stack:
                return False

            popped = stack.pop()
            print(f"{'popped':<15} {popped}")

            if popped != pairs[char]:
                return False

    return len(stack) == 0

checks = [("()", True), ("()[]{}", True), ("(]", False), ("([])", True), ("([)]", False)]
for string, result in checks:
    print(20 * "=")
    assert is_valid(string) == result
    print(result)

====================

char            (

append          (

stack           ['(']

char            )

popped          (

True

====================

char            (

append          (

stack           ['(']

char            )

popped          (

char            [

append          [

stack           ['[']

char            ]

popped          [

char            {

append          {

stack           ['{']

char            }

popped          {

True

====================

char            (

append          (

stack           ['(']

char            ]

popped          (

False

====================

char            (

append          (

stack           ['(']

char            [

append          [

stack           ['(', '[']

char            ]

popped          [

char            )

popped          (

True

====================

char            (

append          (

stack           ['(']

char            [

append          [

stack           ['(', '[']

char            )

popped          [

False