数据结构笔记之十一栈的应用之表达式求值实现

1、精选优质文档-倾情为你奉上11、蛤蟆的数据结构笔记之十一栈的应用之表达式求值实现本篇名言：“人生不售来回票，一旦动身，绝不能复返。”继续栈应用实现，这次是来看下表达式求值的栈实现。1. 表达式求值表达式求值是设计语言编译中的一个基本问题，它的实现是栈应用的又一个典型例子。任何一个表达式都是由操作数（Operand）、运算符（operator）和界限符（delimiter）组成。资料个人收集整理，勿做商业用途操作数可以是常数也可以是变量或变量的标识符。运算符可以分为算术运算符、关系运算符和逻辑运算符三类。界限符有左右括号和表达式结束符。几个算术四则运算的规则：n 先乘除，后加减；n 从左算到右n

2、 先括号内，后括号外此处实现，假定不出现语法错误，否则过于复杂，蛤蟆也不能理解了。2. 运算符优先级对于连个相继出现的操作符1和2 有三种关系：大于、等于和小于。由此可以列出“+-*/”之间的优先级。如下表：资料个人收集整理，勿做商业用途 +-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<= )>>>>&#

3、160;>>#<<<<< =加减乘除优先性都低于“（”但是高于“）”，由运算从左到右可知，当1=2 ，令1>2为了算法简洁，在表达式的左边和右边虚设一个“#”，这一对“#”表示一个表达式求值完成。“（”=“）”当一对括号相遇时表示括号内已运算完成。“）”和“（”、“#”和“(”、“(”和“#”无法相继出现如果出现则表达式出现语法错误。为实现优先算法，可以使用两个工作栈，一个是OPTR，用于寄存运算符，一个是OPND，用于寄存运算数和运算结果。资料个人收集整理，勿做商业用途3. 算法基本思路l 首先置操作数栈为空栈，表达式起始符

4、为“#”为栈底元素。l 依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕（OPTR栈顶元素和当前读入的字符均为“#”）。资料个人收集整理，勿做商业用途4. 求值函数EvaluateExpression实现根据算法基本思路，代码实现如下：int EvaluateExpression()int flag;char c;char x,theta;char a,b;char OP="+-*/()#"SqStack OPTR;SqStack OPND;InitStack(&OPTR); Pu

5、sh(&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 '<':/栈顶元素优先级低 Push(&OPTR,c);flag = getNext(&c);b

6、reak;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);freest

7、ack(&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.h"typedef int Statu

8、s;#define 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

9、(-1);S->top=S->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;/插入

10、e为新的顶元素Status Push(SqStack *S, SElemType 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->base +S->stacksize; S->stacksize += STACKINCREMENT; *(S-

11、>top)=e; S->top+; return 1;/删除S的顶元素，并用e返回其值Status Pop(SqStack *S, SElemType *e) if(S->top = S->base) return -1; S->top-; *e = *(S->top); return 1;/从栈底到栈顶依次对S的每个元素调用函数Visit（），一旦失败操作无效Status ListTraverse(SqStack S,Status (*visit)(SElemType)资料个人收集整理，勿做商业用途 SElemType *p; p=S.base; for(

12、p=S.base;p<S.top;p+) (*visit)(*p); return 1;/输出元素eStatus output(SElemType e) printf("%d ",e); return 1;/*计算整数表达式的值 *表达式必须以#结束 *表达式中可以出现多位数字， *表达式中可以出现空格 *运算符包括+,-,*,/,(,) *运算结果可以是多位整数，并以整数的形式返回 */*判断输入的某个字符是否是运算符 *c表示输入的字符 *op数组中存放系统能识别的运算符 */Status in(char c,char op) char *p; p=op; whi

13、le(*p != '0') if(c = *p) return 1; p+; return 0;/*比较两个运算符的优先级 *a，b中存放待比较的运算符 *'>'表示a>b *'0'表示不可能出现的比较 */char Precede(char a, char b) int i,j; char pre7= /*运算符之间的优先级制作成一张表格*/ '>','>','<','<','<','>','&

14、gt;', '>','>','<','<','<','>','>', '>','>','>','>','<','>','>', '>','>','>','>','<',

15、9;>','>', '<','<','<','<','<','=','0', '>','>','>','>','0','>','>', '<','<','<','<','<

16、','0','=' switch(a) case '+': i=0; break; case '-': i=1; break; case '*': i=2; break; case '/': i=3; break; case '(': i=4; break; case ')': i=5; break; case '#': i=6; break; switch(b) case '+': j=0; break; case '

17、-': j=1; break; case '*': j=2; break; case '/': j=3; break; case '(': j=4; break; case ')': j=5; break; case '#': j=6; break; return preij;/*进行实际的运算 *a，b中分别以整数的形式存放两个待运算的操作数 *theta中存放代表操作符的字符 *结果以整数的形式返回 */int Operate(int a, char theta, int b) int i,j,resu

18、lt; i=a; j=b; switch(theta) case '+': result = i + j; break; case '-': result = i - j; break; case '*': result = i * j; break; case '/': result = i / j; break; return result;/*从输入缓冲区中获得下一个整数或运算符，并通过n带回到主调函数 *返回值为1表示获得的是运算符 *返回值为0表示获得的是整形操作数 */int getNext(char *n) char

19、 c; *n=0; while(c=getchar()=' '); /*跳过一个或多个空格*/ if(!isdigit(c) /*通过函数判断如果字符不是数字，那么只能是运算符*/资料个人收集整理，勿做商业用途 *n=c; return 1; do /*能执行到该条语句，说明字符是数字，此处用循环获得连续的数字*/资料个人收集整理，勿做商业用途 *n=*n*10+(c-'0'); /*把连续的数字字符转换成相对应的整数*/ c=getchar(); while(isdigit(c); /*如果下一个字符是数字，进入下一轮循环*/资料个人收集整理，勿做商业用途 u

20、ngetc(c,stdin); /*新读入的字符不是数字，可能是运算符,为了不影响下次读入，把该字符放回到输入缓冲区*/资料个人收集整理，勿做商业用途 return 0;int EvaluateExpression()int flag;char c;char x,theta;char a,b;char OP="+-*/()#"SqStack OPTR;SqStack OPND;InitStack(&OPTR); Push(&OPTR,'#');InitStack(&OPND);flag=getNext(&c);GetTop(OPTR, &x);w