Это часто встречающаяся головоломка программирования, давайте рассмотрим ее поближе и поймем, почему она интересна в Python.
Во-первых, краткое описание проблемы:
Дана строка из 3 символов: ( ) *
Такие как:
((*)
(()*
(()))
(*)))
определить, является ли это допустимой строкой или нет.
Критерии того, является ли строка действительной, следующие:
- левая или правая скобка должна быть закрыта, например:
( )
!! 😆 очевидно, я знаю.
2. * может обозначать левую скобку, правую скобку или ничего.
поэтому * сама по себе является допустимой строкой!
Хорошо, все это звучало достаточно просто, но как воплотить это в программу?
Хм, если бы не звездочка, задача совсем простая:
- начните слева, пройдитесь по каждому символу в строке.
- вести подсчет левых скобок, вычитать 1 левую скобку из каждой встречающейся правой скобки.
- если левый счетчик падает ниже 0, строка недействительна. После прохождения всей строки, если левый счетчик точно равен нулю, то это допустимая строка.
def check_valid_001(input):
left = 0
lp = '('
rp = ')'
for c in input:
if c is lp:
left = left + 1
elif c is rp:
left = left - 1
if left < 0:
return False
if left == 0:
return True
return False
Теперь, если мы попытаемся включить *, как нам изменить этот алгоритм?
def what_to_do(input):
left = 0
lp = '('
rp = ')'
asterisk = '*'
for c in input:
if c is lp:
left = left + 1
elif c is rp:
left = left - 1
elif c is asterisk:
# what to do?
if left < 0:
return False
if left == 0:
return True
return False
Хм, нет немедленного очевидного решения.
Должны ли мы притворяться, что * — это левая фигурная скобка?
elif c is asterisk:
left = left + 1
Это не сработает:
(*
эта строка будет считаться недействительной.
Должны ли мы притворяться, что * — правая фигурная скобка?
elif c is asterisk:
left = left - 1
Но тогда это не сработает:
*)
Хм, я думаю, что хитрость, стоящая за этим, делает эту задачу интересной, потому что она заставляет вас мыслить нестандартно.
В такой ситуации обычно имеет смысл вернуться к основам, другими словами, вернуться к определениям. Каково определение * в контексте этой проблемы?
Звездочка может использоваться как левая скобка, если необходимо, как правая скобка, если необходимо, или как ничего, если не требуется.
О, это очень "нужно"!
Кажется, это намекает на новую переменную состояния: need
Что, если я оставлю переменную под названием «нужна правая скобка»? Когда я перебираю символы в строке, всякий раз, когда я встречаю левую скобку, я знаю, что мне понадобится еще одна правая скобка, а всякий раз, когда я встречаю правую скобку, мне нужно на одну правую скобку меньше.
Однако, если я столкнусь со звездочкой, так как ее можно использовать как правую скобку, мне также понадобится на одну правую скобку меньше!
После того, как я переберу всю строку, если мне нужно ровно ноль фигурных скобок. тогда строка действительна!
def check_valid_002(input):
left = 0
need_right = 0
lp = '('
rp = ')'
asterisk = '*'
for c in input:
if c is lp:
left = left + 1
need_right = need_right + 1
elif c is rp:
left = left - 1
need_right = need_right - 1
elif c is asterisk:
need_right = need_right - 1
if left < 0:
return False
if need_right == 0:
return True
return False
В этой новой версии работает следующая строка:
(*
но если мы просто добавим еще одну звездочку, она перестанет работать:
(**
так как теперь «need_right» будет отрицательным в конце.
Чтобы решить эту проблему, сохраняйте need_right как минимум равным нулю во время каждой итерации:
need_right = max(need_right, 0)
Но тогда эта строка все еще недействительна:
*)
так как в этом случае «лево» стало бы отрицательным, и мы имеем условие:
if left < 0:
return False
Мы не можем удалить это условие, потому что тогда строки типа «())» станут действительными…
Итак, мы должны вернуться к «*)», в данном случае * явно означает левую скобку, поэтому похоже, что нам не хватает увеличения «left»:
elif c is asterisk:
left = left + 1
need_right = need_right - 1
Объединив все вышеперечисленное, мы получили окончательное решение!
def check_valid_final(input):
left = 0
need_right = 0
lp = '('
rp = ')'
asterisk = '*'
for c in input:
if c is lp:
left = left + 1
need_right = need_right + 1
elif c is rp:
left = left - 1
need_right = need_right - 1
elif c is asterisk:
left = left + 1
need_right = need_right - 1
need_right = max(need_right, 0)
if left < 0:
return False
if need_right == 0:
return True
return False
def test(validator):
inputs = [
'())', '(())', '()()', '(()', '(()())',
'*', '**', '(*', '*)',
'(**', '**)', '*()', '((*'
]
for input in inputs:
print(f'test {input} valid: {validator(input)}')
# print('test 001')
# test(check_valid_001)
# print('test 002')
# test(check_valid_002)
print('test final')
test(check_valid_final)
Плюс юнит-тест на бонусные баллы!
