Write a is_a_dyck_word
function, taking a single word
argument (a
string):
def is_a_dyck_word(word: str) -> bool:
...
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: