数据结构系列--栈的实践
数据结构系列--栈的实践
原创慧子和她的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
—
如何将中缀表达式转换成后缀表达式？
解决办法
遍历中缀表达式中的数字和符号
对于数字：直接输出，按照先后顺序成为后缀表达式的一部分
对于符号：
左括号：进栈
符号: 与栈顶元素进行优先级比较
栈顶符号优先级低：进栈
栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
右括号：将栈顶符号弹出并输出，直到匹配左括号
遍历结束：将栈中的所有符号弹出并输出
算法框架
transform(exp)
{创建栈S；i=0；while(exp[i] !='\0'){if(exp[i]为数字)output(exp[i]);}else if(exp[i]为符号){while(exp[i]优先级<= 栈顶符号优先级){output(栈顶符号);Pop(S);}Push(S,exp[i]);} else if(exp[i]为左括号){Push(S,exp[i]);} else if(exp[i]为右括号){while(栈顶符号不为左括号){output(栈顶符号);Pop(S);}从S中弹出左括号；}else{报错，停止循环；}while(Size(S) > 0) &&(exp[i] == '\0')){// 遍历结束的标志output(栈顶符号);Pop(S);}}#include
#include "LinkStack.h"
int isNumber(char c)
{return ('0' <= c) && (c <='9');
}
int isOperator(char c)
{return (c == '+') || (c == '-') || (c == '*') || (c == '/');
}
int isLeft(char c)
{return (c == '(');
}
int isRight(char c)
{return (c == ')');
}int priority(char c)// 定义符号优先级
{int ret = 0;if((c == '+')||(c == '-')){ret = 1;}if((c == '*')||(c == '/')){ret = 2;}return ret;
}void output(char c)
{if(c !='\0'){printf("%c",c);}
}
void transform(const char* exp)
{LinkStack* stack = LinkStack_Create();int i = 0;while(exp[i] != '\0')// 逐个读入{if(isNumber(exp[i])){output(exp[i]);}else if ( isOperator(exp[i]) ){while(priority(exp[i])) <= priority((char)(int)LinkStack_Top(stack)) ){// 比栈顶元素优先级比较output((char)(int)LinkStack_Pop(stack));}LinkStack_Push(stack,(void*)(int)exp[i];}else if(isLeft(exp[i])){LinkStack_Push(stack,(void*)(int)exp[i]);}else if(isRight(exp[i])){ char c = '\0';while(!isleft((char)(int)LinkStack_Top(stack))// 栈顶元素不是左括号输出栈顶元素{output((char)(int)LinkStack_Pop(stack));}LinkStack_Pop(stack);}else{printf("Invalid expression!");break;}i++;}while((LinkStack_Size(stack)>0) && (exp[i] == '\0'))// 遍历结束输出栈中元素{output((char)(int)LinkStack_Pop(stack));}LinkStack_Destory(stack);// 销毁栈否则会内存泄漏
}
int main()
{transform("9+(3-1)*5+8/2");printf("\n");return 0;
} 计算机是如何基于后缀表达式计算的？基于栈
解决方法：
遍历后缀表达式中的符号和数字
对于数字：进栈
对于符号：
从栈中弹出右操作数
从栈中弹出左操作数
根据符号进行运算
将运算结果压入栈中
遍历结束：栈中的唯一数字为计算结果
算法框架：
compute(exp){创建栈S；i= 0;while(exp[i] != '\0'){if(exp[i]为数字）{Push(S,exp[i]);}else if(exp[i]为符号){1.从栈中弹出右操作数2.从栈中弹出左操作数3.根据符号进行运算；4.Push(stack,结果)；}else{报错，停止循环；}i++;}if((Size(S) == 1) && (exp[i] == '\0')) {栈中唯一的数字为运算结果；}返回结果；
}
#include
#include "LinkStack.h"
int isNumder(char c)
{return('0' <= c) && (c <= '9');
}
int Operator(char c)
{return (c == '+') || (c == '-') || (c == '+') || (c== '/');
}
int value(char c)
{return (c - '0');// 字符转成数字
}
int express(int left,int right,char op)
{int ret = 0;switch(op){case '+':ret = left + right;break;case '-':ret = left - right;break;case '*':ret = left * right;break; case '/':ret = left / right;break;defult:break;}return ret;}int compute(const char* exp)
{LinkStack* stack = LinkStack_Create();int ret = 0;int i= 0;while(exp[i] != '\0'){if(isNumder(exp[i])){LinkStack_Push(stack,(void*)value(exp[i]));}else if(isOperator(exp[i])){int right = (int)LinkStack_Pop(stack);int left = (int)LinkStack_Pop(stack);int result = express(left,right,exp[i]);LinkStack_Push(stack,(void*)result);}else{printf("Invalid expression!");break;}i++;}if((LinkStack_Size(stack) == 1) && (exp[i] == !='\0')){ret = (int)LinkStack_Pop(stack);}else// 多了符号，少些数字同样不合法{printf("Invalid expression!");break;}LinkStack_Destory(stack);return ret;
}
int main()
{printf("9+(3-1)*5+8/2 = %d\n",compute("931-5*82/+"));return 0;
} 中缀表达式是人习惯的表达方式
后缀表达式是计算机喜欢的表达方式
通过栈可以方便的将中缀形式变换成后缀表达式
中缀表达式的计算过程类似于程序编译运行的过程
留有疑问：
