甘肃龙网

  1. 首页 > 生活 > >

数据结构系列--栈的实践( 二 )

生活百科数据结构


遍历结束：将栈中的所有符号弹出并输出

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

文章插图
算法框架
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;}


上一篇：关于古人植树养花的诗句？

下一篇：回归算法