资源描述:
《数据结构笔记之十一栈的应用之表达式求值实现.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、11、蛤蟆的数据结构笔记之十一栈的应用之表达式求值实现本篇名言:“人生不售来回票,一旦动身,绝不能复返。”继续栈应用实现,这次是来看下表达式求值的栈实现。1.表达式求值表达式求值是设计语言编译中的一个基本问题,它的实现是栈应用的又一个典型例子。任何一个表达式都是由操作数(Operand)、运算符(operator)和界限符(delimiter)组成。资料个人收集整理,勿做商业用途操作数可以是常数也可以是变量或变量的标识符。运算符可以分为算术运算符、关系运算符和逻辑运算符三类。界限符有左右括号和表达式结束符。几个算术四则运算的规则:n先乘除,后加减;n从左算到右n先括号内,后括号外此处实现,
2、假定不出现语法错误,否则过于复杂,蛤蟆也不能理解了。2.运算符优先级对于连个相继出现的操作符θ1和θ2 有三种关系:大于、等于和小于。由此可以列出“+-*/”之间的优先级。如下表:资料个人收集整理,勿做商业用途 +-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<= )>>>> >>#<<<<< =加减乘除优先性都低于“(”但是高于“)”,由运算从左到右可知,当θ1=θ2 ,令θ1>θ2为了算法简洁,在表达式的左边和右边虚设一个“#”,这一对“#”表示一个表达式求值完成。“(”=“)”当一对括号相遇时表示括号内已运算完成。“)”和“(”、“#”和“(”
3、、“(”和“#”无法相继出现如果出现则表达式出现语法错误。为实现优先算法,可以使用两个工作栈,一个是OPTR,用于寄存运算符,一个是OPND,用于寄存运算数和运算结果。资料个人收集整理,勿做商业用途1.算法基本思路l首先置操作数栈为空栈,表达式起始符为“#”为栈底元素。l依次读入表达式中的每个字符,若是操作数则进OPND栈,若是运算符则和OPTR栈的栈顶运算符比较优先权作相应操作,直至整个表达式求值完毕(OPTR栈顶元素和当前读入的字符均为“#”)。资料个人收集整理,勿做商业用途2.求值函数EvaluateExpression实现根据算法基本思路,代码实现如下:intEvaluateExp
4、ression(){intflag;charc;charx,theta;chara,b;charOP[]="+-*/()#";SqStackOPTR;SqStackOPND;InitStack(&OPTR);Push(&OPTR,'#');InitStack(&OPND);flag=getNext(&c);GetTop(OPTR,&x);while(c!='#'
5、
6、x!='#'){if(flag==0){Push(&OPND,c);flag=getNext(&c);}else{GetTop(OPTR,&x);switch(Precede(x,c)){case'<'://栈顶元素优先级低Pu
7、sh(&OPTR,c);flag=getNext(&c);break;case'='://脱括号并接受下一字符Pop(&OPTR,&x);flag=getNext(&c);break;case'>'://退栈并将运算结果入栈Pop(&OPTR,&theta);Pop(&OPND,&b);Pop(&OPND,&a);Push(&OPND,Operate(a,theta,b));break;}}GetTop(OPTR,&x);}GetTop(OPND,&c);freestack(&OPTR);freestack(&OPND);returnc;}1.Main函数实现Main函数实现voidmai
8、n(){intc;printf("Pleaseinputoneexpression:");c=EvaluateExpression();printf("Result=%d",c);}结果如下图1所示:1.源码可以直接在VS上进行编译运行。#include"stdio.h"#include"stdlib.h"#include"ctype.h"typedefintStatus;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefcharSElemType;/*放入堆栈的元素的类型*/typedefstruct{SElemType*b
9、ase;SElemType*top;intstacksize;}SqStack;//构造一个空栈StatusInitStack(SqStack*S){S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));资料个人收集整理,勿做商业用途if(!S->base)exit(-1);S->top=S->base;S->stacksize=STACK_INIT_