数据结构系列--栈的实践 _数据结构

数据结构系列--栈的实践
原创慧子和她的3D慧子和她的3D昨天
#rd
“用栈来解决问题。”C语言中符号的匹配+将中缀表达式转换成后缀表达式
01
—
C语言中符号的匹配
在C语言中一些符号都是成对匹配出现
#include int main(){int a[5][5];int (*p)[4];p = a[0];printf("%d\n",&p[3][3] - &a[3][3]);return 0;}
几乎所有的编译器都具有检测括号是否匹配的能力，如何实现编译器中的符号成对检测？
算法思路从这里开始;
从第一个字符开始扫描
当遇见普通字符时忽略，当遇见左括号时压入栈中
当遇见右括号时从栈中弹出栈顶符号
进行匹配
匹配成功：继续读入下一个字符
匹配失败：立即停止，并报错.
结束：
成功：所有字符扫描完毕，且栈为空
失败:匹配失败或所有字符扫描完毕但栈为空
算法框架

文章插图

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

#include #include #include "LinkStack.h"int isLeft(char c){int ret = 0;switch(c){case '<':case '(':case '[':case '{':case '\'':// 单引号和双引号需要转译case '\"':ret = 1;break;defult;// swich case都要加defult形成好习惯，处理意外情况ret = 0;break;}return ret;}int isRight(char c){int ret = 0;switch(c){case '>':case ')':case ']':case '}':case '\'':case '\"':ret = 1;break;defult;ret = 0;break;}return ret;}int match(char left,char right){int ret = 0;switch(left){case '<':ret = (reght == '>');case '(':ret = (reght == ')');case '[':ret = (reght == ']');case '{':ret = (reght == '}');case '\'':ret = (reght == '\'');case '\"':ret = (reght == '\"');ret = 1;break;defult;ret = 0;break;}}int scanner(const char* code){// 返回0代码编译不过，有匹配问题LinkStack* stack= LinkStack_Create();int ret = 0;int i;while(code[i] != '\0')// 逐个字符扫描{if(isLeft(code[i]))// 判断是左符号就压入栈{LinkStack_Push(stack,(void*)(code + i)); // 压地址进去}if(isRight(code[i]))// 判断是左符号就压入栈{char *c= (char*)LinkStack_Pop(stack)); // 压地址进zhanif((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("succeed!\n");}else{printf("invalued code!\n");ret = 0;}LinkStack_Destory(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;}

总结：
当需要检测成对出现但又不相互相邻的事物时，可以使用栈的“”先进后出“”特性，
栈非常适合于需要“”就近匹配“”的场合
02
—
如何将中缀表达式转换成后缀表达式？
解决办法
遍历中缀表达式中的数字和符号
对于数字：直接输出，按照先后顺序成为后缀表达式的一部分
对于符号：
左括号：进栈
符号: 与栈顶元素进行优先级比较
栈顶符号优先级低：进栈
栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
右括号：将栈顶符号弹出并输出，直到匹配左括号