c - 如何在 C 语言中找到字符串的平衡？

Question

我希望这个程序使用带有入栈和出栈的堆栈实现来递归地解决这个问题。我已经完成了推送和弹出操作，以及这些功能:

用户输入的字符串只能由这些字符组成。任何其他字符都会返回不平衡的。

'(', ')', '{', '}', '[', ']'

平衡字符串的示例如下

()
(())
()()
{()()}
[]
[()[]{}]()
etc..

不平衡的字符串如下所示:

{}}
()[}
[()}
etc..

这是平衡字符串的递归定义:

1. (BASIS)空字符串是平衡的
2. (嵌套)如果 s 也是平衡字符串，则 (s)、[s] 和 {s} 是平衡的。
3. (CONCATENATION)如果 A 和 B 都是字符串，则 AB 也是平衡的。

我不知道我的基本情况是什么，也不知道如何在递归中实现它。我可以没有，但我想学习递归。有什么帮助吗？

Answer 1

我认为你想实现“括号平衡”问题。使用栈就可以轻松解决，无需任何递归操作。您可以按照此操作。

//stk is a stack
// s is a string
for(int i=0; i<s.size(); i++)
{
   if(str[i]=='('||str[i]=='[')
      stk.push(s[i]);
   else if(str[i]==')' && !stk.empty() && stk.top()=='(')
      stk.pop();
   else if(str[i]==']' && !stk.empty() && stk.top()=='[')
      stk.pop();
}

然后通过一个标志就可以判断这串括号是否平衡。您可以从这个问题中获得帮助。我认为与你的问题相同(Basic Recursion, Check Balanced Parenthesis)。