C中的匹配括号程序

Question

我对c编程很新,我有一个与括号匹配算法有关的问题:

基本上,对于CS分配,我们必须执行以下操作:

我们需要提示用户输入1-20个字符的字符串.然后,我们需要报告是否有任何括号匹配.我们需要考虑以下类型的括号"{} []()".

例:

Matching Brackets
-----------------
Enter a string (1-20 characters): (abc[d)ef]gh
The brackets do not match.

另一个例子:

Enter a string (1-20 characters): ({[](){}[]})
The brackets match

其中一个要求是我们不使用任何堆栈数据结构,但使用以下技术:

• 数据类型和基本运算符
• 分支和循环编程构造
• 基本输入和输出功能
• 字符串
• 功能
• 指针
• 数组
• 基本模块化

我需要采取哪些算法步骤的想法？我真的坚持这个.它不像计算括号那么简单,因为({)}的情况不起作用; 括号计数匹配,但显然这是错误的.

任何有助于我正确方向的帮助将非常感激.

Answer 1

您可以使用递归(这实际上也模拟了一个堆栈,这是对需要发生的事情的一般共识):

• 当您看到一个开口支架时,请向下递减.
• 当你看到一个结束括号:
  • 如果它匹配(即与当前函数中的左括号相同的类型),处理它并继续下一个字符(不要递归)
  • 如果它不匹配,则失败.
• 如果你看到任何其他角色,只需转到下一个角色(不要递归)
• 如果我们到达字符串的末尾并且我们当前有一个没有匹配的开始括号,则失败,否则成功.

Answer 2

您在这里描述一种上下文无关语言，您需要验证某个单词是否在该语言中。

这意味着您可以创建描述该语言的上下文无关语法。

对于这种特定语言，可以使用确定性堆栈自动机来验证某个单词是否在该语言中（并非每种上下文无关语言都如此，有些语言需要非确定性堆栈自动机）请注意
，您可以使用递归来模仿堆栈，并为其使用隐式调用堆栈。

其他替代方案（适用于所有上下文无关语言）是CYK 算法，但在这里它是一种矫枉过正。