括号匹配问题

时间：2022-08-19 18:52:42

给定一个字符串，其中的字符只包含三种括号：花括号{ }、中括号[ ]、圆括号( )，即它仅由 “( ) [ ] { }” 这六个字符组成。设计算法，判断该字符串是否有效，即字符串中括号是否匹配。括号匹配要求括号必须以正确的顺序配对，如 “{ [ ] ( ) }” 或 “[ ( { } [ ] ) ]” 等为正确的格式，而 “[ ( ] )” 或 “{ [ ( ) }” 或 “( { } ] )” 均为不正确的格式。

解决此问题，单纯从每种括号的数量上进行匹配是错误的，比如对于 “[ ( ] )”，虽然中括号和圆括号在数量上是匹配的，但它们的顺序却不匹配。 在考察第 i 位字符 c 与前面的括号是否匹配时，如果 c 为左括号，开辟缓冲区记录下来，希望 c 能够与后面出现的同类型最近右括号匹配；如果 c 为右括号，考察它能否与缓冲区中的左括号匹配。这个匹配过程，是检查缓冲区最后出现的同类型左括号，这也就考虑到了后进先出的思想，所以我们很容易想到栈。栈是一种特殊的线性表，只允许在表的顶端 top 进行插入或者删除操作，是一种操作受限制的线性表，栈元素正是服从后进先出原则。因此，我们利用栈来解决这个问题。

检验括号是否匹配的方法可以用"期待的急迫程度"这个概念来描述。 分析可能出现的不匹配的情况有以下三种：

（1）到来的右括弧非是所“期待” 的，即出现的右括号与栈中最后一个左括号不匹配。

（2）到来的是“不速之客”，即再出现右括号时栈已经为空。

（3）直到结束，也没有到来所“期待” 的，所有字符扫描结束后栈中仍有元素。


完整的括号匹配算法流程如下：

从前向后扫描字符串：

  1. 遇到左括号 x，就把 x 压栈；
  2. 遇到右括号 y：
    • 如果发现栈顶元素x和该括号y匹配，则栈顶元素出栈，继续判断下一个字符；
    • 如果栈顶元素x和该括号y不匹配，字符串不匹配；
    • 如果栈为空，字符串不匹配；
  3. 扫描完成后，如果栈恰好为空，则字符串匹配，否则，字符串不匹配。
      我们利用 C++ 中的顺序容器适配器 stack，很容易写出括号匹配算法的代码： 
      #include <iostream>
      #include <stack>
      using namespace std;

      // 判断字符是不是左括号类型
      bool isLeft(char c)
      {
      return (c == '(' || c == '[' || c == '{');
      }

      // 判断右括号与左括号是否匹配
      bool isMatch(char right, char left)
      {
      if (right == ')')
      {
      return (left == '(');
      }

      if (right == ']')
      {
      return (left == '[');
      }

      if (right == '}')
      {
      return (left == '{');
      }
      }

      // 判断字符串是否匹配
      bool matching(char* s)
      {
      stack<char> cs;
      char c;
      while (*s)
      {
      c = *s;
      if (isLeft(c))
      {
      cs.push(c);
      }
      else
      {
      if (cs.empty() || !isMatch(c, cs.top()))
      {
      return false;
      }

      cs.pop();
      }
      ++s;
      }

      if (!cs.empty())
      {
      return false;
      }
      return true;
      }
      测试代码如下：       
      int main()
      {
      char s[] = "{{[]({})}}";
      if (matching(s))
      {
      cout << s << "是匹配的。" << endl;
      }
      else
      {
      cout << s << "是不匹配的。" << endl;
      }

      return 0;
      }
      运行结果是：       括号匹配问题

      标签：

      相关文章