数据结构：栈的应用_符号匹配

数据结构：栈的应用_符号匹配

算法步骤

算法思路：从第一个字符开始扫描当遇见普通字符时忽略，当遇见左符号时压入栈中当遇见右符号时从栈中弹出栈顶符号进行匹配 匹配成功：继续读入下一个字符 匹配失败：立即停止，并报错结束： 成功：所有字符扫描完毕，且栈为空 失败：匹配失败或所有字符扫描完毕但栈非空

算法框架

scanner(code){ 创建栈 S； i = 0； while（code[i]!='\0'） { if(code[i]为左括号){ Push（S，code[i]）； } if（code[i]为右括号）{ c = Pop(S); if(c与code[i]不匹配){ 报错，停止循环 } } i++; } if((Size(S)==0)&&(code[i]=='\0')){ 匹配成功； }else { 匹配失败，报错 }}

听了国嵌唐老师的课，用C语言实现如下：

LinkList.c LinkList.h LinkStack.c LinkStack.h 前面博客有，请读者自行查阅

main.c

#include #include #include "LinkStack.h" /* run this program using the console pauser or add your own getch, system("pause") or input loop */int isLeft(char c){ int ret = 0; switch(c) { case '<': 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 '}': 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; case '\'': ret = (right=='\''); break; case '\"': ret = (right=='\"'); break; default: ret = 0; break; }}int scanner(const char* code){ LinkStack* stack = LinkStack_Create(); int ret = 0; int i = 0; while(code[i]!='\0') { if(isLeft(code[i])) { LinkStack_Push(stack,(void*)(code + i)); } if(isRight(code[i])) { char* c = (char*)LinkStack_Pop(stack); if((c==NULL)||!match(*c,code[i])) { printf("%c does not match!\n",code[i]); ret = 0; break; } } i++; } if((LinkStack_Size(stack)==0)&&(code[i]=='\0')) { printf("Succeed!\n"); ret=1; } else { printf("Invalid code!\n"); ret = 0; } LinkStack_Destroy(stack); return ret;}int main(int argc, char *argv[]){ const char* code = "void f(int a[]) { int (*p)[5];p = NULL;}"; scanner(code); return 0;}

运行效果：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。