Dyck words

Created by julien.palard julien.palard

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

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:

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.

assert is_a_dyck_word("ABC") is False

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

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:

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:

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:

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!

There's no corrections yet, hit the `Submit` button to send your code to the correction bot.

Keyboard shortcuts:

  • Ctrl-Enter: Send your code to the correction bot.
  • Escape: Get back to the instructions tab.

See solutions