5

我对 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

要求之一是我们不使用任何堆栈数据结构，而是使用以下技术：

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

我需要采取的算法步骤有什么想法吗？我真的坚持这个。它不像计算括号那么简单，因为 ( { ) } 的大小写是行不通的；括号计数匹配，但显然这是错误的。

任何帮助我走向正确方向的帮助将不胜感激。

4

5 回答 5

5

您可以使用递归（这本质上也模拟了堆栈，这是对需要发生的事情的普遍共识）：

  • 当你看到一个左括号时，向下递归。
  • 当您看到右括号时：
    • 如果匹配（即与当前函数中的左括号类型相同），则处理它并继续下一个字符（不要递归）
    • 如果不匹配，则失败。
  • 如果您看到任何其他字符，只需转到下一个字符（不要递归）
  • 如果我们到达字符串的末尾并且我们当前有一个没有匹配的左括号，则失败，否则成功。
于 2013-10-15T07:53:33.357 回答
3

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

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

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

其他替代方法（适用于所有上下文无关语言）是CYK Algorithm，但在这里有点过头了。

于 2013-10-15T07:40:47.363 回答
2

这是不使用正则表达式/复杂语言的最简单方法。

您唯一需要的是一个最大长度为 10 的简单数组来模拟堆栈。您需要它来跟踪打开的最后一个括号类型。每次打开括号时，都会将括号类型“推”到数组的末尾。每次关闭括号时，当且仅当括号类型匹配时，您才会从数组末尾“弹出”括号类型。

算法：

遍历字符串中的每个字符。

当您遇到任何类型的左括号时，请将其附加到您的数组中。如果您的数组已满（即您已经存储了 10 个开括号类型），并且您不能追加它，那么您已经知道括号不匹配并且您可以结束您的程序。

当您遇到任何类型的右括号时，如果右括号类型与数组的最后一个元素不匹配，则您已经知道括号不匹配，您可以结束程序，打印它们不匹配。否则，如果闭括号类型与数组的最后一个元素匹配，则将其从数组末尾“弹出”。

最后，如果在迭代结束时数组为空，那么您知道括号匹配。

编辑：在评论中向我指出这是一个显式堆栈，递归可能是使用隐式堆栈的更好方法。

于 2013-10-15T07:51:35.817 回答
2

所以你不能使用堆栈..但是你可以使用数组！这很好。

这可能违反规则，但您可以用数组模拟堆栈。保留数组中“下一个开放点”的索引，并确保从该索引中执行所有插入/删除操作。

我的建议？解析字符串中的每个字符，并使用上述“堆栈”来确定何时添加和删除括号/parens/curlys。

于 2013-10-15T07:42:13.187 回答
1

正如阿米特回答的那样，您肯定需要某种堆栈。这可以在数学上证明。但是，您可以通过使用编译器的堆栈机制来避免在代码中使用堆栈数据结构。这需要您使用递归函数调用。

于 2013-10-15T07:47:24.920 回答