数据结构笔记之十一栈的应用之表达式求值实现(共10页).docx
《数据结构笔记之十一栈的应用之表达式求值实现(共10页).docx》由会员分享,可在线阅读,更多相关《数据结构笔记之十一栈的应用之表达式求值实现(共10页).docx(10页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上11、蛤蟆的数据结构笔记之十一栈的应用之表达式求值实现本篇名言:“人生不售来回票,一旦动身,绝不能复返。”继续栈应用实现,这次是来看下表达式求值的栈实现。1. 表达式求值表达式求值是设计语言编译中的一个基本问题,它的实现是栈应用的又一个典型例子。任何一个表达式都是由操作数(Operand)、运算符(operator)和界限符(delimiter)组成。资料个人收集整理,勿做商业用途操作数可以是常数也可以是变量或变量的标识符。运算符可以分为算术运算符、关系运算符和逻辑运算符三类。界限符有左右括号和表达式结束符。几个算术四则运算的规则:n 先乘除,后加减;n 从左算到右n
2、 先括号内,后括号外此处实现,假定不出现语法错误,否则过于复杂,蛤蟆也不能理解了。2. 运算符优先级对于连个相继出现的操作符1和2有三种关系:大于、等于和小于。由此可以列出“+-*/”之间的优先级。如下表:资料个人收集整理,勿做商业用途+-*/()#+-*/(#2为了算法简洁,在表达式的左边和右边虚设一个“#”,这一对“#”表示一个表达式求值完成。“(”=“)”当一对括号相遇时表示括号内已运算完成。“)”和“(”、“#”和“(”、“(”和“#”无法相继出现如果出现则表达式出现语法错误。为实现优先算法,可以使用两个工作栈,一个是OPTR,用于寄存运算符,一个是OPND,用于寄存运算数和运算结果。
3、资料个人收集整理,勿做商业用途3. 算法基本思路l 首先置操作数栈为空栈,表达式起始符为“#”为栈底元素。l 依次读入表达式中的每个字符,若是操作数则进OPND栈,若是运算符则和OPTR栈的栈顶运算符比较优先权作相应操作,直至整个表达式求值完毕(OPTR栈顶元素和当前读入的字符均为“#”)。资料个人收集整理,勿做商业用途4. 求值函数EvaluateExpression实现根据算法基本思路,代码实现如下:int EvaluateExpression()int flag;char c;char x,theta;char a,b;char OP=+-*/()#;SqStack OPTR;SqSta
4、ck OPND;InitStack(&OPTR); Push(&OPTR,#);InitStack(&OPND);flag=getNext(&c);GetTop(OPTR, &x);while(c!=# | x != #)if(flag = 0)Push(&OPND,c);flag = getNext(&c); elseGetTop(OPTR, &x);switch(Precede(x, c)case :/退栈并将运算结果入栈 Pop(&OPTR, &theta);Pop(&OPND,&b);Pop(&OPND,&a);Push(&OPND, Operate(a, theta, b);brea
5、k;GetTop(OPTR, &x);GetTop(OPND, &c);freestack(&OPTR);freestack(&OPND);return c;5. Main函数实现Main函数实现void main() int c; printf(Please input one expression:); c=EvaluateExpression(); printf(Result=%dn,c);结果如下图1所示:6. 源码可以直接在VS上进行编译运行。#include stdio.h#include stdlib.h#include ctype.htypedef int Status;#de
6、fine STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char SElemType; /*放入堆栈的元素的类型*/typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;/构造一个空栈Status InitStack(SqStack *S) S-base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);资料个人收集整理,勿做商业用途 if(!S-base)exit (-1);S-top=S-
7、base; S-stacksize=STACK_INIT_SIZE; return 1;void freestack(SqStack *S)free(S-base);/判断是否为空栈Status StackEmpty(SqStack S) if(S.top = S.base) return 1; else return 0;/用e返回S的顶元素Status GetTop(SqStack S, SElemType *e) if(S.top = S.base) return -1; *e = *(S.top-1); return 1;/插入e为新的顶元素Status Push(SqStack *S
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 笔记 十一 应用 表达式 求值 实现 10
限制150内