(盐城工学院数据结构课程设计)栈的应用表达式求值

1、栈的应用：表达式求值的设计数据结构课程设计报告栈的应用：表达式求值的设计专业学生姓名班级学号指导教师徐燕萍完成日期1目 录1 设计内容.12 设计分析2.1 系统需求分析.12.1.1 系统目标.12.1.2 主体功能.12.2 系统概要设计.12.2.1 系统的功能模块划分.12.2.2 系统流程图.23 设计实践3.1 基本分析.33.2 中缀表达式求值.43.3 后缀表达式求值.53.4 中缀表达式转换成后缀表达式.64 测试方法4.1 基本测试.74.2 拓展测试.74.3 容错测试.85 程序运行效果.76 设计心得.87 附录：源代码.101栈的应用：表达式求值的设计1 设计内容设

2、计一个表达式求值的程序。该程序必须可以接受包含（，），+，-，*，/，%，和（求幂运算符，ab=ab）的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。2 设计分析2.1系统需求分析2.1.1系统目标利用栈设计一个程序，该程序能够用于表达式求值，程序将读入的中缀表达式转换为后缀表达式，然后读取后缀表达式，输出结果。输入要求：程序从“input.txt”文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。输出要求：对于每一个表达式，将其结果放在“output.txt”文件的每一行中。这些结果可能是值

3、（精确到小数点后两位），也可能是错误信息“ERROR IN INFIX NOTATION”。2.1.2 主体功能能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理负数与小数，判断表达式是否语法正确（包含分母不能为零的情况），正确实现对算术四则混合运算表达式的求值，能够将计算中遇到的问题和结果以文件的形式予以存储。2.2系统概要设计2.2.1系统的功能模块划分1.判断操作数的函数isnum()判断当前所指字符是否属于数字，是就返回1，不是就返回0。2.求运算符优先级函数priority()为了方便判断运算符优先级，先利用switch函数将不同的运算符返回不同的整型数字，在根据数字的大小

4、判断优先级。+，-优先级相同，返回数字相同 ，*，/也是。3.表达式求值函数infix_value()此函数是直接按照设计思路完成问题要求的函数，其中要调用到判断操作符的函数isnum()和求运算符优先级的函数priority()。循环结束弹出栈2的数值，并返回。4.主函数main()定义一个数组存储表达式整个字符串，将返回的数值直接赋值到浮点型的result，输出result。5.两个栈的函数设计： 栈的初始化函数charInit_SeqStack() Init_SeqStack() 栈判空 Empty_SeqStack() char Empty_SeqStack() 入栈函数 Push_S

5、eqStack() charPush_SeqStack() 出栈函数 Pop_SeqStack() charPop_SeqStack() 取栈顶函数 GetTop_SeqStack() charGetTop_SeqStack() 销毁栈 Destory_SeqStack() charDestory_SeqStack()2.2.2系统流程图 开始优先级比较算法Operate 算法建立栈存放操作字符存放数据计算结束表达式是否合法输出表达是值输出错误提示图1 系统流程图3设计实践3.1基本分析在计算机中，算术表达式的计算往往是通过使用栈来实现的。所以，本表达式求值程序的最主要的数据结构就是栈。可以使

6、用栈来存储输入表达式的操作符和操作数。输入的表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式子。表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。操作数既可以是常数，也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。 3.2中缀表达式求值中缀表达式：每个二目运算符在两个运算量的中间，假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、结束符“”，如

7、：(7+15)*(23-28/4)。要对一个简单的算术表达式求值，首先要了解算术四则运算的规则，即： (1) 从左到右； (2) 先乘除，后加减； (3) 先括号内，后括号外。 运算符和界限符可统称为算符，它们构成的集合命名为OPS。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符1和2之间的优先关系必为下面三种关系之一： 1<2，1的优先权低于2。 1=2，1的优先权等于2。 1>2，1的优先权高于2。 实现算符优先算法时需要使用两个工作栈：一个称作operator，用以存放运算符；另一个称作operand，用以存放操作数或运算的中间结果。算法的基本过程如下：首先初

8、始化操作数栈operand和运算符栈operator，并将表达式起始符“”压入运算符栈； 依次读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理： (1) 若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈； (2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行运算后，将运算结果作为中间结果推入operand栈； (3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左

9、右括号相遇，只需将栈顶运算符（左括号）退栈即可。operator栈的栈顶元素和当前读入的字符均为“#”时，说明表达式起始符“#”与表达式结束符“#”相遇，整个表达式求解结束。 int ExpEvaluation() /*读入一个简单算术表达式并计算其值。*/ InitStack(&operand); InitStack(&operator); PushStack(&operator, ); printf(nn Please input an expression (Ending with ) :); ch=getchar(); /*读入表达式中的一个字符*/ while

10、(ch!=|GetTop(operator)!=) if(!In(ch, OPS) /*判断ch是否运算符*/ a=GetNumber(&ch); /* 用ch逐个读入操作数的各位数码，并转化为十进制数a */ PushStack(&operand,a); else switch(Compare(GetTop(operator),ch) case <: PushStack(&operator, ch); ch=getchar(); break; case =: PopStack(&operator,&x); ch=getchar(); break;

11、 case >: PopStack(&operator, &op); PopStack(&operand, &b); PopStack(&operand, &a); v=Execute(a,op,b); PushStack(&operand,v); break; v=GetTop(operand); return(v); 为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式，后缀表达式的运算符在运算对象之后。在后缀表达式中，不再引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，而不用再考虑运算规则和级别。中缀表达式

12、“（a+b*c）-d/e”的后缀表达式为：“abc*+de/-”。3.3后缀表达式求值计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。这是因为表达式中即无括号又无优先级的约束。具体做法：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。 下面是后缀表达式求值的算法，在下面的算法中假设，每个表达式是合乎语法的，并且假设后缀表达式已被存入一个足够大的字符数组A中，且以#为结束字符，为了简化问题，限定运算数的位数仅为一位且忽略了数字字符串与相对应的数据

13、之间的转换问题。 double calcul_exp(char *A) /*本函数返回由后缀表达式A表示的表达式运算结果*/ SeqStarck s; ch=*A+ ; InitStack(s); while(ch!= # ) if(ch!=运算符) PushStack(s, ch); else PopStack(s, &a); PopStack(s, &b); /*取出两个运算量*/ switch(ch) case ch=+： c=a+b; break ; case ch=-： c=a-b; break ; case ch=*： c=a*b; break ; case ch=

14、/ ： c=a/b; break ; case ch=%：c=a%b; break ; PushStack (s, c) ; ch=*A+ ; PopStack(s, result) ;return result ; 3.4中缀表达式转换成后缀表达式将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组A中，转换后的后缀表达式存储在字符数组B中。具体做法：遇到运算对象顺序向存储后缀表达式的B数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而

15、是将其送入B中存放。读者不难写出算法，在此不在赘述。程序的整体算法分两步： 第一步，从”input.txt”文件中读取中缀表达式，并应用运算符栈OpHolder把中缀表达式转换为后缀表达式，将输出结果存放在一个temp文件中。第二步，从temp文件中读取中缀表达式，并应用操作栈Operands计算后缀表达式结果，将结果输出到”output.txt”文件中。4测试方法设计针对程序的input.txt文件，并将运行结果与期望测试进行比较。5 程序运行效果5.1 基本测试：在input文件中输入表达式如下图2： 则输出结果如下图3： 图2 图3图4 5.2扩展测试：在input文件中输入表达式如下图

16、5： 则输出结果如下图6： 图5 图65.3容错测试：在input文件中输入表达式如下图7： 则输出结果如下图8： 图7 图86 设计心得通过此次的课程设计，巩固和加深了我对栈、队列、字符串等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（；提高利用计算机分析解决综合性实际问题的基本能力。在细节问题的分析上，较以往有了很大的提高。在寻求最优解的问题上，也能够找到多种解决方案来使自己的程序收放自如。如，在处理实数的问题上，我采用的是每取得一个字符，就立刻对此字符进行处理的方法。其实，我们可以用一个字符数组，来存储连接着的一系列数字字符，然后再通过atof函数，直接得到字符数组中所存储的数字

17、。再如，对负数问题的处理上，我最初的想法是通过一个标志mark来记录前面的字符是否是负号（或减号），再在后面取到除符号外的数字时，选择是否添加负号。另外，与其他人不同的是，在我的课程设计中，Compare（）函数与其他有着很大的区别。通常情况下，同学们参照课本，都会采用占用7*7=49个空间的数组来分别存储对应两个字符的优先级符号，并对两个字符进行预算之后得到数组中的位置。虽然7*7的数组所占的空间并不是非常大，但在我看来这也是一种浪费，并且空间的浪费并没有换回时间一定的节省。因此，我采用了一种常规的思路。将各种运算符按照数学逻辑上的优先顺序进行排序，并得到两个字符之间的优先级关系。这样一来，

18、我们将不再需要那7*7的数组，且时间复杂度并不大幅增涨。在这个课程设计中，运用到的数据结构的知识主要是栈的知识。栈在各种软件系统中，应用非常广泛。栈的的存储特性(LIFO先进后出)，使得在用栈来编程时，思路清晰明了。在使用递归算法时，栈也是一种很好的选择。此外，这次的课程设计进一步加强了我们运用C语言进行编程，调试，处理问题的能力，加深了我们对算法及数据结构的认识。同时我也意识到，开发程序的早期计划要做的充分，以免出现程序完成后发现不足而带来的修改麻烦。虽然这只是一个小小的软件，但对我们之后的影响确实很大的。7 附：源程序清单#include <stdio.h>#include &

19、lt;stdlib.h>#include <math.h>int PrintError = 0;/*全局变量，0代表正常，1代表表达式出错*/*char类型链表式堆栈，用来存放运算符号，以及用在中缀表达式转换等时候*/typedef struct Node *PtrToNode;typedef PtrToNode Stack;int IsEmpty(Stack S);void MakeEmpty(Stack S);void Push(char X,Stack S);char Top(Stack S);void Pop(Stack S);typedef struct Nodec

20、har Element;PtrToNode Next;/*float类型链表式堆栈，用来存放操作数*/typedef struct FNode *Ptr_Fn;typedef Ptr_Fn FStack;int FisEmpty(FStack S);void FPush(float X,FStack S);float FTop(FStack S);void FPop(FStack S);typedef struct FNodefloat Element;Ptr_Fn Next;void ConvertToPost(FILE *In, Stack Whereat,FILE *Temp);void

21、 Reverse(Stack Rev);void Calculate(FILE *Change, Stack Whereat,FILE *Temp);/*主函数*/int main()FILE *InputFile, *OutputFile,*Temp;/*初始化变量*/Stack Whereat;char sample;InputFile = fopen("Input.txt","r");/*打开文件*/OutputFile = fopen("Output.txt","w");Whereat = malloc(s

22、izeof(struct Node);/*给 Whereat分配空间*/Whereat->Next = NULL;if (!InputFile | !OutputFile) /*错误处理*/printf("intput or output file(s) do not exist.n");return(1);sample = getc(InputFile); while ( sample != EOF)Temp = fopen("Temp.txt","w+"); /*生成Temp文件*/ungetc(sample,InputFi

23、le); /* put back sample字符*/ConvertToPost(InputFile,Whereat,Temp); /*中缀变后缀*/if (PrintError) /*错误处理*/fprintf(OutputFile,"Error in infix notation."); fscanf(InputFile,"n",&sample);PrintError = 0;else if (IsEmpty(Whereat) = 1) /*跳过在input文件中的空格*/else if (IsEmpty(Whereat) != 1)Reve

24、rse(Whereat);if (Top(Whereat) = 'B') /*错误处理，*/ /*A表示操作数B表示运算符*/PrintError = 1; /*后缀表达式第一个元素应是操作数而不是运算符号*/fclose(Temp);Temp = fopen("Temp.txt","r+");Calculate(OutputFile, Whereat,Temp);/*计算结果*/fclose(Temp);MakeEmpty(Whereat);/* 清空Whereat用来处理下一行*/putc('n',OutputFile

25、);/* 在输出文件中换行*/sample = getc(InputFile); /* While循环结束*/free(Whereat); fclose(InputFile);fclose(OutputFile);remove("Temp.txt"); /* 删除Temp.txt*/return 1;/*检查堆栈是否为空*/int IsEmpty(Stack S)return(S->Next=NULL);/*检查float堆栈是否为空*/int FIsEmpty(FStack S)return(S->Next=NULL);/*弹出栈顶元素*/void Pop(S

26、tack S)PtrToNode FirstCell;if (IsEmpty(S)perror("Empty Stack");elseFirstCell = S->Next;S->Next = S->Next->Next;free(FirstCell);/*弹出float栈顶元素*/void FPop(FStack S)Ptr_Fn FirstCell;if (FIsEmpty(S)perror("Empty Stack");elseFirstCell = S->Next;S->Next = S->Next-&g

27、t;Next;free(FirstCell);/*将堆栈置空*/void MakeEmpty(Stack S)if (S = NULL)perror("Must use Createstack first");elsewhile (!IsEmpty(S)Pop(S);/*将float堆栈置空*/void FMakeEmpty(FStack S)if (S = NULL)perror("Must use Createstack first");elsewhile (!IsEmpty(S)Pop(S);/*元素进栈*/void Push(char X, St

28、ack S)PtrToNode TmpCell;TmpCell = (PtrToNode)malloc(sizeof(struct Node);if (TmpCell = NULL)perror("Out of Space!");elseTmpCell->Element = X;TmpCell->Next = S->Next;S->Next = TmpCell;/*float元素进栈*/void FPush(float X, FStack S)Ptr_Fn TmpCell;TmpCell = (Ptr_Fn)malloc(sizeof(struct

29、FNode);if (TmpCell = NULL)perror("Out of Space!");elseTmpCell->Element = X;TmpCell->Next = S->Next;S->Next = TmpCell;/*返回栈顶元素*/char Top(Stack S)if (!IsEmpty(S)return S->Next->Element;perror("Empty Stack");exit(1);return 0;/*返回float栈顶元素*/float FTop(FStack S)if (!

30、FIsEmpty(S)return S->Next->Element;perror("Empty Stack");exit(1);return 0;/*将堆栈元素倒置*/void Reverse(Stack Rev)Stack Tempstack;Tempstack = malloc(sizeof(struct Node);Tempstack->Next = NULL;while (!IsEmpty(Rev)Push(Top(Rev),Tempstack); /*将元素压栈到一个临时堆栈*/Pop(Rev);Rev->Next = Tempstack

31、->Next; /*指向新的堆栈*/*Whereat 说明:Whereat 记录了操作数和运算符号的位置，用A和B区分。A = operand, B = operator. (例如 1+2转换成12+,在whereat中的形式应该是 AAB)OpHolder说明:Char类型的堆栈Opholder用来保存运算符号。*/*将中缀表带式转换为后缀表达式*/void ConvertToPost(FILE *In, Stack Whereat, FILE *Temp)Stack OpHolder;char holder;char lastseen;int digitcounter = 0; /*

32、操作数的计数器*/OpHolder = malloc(sizeof(struct Node); /*初始化*/OpHolder->Next = NULL;holder=getc(In);lastseen = '' /*用来防止输入格式错误，例如两个小数点*/putc(' ',Temp); while (holder !='n') && (holder != EOF)if (holder = ' ')digitcounter = 0;else if ( IsOperator(holder) = -1) /*如果

33、holder不是操作数或运算符号*/PrintError = 1;else if (IsOperator(holder)=0)if (lastseen = holder) && (lastseen = '.') /*错误处理*/PrintError = 1;elselastseen = holder;if (digitcounter = 0)Push('A',Whereat); /*进栈*/digitcounter+;/*计数器加一*/putc(' ',Temp);putc(holder,Temp);elsedigitcounte

34、r = 0;if (lastseen = holder) && (lastseen != '(') && (lastseen != ')') /*"("情况特殊对待*/PrintError = 1;elselastseen = holder;if(IsEmpty(OpHolder)=1) /*当OpHolder为空*/Push(holder,OpHolder);else if(OperatorValue(Top(OpHolder) = 6) /*OpHolder是"("的情况*/if(Ope

35、ratorValue(holder)=5)Pop(OpHolder);elsePush(holder,OpHolder);else if(OperatorValue(holder) = 6) Push(holder,OpHolder);else if(OperatorValue(holder) = 5) /* OpHolder是" )"的情况*/while (IsEmpty(OpHolder) != 1) && (OperatorValue(Top(OpHolder) != 6) putc(' ',Temp);Push('B'

36、,Whereat);putc(Top(OpHolder),Temp);Pop(OpHolder);if (IsEmpty(OpHolder) = 1) /*错误处理,括号不匹配*/PrintError = 1;else Pop(OpHolder);else if(OperatorValue(holder) = OperatorValue(Top(OpHolder) && (OperatorValue(holder) = 3) /*幂运算情况*/Push(holder,OpHolder);else if(OperatorValue(holder) < OperatorVal

37、ue(Top(OpHolder) && OperatorValue(Top(OpHolder) = 3) /*幂运算情况*/putc(' ',Temp);Push('B',Whereat); putc(Top(OpHolder),Temp);Pop(OpHolder);while(IsEmpty(OpHolder) != 1) && (OperatorValue(Top(OpHolder) = 3)Push('B',Whereat);putc(' ',Temp);putc(Top(OpHolder)

38、,Temp); Pop(OpHolder);Push(holder,OpHolder);/*如果当前运算符号的优先级小于或者等于堆栈中的运算符号的优先级,则将其放入temp中，并且将堆栈中的运算符号出栈，放入temp中，直到堆栈为空或者优先级小于堆栈顶元素的优先级*/else if(OperatorValue(Top(OpHolder) >= OperatorValue(holder)while(IsEmpty(OpHolder) != 1) && (OperatorValue(Top(OpHolder) >= OperatorValue(holder) &

39、& (OperatorValue(Top(OpHolder)!=6)putc(' ',Temp);putc(Top(OpHolder),Temp);Push('B',Whereat);Pop(OpHolder);Push(holder,OpHolder);else if(OperatorValue(Top(OpHolder) < OperatorValue(holder) /*如果当前运算符号的优先级大于堆栈中的运算符号的优先级,则将其压入堆栈中*/Push(holder,OpHolder);holder=getc(In); /* While循环结

40、束*/while(IsEmpty(OpHolder)!=1) /*最后如果堆栈中还有运算符号，则一并放到temp中*/Push('B',Whereat);putc(' ',Temp);putc(Top(OpHolder),Temp);Pop(OpHolder);MakeEmpty(OpHolder); free(OpHolder);/*判断类型，1为运算符号，0为操作数，-1为错误*/int IsOperator(char ToCompare)if (ToCompare = '(' | ToCompare = ')'| ToCom

41、pare = '+' | ToCompare = '-' | ToCompare = '*'| ToCompare = '/' | ToCompare = ''| ToCompare = '%')return 1;else if (ToCompare = '1' | ToCompare = '2'| ToCompare = '3' | ToCompare = '4' | ToCompare = '5'| ToCompar

42、e = '6' | ToCompare = '7'| ToCompare = '8' | ToCompare = '9'| ToCompare = '0'| ToCompare = '.') return 0; elsereturn -1;/*返回运算符号的优先级*/int OperatorValue(char ValueToGive)if (ValueToGive = '(')return 6;if (ValueToGive = ')')return 5;if (V

43、alueToGive = '')return 3; if (ValueToGive = '%')return 2;if (ValueToGive = '*') return 2;if (ValueToGive = '/')return 2;if (ValueToGive = '+')return 1;if (ValueToGive = '-')return 1;return 0;/*计算后缀表达式*/void Calculate(FILE *Change, Stack Whereat, FILE *

44、Temp)FStack Operands;float looker;char Op;char spacefinder;float answer = 0;float NumA;float NumB;Operands = (Ptr_Fn)malloc(sizeof(struct FNode);Operands->Next= NULL;while (IsEmpty(Whereat) != 1) && PrintError != 1) /*循环直到Whereat空，或者遇到错误*/if (Top(Whereat) = 'A')fscanf(Temp,"

45、",&spacefinder);fscanf(Temp,"%f",&looker); /*如果是A,则是操作数*/FPush(looker,Operands);Pop(Whereat);else if (Top(Whereat) = 'B')fscanf(Temp," ",&spacefinder); /*如果是B,则是运算符*/Op = getc(Temp);switch(Op) /* 判断是什么运算符*/case(''): /*幂运算*/NumB = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands) /*错误处理*/PrintError = 1;elseNumA = FTop(Operands);FPop(Operands);if (NumA = 0 && NumB < 0)|(NumA<0) && (NumB - (int)NumB != 0)PrintError = 1;elseanswer = pow(NumA,NumB);FPush(answer,Operands);break;case '%&