数据结构之线性表——就近匹配（栈的应用）

不念不忘少年蓝@ 2022-05-29 12:21 146阅读 0赞

`1 就近匹配`

`几乎所有的编译器都具有检测括号是否匹配的能力，如何实现编译器中符号的成对检测？例如：检测如下一串代码：`

`2 算法思路 从第一个字符开始扫描，当遇见普通字符时忽略，当遇见左符号时压入栈中，当遇见右符号时从栈中弹出栈顶符号，并进行匹配，匹配成功：继续进入下一个字符；匹配失败：立即停止，报告错误。结束：成功，所有字符扫描完毕，且栈为空。失败：匹配失败或所有字符扫描完毕但栈非空。 当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性。栈非常适合于需要“就近匹配”的场合。 代码实现：其中LinkStack.h LinkStack.c的内容参考点击打开链接3 具体实现如下：`

/*
    从第一个字符开始扫描，当遇见普通字符时忽略，
    当遇见左符号时压入栈中，当遇见右符号时从栈中弹出栈顶符号，
    并进行匹配，匹配成功：继续进入下一个字符；
    匹配失败：立即停止，报告错误
    结束：成功，所有字符扫描完毕，且栈为空
    失败：匹配失败或所有字符扫描完毕但栈非空
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "LinkStack.h"
    
    //判别左符号
    int isLeft(char c)
    {
    	int ret = 0;
    	switch (c)
    	{
    	case '<':
    	case '/':
    	case '(':
    	case '[':
    	case '{':
    		ret = 1;
    		break;
    	default:
    		ret = 0;
    		break;
    	}
    	return ret;
    }
    
    //判别右符号
    int isRight(char c)
    {
    	int ret = 0;
    	switch (c)
    	{
    	case '>':
    	case ']':
    	case '}':
    	case ')':
    		ret = 1;
    		break;
    	default:
    		ret = 0;
    		break;
    	}
    	return ret;
    }
    //进行匹配判断
    int match(char left,char right)
    {
    	int ret = 0;
    	switch (left)
    	{
    	case '<':
    		ret = (right == '>');
    		break;
    	case '(':
    		ret = (right == ')');
    		break;
    	case '[':
    		ret = (right == ']');
    		break;
    	case '{':
    		ret = (right == '}');
    		break;
    	default:
    		ret = 0;
    		break;
    	}
    	return ret;
    }
    int scanner(const char *exp)
    {
    	int        ret = 0;
    	int        i = 0;
    	//1.建立一个空栈 需要一个先进后出的场合 来做就近匹配
    	LinkStack *stack = LinkStack_Create();
    	if (NULL == stack)
    	{
    		ret = -1;
    		printf("func err LinkStack_Create()\n");
    		return ret;
    	}
    	//2.从第一个字符开始扫描，当遇见普通字符时忽略 进行i++,进入下一次扫描
    	while (exp[i]!='\0')
    	{
    		//3.当遇见左符号时压入栈中
    		if (isLeft(exp[i]))
    		{
    			//LinkStack_Push(stack,(void *)(int)exp[i]);
    			//进栈的时候可以存入的是实际数据在内存中的地址
    			//也可以将实际数据直接转换成int型的数据当作地址存入结构体的item成员 
    			//int LinkStack_Push(LinkStack* stack, void* item)
    			//LinkStack_Push(stack,(void *)(char)(int)exp[i]);
    			LinkStack_Push(stack,(void *)(exp+i));
    		}
    		//4.当遇见右符号时从栈中弹出栈顶符号
    		if (isRight(exp[i]))
    		{
    			char *c = (char *)LinkStack_Pop(stack);//遇到右符号，出栈一个符号，与之进行匹配
    			//5.并进行匹配，匹配成功：继续进入下一个字符
    			if ((c == NULL)||!match(*c,exp[i]))//匹配成功，返回来match(*c, code[i])为0，c不为NULL,则错误，不执行下面语句，继续下一轮扫描
    			{
    			//6.匹配失败：立即停止，报告错误
    				printf("%c does not match %c\n",*c, exp[i]);
    				ret = 0;
    
    				break;
    			}
    		}
    		i++;
    	}
    	//7.结束：成功，所有字符扫描完毕，且栈为空
    	if (LinkStack_Size(stack) == 0&&(exp[i]=='\0'))
    	{
    		printf("Succeed!\n");
    		ret = 1;
    	}
    	//8.失败：匹配失败或所有字符扫描完毕但栈非空
    	else
    	{
    		printf("Invalid code!\n");
    	}
    	LinkStack_Destroy(stack);
    	return ret;
    }
    int main()
    {
    	const char * code = "{[4](*p)[4]]";
    	scanner(code);
    	return 0;
    }