用于检查String是否具有平衡括号的递归算法

Question

可能重复:
基本递归,检查平衡括号

我最近在算法设计手册中遇到了这个问题,即使基于堆栈的算法非常简单,我想为这个问题写一个递归算法,但是由于在递归中是一个菜鸟我不能提出太多,所以可以有人帮我解决这个问题吗？

PS我只看到关于这个问题的其他帖子,但是他们不是很有效率,而且那些人是非常非常有说服力的.

Answer 1

背景:发现括号是否平衡的问题实际上是一个决策问题,描述它的语言¹是一种无上下文的语言.
可以使用具有堆栈²的自动机来解析上下文无关语法

因此,可以针对此问题实现以下迭代解决方案:

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)确切地说:一些语法需要一个非确定性的自动机和一个堆栈,但这是一个更理论化的东西,而不是这里的问题.