括号匹配问题

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

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

解决此问题,单纯从每种括号的数量上进行匹配是错误的,比如对于 “[ ( ] )”,虽然中括号和圆括号在数量上是匹配的,但它们的顺序却不匹配。 在考察第 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;}

运行结果是:

点这里可以跳转到人工智能网站

发表评论