《数据结构笔记之十一栈的应用之表达式求值实现》由会员分享，可在线阅读，更多相关《数据结构笔记之十一栈的应用之表达式求值实现（12页珍藏版）》请在金锄头文库上搜索。
1、11、蛤蟆的数据结构笔记之一栈的应用之表达式求值实现 本篇名言： “人生不售来回票，一旦动身，绝不能复返。” 继续栈应用实现，这次是来看下表达式求值的栈实现。1. 表达式求值表达式求值是设计语言编译中的一个基本问题，它的实现是栈应用的又一个典型例子。任何一个表达式都是由操作数（Operand）、运算符（operator）和界限符（delimiter）组成。操作数可以是常数也可以是变量或变量的标识符。运算符可以分为算术运算符、关系运算符和逻辑运算符三类。界限符有左右括号和表达式结束符。几个算术四则运算的规则：先乘除，后加减；从左算到右先括号内，后括号外此处实现，假定不出现语法错误，否则过于复杂，
2、蛤蟆也不能理解了。2. 运算符优先级对于连个相继出现的操作符0 1和0 2有三种关系:大于、等于和小于。由此可以列出之间的优先级。如卜表：+ -* / ()#+ - * / ( # 02 为了算法简洁，在表达式的左边和右边虚设一个“ #”这一对“ #表示一个表达式求值完成。“（”=）“”当一对括号相遇时表示括号内已运算完成。）”和“（”、“ #和 “、“和“ #无法相继出现如果出现则表达式出现语法错误。为实现优先算法，可以使用两个工作栈，一个是OPTR用于寄存运算符，一个是OPND,用于寄存运算数和运算结果。3. 算法基本思路首先置操作数栈为空栈，表达式起始符为“ #为栈底元素。依次读入表达式
3、中的每个字符，若是操作数则进 OPND栈，若是运算符则和 OPTR栈的 栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕(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(
4、flag = 0)flag = getNext(&c);itch(Precede(x, c)casev:/栈顶元素优先级低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 tf( Please in put one expressi on:;c=EvaluateExpressi on(
5、);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 ctype.htypedef int Status;#define STACK_INIT_SIZE100#define STACKINCREMENT10typedef char SElemType;/*放入堆栈的元素
6、的类型*/ typedef structSElemType *base;SElemType *top;int stacksizeSqStack;判断是否为空栈StatusStackEmpty(SqStackS)if (S.top = S.base)return 1;elsereturn 0;用e返回S的顶元素StatusGetTop(SqStackS, SElemType *e)if (S.top = S.base)return -1;*e = *(S.top-1);return 1;插入e为新的顶元素StatusPushSqStack *S, SEIemType e)if (S-top -
7、S-base) = Sstacksize)S-base =(SElemType*)realloc( S-base (Sstacksize+STACKINCREMENT )* sizeof(SElemType) );if(! S-base)exit(-1);S-top = S-base +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);re
8、turn 1;从栈底到栈顶依次对S的每个元素调用函数Visit (), 旦失败操作无效Status ListTraverse( SqStackS,Status (* visit)(SEIemType)SEIemType *p;p=S.base;for(p=S.base;p表示 ab*0表示不可能出现的比较*/char Precedehara, char b)int i,j;char pre7=/*运算符之间的优先级制作成一张表格*/ v,v,v,v,v,=,O,0,v,v,v,v,v,0,=；switch (a)case+: i=0; break;case-: i=1; break;case*
9、: 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; break;case): j=5; break;*结果以整数的形式返回*/int Operate (nt a, char theta, int b) int “result;case*: result = i * j; break; case/
10、: result = i / j; break;retur n result;/*从输入缓冲区中获得下一个整数或运算符，并通过n带回到主调函数*返回值为1表示获得的是运算符*返回值为0表示获得的是整形操作数*/nt getNext(char *n)char c;*n=0;while (c=getchar()= );/*跳过一个或多个空格 */if (!isdigit(c)/*通过函数判断如果字符不是数字，那么只能是运算符*/n=c;do/*能执行到该条语句，说明字符是数字，此处用循环获得连续的数字*/* n=* n*10+(c- 0);/*把连续的数字字符转换成相对应的整数*/c=getcha
11、r(); 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)casev:/栈顶元素优先级低Push(&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, theta, b)GetTop(OPND, &c);freestack(&OPTR);freestack(&OPND);return c;
