Dyck words

Created on April 18, 2023 by Julien Palard

Write a is_a_dyck_word function, taking a single word argument (a string):

1
2

def is_a_dyck_word(word: str) -> bool:
    ...

What is a Dyck word?

See: https://en.wikipedia.org/wiki/Dyck_language.

A Dyck word is a word composed of two symbols, typically ( and ) (but any pair will do, like [ and ] or even A and B). A Dyck word have to be "well-parenthesized".

A few examples may help here:

1
2
3
4
5
6
7
8
9

assert is_a_dyck_word("") is True
assert is_a_dyck_word("()") is True
assert is_a_dyck_word("(((())))") is True
assert is_a_dyck_word("()()()()") is True
assert is_a_dyck_word("()(())()") is True
assert is_a_dyck_word("(((") is False
assert is_a_dyck_word("((()") is False
assert is_a_dyck_word("()))") is False
assert is_a_dyck_word("()()()(") is False

A string containing more than two different symbols is not valid. Your function have to return False in such cases.

1

assert is_a_dyck_word("ABC") is False

But beware, in this exercise you don't know the symbols in advance! So:

1
2
3
4
5
6
7
8
9

assert is_a_dyck_word("[]") is True
assert is_a_dyck_word("{}") is True
assert is_a_dyck_word("<>") is True
assert is_a_dyck_word("[[]]") is True
assert is_a_dyck_word("{{}}") is True
assert is_a_dyck_word("<<>>") is True
assert is_a_dyck_word("[][]") is True
assert is_a_dyck_word("{}{}") is True
assert is_a_dyck_word("<><>") is True

But it generalizes to any character, as long as there's one character with the role of "the opening one" and one with the role of "the closing one" it should work:

1
2
3
4
5
6

assert is_a_dyck_word("AB") is True
assert is_a_dyck_word("ABAB") is True
assert is_a_dyck_word("AABB") is True
assert is_a_dyck_word("AABBAB") is True
assert is_a_dyck_word("AAABBB") is True
assert is_a_dyck_word("ABABAB") is True

A last few lines to insist on the fact that any character can handle the "opening" role and that any caracter can handle the "closing" role:

1
2
3
4
5
6
7

assert is_a_dyck_word(",.") is True
assert is_a_dyck_word(",.,.") is True
assert is_a_dyck_word("..,,") is True
assert is_a_dyck_word("dodo") is True
assert is_a_dyck_word("mama") is True
assert is_a_dyck_word("papa") is True
assert is_a_dyck_word("tutu") is True

So you'll have also find a way to guess the symbols.

Hint: If you feel overwelmed you can start by using ( and ) just to train yourself, the correction bot will tell you if this part is OK.

So yes, I know, guessing the symbols from the provided string will lead you to strange situations like:

1

assert is_a_dyck_word(")(") is True

Because here the obvious guess is that the opening symbol is ')' and the closing symbol is '('. It's OK.

You know what, I even feel it's comforting, because I initially felt bad about "((()))" being ")))(((" when read from right to left, but it's still a Dyck word under our definition!