数据结构笔记之十一栈的应用之表达式求值实现_第1页
数据结构笔记之十一栈的应用之表达式求值实现_第2页
数据结构笔记之十一栈的应用之表达式求值实现_第3页
已阅读5页,还剩7页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、11、蛤蟆的数据结构笔记之一栈的应用之表达式求值实现 本篇名言: “人生不售来回票,一旦动身,绝不能复返。” 继续栈应用实现,这次是来看下表达式求值的栈实现。1. 表达式求值表达式求值是设计语言编译中的一个基本问题,它的实现是栈应用的又一个典型例子。任何一个表达式都是由操作数(Operand)、运算符(operator)和界限符(delimiter)组成。操作数可以是常数也可以是变量或变量的标识符。运算符可以分为算术运算符、关系运算符和逻辑运算符三类。界限符有左右括号和表达式结束符。几个算术四则运算的规则:先乘除,后加减;从左算到右先括号内,后括号外此处实现,假定不出现语法错误,否则过于复杂,

2、蛤蟆也不能理解了。2. 运算符优先级对于连个相继出现的操作符0 1和0 2有三种关系:大于、等于和小于。由此可以列出之间的优先级。如卜表:+ -* / ()#+ > >< < <>>- > >< < <>>* > >> > <>>/ > >> > <>>( < << < <=) > >> >>># < << < <=加减乘除优先性都低

3、于 “(”但是高于“”,由运算从左到右可知,当 0仁蔦 令0 1>02 为了算法简洁,在表达式的左边和右边虚设一个“ #”这一对“ #表示一个表达式求值完成。“(”=)“”当一对括号相遇时表示括号内已运算完成。)”和“(”、“ #和 “、“和“ #无法相继出现如果出现则表达式出现语法错误。为实现优先算法,可以使用两个工作栈,一个是OPTR用于寄存运算符,一个是OPND,用于寄存运算数和运算结果。3. 算法基本思路首先置操作数栈为空栈,表达式起始符为“ #为栈底元素。依次读入表达式中的每个字符,若是操作数则进 OPND栈,若是运算符则和 OPTR栈的 栈顶运算符比较优先权作相应操作,直至整

4、个表达式求值完毕(OPTR栈顶元素和当前读入的字符均为“#”'。4. 求值函数 EvaluateExpressio实现根据算法基本思路,代码实现如下:int EvaluateExpressio n()int flag;char c;char x,theta;char a,b);In itStack(&OPTR);Push(&OPTR,'#');In itStack(&OPND);flag=getNext (&c);GetTop(OPTR, &x);while(c匸'#' | x != '#')if(

5、flag = 0)flag = getNext(&c);itch(Precede(x, c)case'v':/栈顶元素优先级低Pop(&OPND,&b);Pop(&OPND,& a);Push(&OPND, Operate®, theta, b)GetTop(OPTR, &x);GetTop(OPND, &c); freestack(&OPTR); freestack(&OPND); return c;5. Main函数实现Main函数实现void mai n()int c;pr in t

6、f( "Please in put one expressi on:"c=EvaluateExpressi on();printf( "Result=%dn" ,c);结果如下图1所示:旳 rWindow5syst-eirn32cnnrd.eKe0=1 &l( SJPlease Inirut ons expression :1 *2*3+4/2#Result =9革按耳意型谡F6.源码可以直接在VS上进行编译运行。#include "stdio.h"#include "stdlib.h"#include &

7、quot;ctype.h"typedef int Status;#define STACK_INIT_SIZE100#define STACKINCREMENT10typedef char SElemType;/*放入堆栈的元素的类型*/ typedef structSElemType *base;SElemType *top;int stacksizeSqStack;判断是否为空栈StatusStackEmpty(SqStackS)if (S.top = S.base)return 1;elsereturn 0;用e返回S的顶元素StatusGetTop(SqStackS, SEl

8、emType *e)if (S.top = S.base)return -1;*e = *(S.top-1);return 1;插入e为新的顶元素StatusPushSqStack *S, SEIemType e)if (S->top - S->base) >= S>stacksize)S->base =(SElemType*)realloc( S->base (S>stacksize+STACKINCREMENT )* sizeof(SElemType) );if(! S->base)exit(-1);S->top = S->bas

9、e +S->stacksize;S->stacksize += STACKINCREMENT ;return 1;/删除S的顶元素,并用e返回其值StatusPop(SqStack *S, SEIemType *e)if (S->top = S->base)return -1;S->top-;*e = *( S->top);return 1;从栈底到栈顶依次对S的每个元素调用函数Visit (), 旦失败操作无效Status ListTraverse( SqStackS,Status (* visit)(SEIemType)SEIemType *p;p=S.

10、base;for(p=S.base;p<S.top;p+)(*visit)(*p);输出元素eStatusoutput(SElemType e)printf( "%d " ,e);return 1/*计算整数表达式的值/*判断输入的某个字符是否是运算符*c表示输入的字符Statusi n(char c,char op)char *p;p=op;while (*p != '0')if(c = *p)*op数组中存放系统能识别的运算符return 1;P+;return 0;/case'#': j=6; break;-/*进行实际的运算*a

11、, b中分别以整数的形式存放两个待运算的操作数 theta中存放代表操作符的字符比较两个运算符的优先级*a,b中存放待比较的运算符*'>'表示 a>b*'0'表示不可能出现的比较*/char Precedehara, char b)int i,j;char pre7=/*运算符之间的优先级制作成一张表格*/'>' '>' '<''<' '<' '>' '>''v','v

12、9;,'v','v','v','=','O','>','>','>','>','0','>','>','v','v','v','v','v','0','=';switch (a)case'+': i=0; break;case'-

13、9;: i=1; break;case'*': i=2; break;case'/': i=3; break case'(': i=4; break;case')': i=5; break;case'#': i=6; break;switch (bcase'+': j=0; break;case'-': j=1; break;case'*': j=2; break;case'/': j=3; break;case'(': j=4; br

14、eak;case')': j=5; break;*结果以整数的形式返回*/int Operate (nt a, char theta, int b) int “result;case'*': result = i * j; break; case'/': result = i / j; break;retur n result;/*从输入缓冲区中获得下一个整数或运算符,并通过n带回到主调函数*返回值为1表示获得的是运算符*返回值为0表示获得的是整形操作数*/nt getNext(char *n)char c;*n=0;while (c=getch

15、ar()=' );/*跳过一个或多个空格 */if (!isdigit(c)/*通过函数判断如果字符不是数字,那么只能是运算符*/n=c;do/*能执行到该条语句,说明字符是数字,此处用循环获得连续的数字*/* n=* n*10+(c- '0');/*把连续的数字字符转换成相对应的整数*/c=getchar(); while(isdigit(c);/*如果下一个字符是数字,进入下一轮循环*/un getc(c,stdi n);/*新读入的字符不是数字,可能是运算符,为了不影响下次读入,把该字符放回到输入缓冲区*/return 0;intEvaluateExpressi on()char a,bGetTop(OPTR, &x);while(c匸'#' | x != '#')if(flag = 0)Push(&OPND,c); flag = getNext(&c);elseGetTop(OPTR, &x); switch(Precede(x, c)case'v':/栈顶元素优先级低Push(&OPTR,c);flag = getNext(&c);break;case'-':/脱括号并接受下一字符Pop(&OPT

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论