Возможный дубликат:
Базовая рекурсия, проверка сбалансированных скобок
Недавно я столкнулся с этой проблемой в Руководстве по разработке алгоритмов, хотя алгоритм на основе стека очень тривиален, я хочу написать рекурсивный алгоритм для этой проблемы. Однако, будучи нубом в рекурсии, я не могу многого придумать, так что могу кто-нибудь поможет мне с этой проблемой?
PS Я видел другие посты только по этому вопросу, но они не очень эффективны, а те, что есть, не очень поясняющие.
Предыстория: проблема определения сбалансированности скобок на самом деле является проблемой принятия решения, и язык1, описывающий ее, представляет собой контекстно-свободный язык.
Контекстно-независимые грамматики можно анализировать с помощью автомата со стеком2.
Таким образом, для этой проблемы может быть найдено следующее итеративное решение:
iterative(str):
stack <- empty stack
for each char in str:
if char is open paranthesis: //push the paranhtesis to stack
stack.push(char)
else if char is close parantesis: //if close paranthesis - check if it is closing an open parenthesis
if stack.head() == matchingParanthesis(char):
stack.pop()
else: //if the closing parenthesis do not close anything previously opened, return false
return false
//end of loop - check if all opened parenthesis were closed:
return stack.isEmpty()
Идея состоит в том, что скобка, представляющая открытую область, находится в голове стека, и каждая закрывающая скобка — вы можете проверить, закрывает ли она соответствующую открытую скобку, просмотрев голову стека.
Примечание. Легко видеть, что для скобок одного типа мы могли бы использовать целое число, чтобы имитировать стек (поскольку нам нужно было только подсчитать число, и нам не важен тип скобки).
Кроме того, поскольку алгоритмы цикла и стека действительно похожи на рекурсию, мы можем вывести следующий рекурсивный алгоритм:
checkValidty(str,currentParenthesis,currentIndex):
//currentIndex is a common variable, changed by reference to affect all levels of recursion!
while (currentIndex < str.size()):
char <- str[currentIndex]
currentIndex <- currentIndex + 1
if char is open paranthesis:
//if the recursive call is unseccesfull - end the check, the answer is no
if !checkValidity(str,char,currentIndex):
return false
else if char is close parantesis:
if currentParenthesis == matchingParanthesis(char):
return true
else: //if the closing parenthesis do not close anything previously opened, return false
return false
//end of loop - check if all opened parenthesis were closed:
return currentParenthesis == nil
Вызовите с помощью checkValidty(str,nil,0), где str – проверенная строка.
Нетрудно заметить, что итеративный и рекурсивный алгоритмы на самом деле одинаковы, во втором мы используем стек вызовов и переменную lastParenthesis в качестве головы стека.
(1) Язык — это все слова, принимаемые задачей. например (w) есть на языке, а )w( нет.
(2) если быть точным: некоторым грамматикам нужны недетерминированные автоматы и стек, но это немного больше теоретическая вещь, и здесь это не проблема.
