<分区>
Possible Duplicate:
Basic Recursion, Check Balanced Parenthesis
我最近在算法设计手册中遇到了这个问题,尽管基于堆栈的算法非常简单我想为这个问题编写一个递归算法,但是作为递归的菜鸟我无法想出太多,所以有人可以帮我解决这个问题吗?
PS 我只看到了关于这个问题的其他帖子,但它们效率不高,而那些效率很高的帖子也不是很解释。
<分区>
Possible Duplicate:
Basic Recursion, Check Balanced Parenthesis
我最近在算法设计手册中遇到了这个问题,尽管基于堆栈的算法非常简单我想为这个问题编写一个递归算法,但是作为递归的菜鸟我无法想出太多,所以有人可以帮我解决这个问题吗?
PS 我只看到了关于这个问题的其他帖子,但它们效率不高,而那些效率很高的帖子也不是很解释。
最佳答案
背景:判断括号是否平衡的问题实际上是一个决策问题,描述它的语言1是context-free language。 .
上下文无关语法可以使用带有堆栈的自动机来解析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) 确切地说:一些语法需要一个非确定性自动机和一个堆栈,但这是一个更理论化的东西,不是这里的问题。
关于algorithm - 检查String是否有平衡括号的递归算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12539039/