你在使用编辑器写代码的时候是否思考过这个问题:如果少写了一个大括号或中括号,编辑器就会提示错误,这种做法是怎么做到的呢?
其实这个检测就可以通过栈模型来实现,括号的数量总是匹配出现的,并且都是与最近的一个匹配。我们可以编写代码来实现这个检测的功能。具体实现思路如下:
从第一个字符开始扫描, 当遇见普通字符时忽略, 当遇见左符号时压入栈中 当遇见右符号时从栈中弹出栈顶符号,并进行匹配. 匹配成功:继续读入下一个字符 匹配失败:立即停止,并报错 结束. ------成功: 所有字符扫描完毕,且栈为空 ------失败:匹配失败或所有字符扫描完毕但栈非空
【实现代码】
以下代码需要用到栈模型链式存储的 LinkStack.h 和 LinkStack.c 头文件:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "LinkStack.h" /***************** 算法思路 ***************** 从第一个字符开始扫描, 当遇见普通字符时忽略, 当遇见左符号时压入栈中 当遇见右符号时从栈中弹出栈顶符号,并进行匹配. 匹配成功:继续读入下一个字符 匹配失败:立即停止,并报错 结束. ------成功: 所有字符扫描完毕,且栈为空 ------失败:匹配失败或所有字符扫描完毕但栈非空*/ 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; } //匹配成功返回1,不成功返回0 return ret; } int isRight(char right) { int ret = 0; switch (right) { case '>': //右尖括号 case ')': //右小括号 case ']': //右中括号 case '}': //右大括号 case '\'': //右单引号 case '\"': //右双引号 ret = 1; //是需要检测的符号返回1 break; default: ret = 0; //不是需要检测的符号返回0 break; } return ret; } int isLeft(char left) { int ret = 0; switch (left) { case '<': //左尖括号 case '(': //左小括号 case '[': //左中括号 case '{': //左大括号 case '\'': //左单引号 case '\"': //左双引号 ret = 1; //是需要检测的符号返回1 break; default: ret = 0; //不是需要检测的符号返回0 break; } return ret; } int read(const char* code) { int i = 0; LinkStack* stack = LinkStack_Create(); while (code[i]) { // 判断是否是左符号 if (isLeft(code[i])) { // 是的话就压如栈中 printf("push = %c\n", code[i]); LinkStack_Push(stack, (void*)&code[i]); //continue; } // 判断是否是右符号 if (isRight(code[i])) { // 如果是则取出栈顶的符号与这个右符号对比 char left = *(char*)LinkStack_Top(stack); if (match(left, code[i])) { // 匹配成功,从栈中弹出匹配过的左符号 printf("pop = %c\n", code[i]); LinkStack_Pop(stack); } else { // 匹配失败直接报错并终止循环 printf("数据异常,匹配失败! left = %c, right = %c\n", left, code[i]); break; } } i++; } // 最后判断栈中是否还有数据,如果还有证明缺少右符号 if (!LinkStack_Size(stack)) { printf("匹配成功!\n"); } else { char ch = *(char*)LinkStack_Top(stack); printf("缺少匹配 %c\n", ch); } // 销毁 LinkStack_Destroy(stack); return 0; } int main(int argc, char* argv[]) { const char* code = "#include <stdio.h> int main() { int a[4][4]; int (*p)[4]; p = a[0]; return 0;}"; read(code); return 0; }