首页 > 代码库 > 栈的应用 - 就近匹配
栈的应用 - 就近匹配
链式存储栈的API详情參看我的博文:栈的链式存储 - API实现
就近匹配
差点儿全部的编译器都具有检測括号是否匹配的能力
怎样实现编译器中的符号成对检測?
#include <stdio.h> int main() { int a[4][4]; int (*p)[4]; p = a[0]; return 0;算法思路
从第一个字符開始扫描
当遇见普通字符时忽略。
当遇见左符号时压入栈中
当遇见右符号时从栈中弹出栈顶符号。并进行匹配
匹配成功:继续读入下一个字符
匹配失败:马上停止。并报错
结束:
成功: 全部字符扫描完成。且栈为空
失败:匹配失败或全部字符扫描完成但栈非空
当须要检測成对出现但又互不相邻的事物时
能够使用栈“后进先出”的特性
栈很适合于须要“就近匹配”的场合
主要代码:
// scanner.h // 栈的案例:就近匹配 #include "stdio.h" #include "stdlib.h" #include "linkstack.h" int isLeft(char c) { int ret = 0; switch (c) { case '<': case '(': case '[': case '{': ret = 1; break; default: break; } return ret; } int isRight(char c) { int ret = 0; switch (c) { case '>': case ')': case ']': case '}': ret = 1; break; default: 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; } return ret; } void scanner(const char* code) { LinkStack *stack = LinkStack_Create(); 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]); break; } } ++i; } if (LinkStack_Size(stack) == 0 && code[i] == '\0') { printf("Success!\n"); } else { printf("Fail!\n"); } LinkStack_Destroy(stack); } void playScanner() { const char* code = "#include <stdio.h> int main() { int a[4][4]; int (*p)[4]; p = a[0]; return 0; "; scanner(code); return; }代码详情參看:Github
栈的应用 - 就近匹配
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。