数据结构设计报告-栈的应用-表达式求值的设计

数据结构课程设计报告栈的应用:表达式求值的设计目 录1 设计内容12 设计分析12.1 后缀表达式设计12.2中缀到后缀的转换设计23设计实践33.1实现要求33.2 中缀表达式求值33.3后缀表达式求值43.4 中缀表达式转换成后缀表达式44测试方法45程序运行效果56 设计心得67 附录6栈的应用:表达式的求值的设计1 设计内容 设计一个表达式求值的程序。该程序必须可以接受包含(,),+,-,*,/,%,和（求幂运算符，ab=ab）的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。输入要求：程序从“input.txt”文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件在文件的结尾处停止。输出要求：对于每个表达式，将其结果放在“output.txt”文件的每一行中。这些结果可能是值，也可能是错误信息“ERROR IN INFIX NOTATION”。 2 设计分析2.1 后缀表达式设计后缀表达式是由一系列的运算符、操作数组成的表达式，其中运算符位于两个操作数之后。后缀表达式很容易通过应用栈实现表达式的计算。其基本过程是：当输入一个操作数时，它被压入栈中，当一个运算符出现时，就从栈中弹出适当数量的操作数，对该运算进行计算，计算结果再压回栈中。对于最常见的二元运算符来说，弹出的操作数只有两个。处理完整个后缀表达式之后，栈顶上的元素就是表达式的结果值。整个计算过程不需要理解计算的优先级规则。2.2中缀到后缀的转换设计从上面的分析可知，后缀表达式是很容易应用栈进行计算的，但要处理的是中缀表达式。同样，也可以应用栈将中缀表达式转换为后缀表达式。此时，栈里要保存的是运算符，而在后缀表达式计算中，栈里保存的是操作数。应用栈将中缀表达式转换为后缀表达式的基本过程如下。从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理：如果遇到空格，则认为是分隔符，不需处理。若遇到操作数，则直接输出。若是左括号，则将其压入至栈中。若遇到的是右括号，表明括号的中缀表达式已经扫描完毕，把括号中的运算符退栈，并输出。若遇到的是运算符，当该运算符的优先级大于栈顶运算符的优先级时，则把它压栈，当该运算符的优先级小于等于栈顶运算符时，将栈顶运算符退栈并输出，再比较新的栈顶运算符，按同样处理方法，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈。若中缀表达式处理完毕，则要把栈中存留的运算符一并输出。上述处理过程的一个关键是不同运算符优先级的设置。在程序实现中，可以用一个数来代表运算符的优先级，优先级数值越大，它的优先级越高，这样的优先级的比较就转换为两个数的大小比较。程序的整体算法过程分两步：第一步，从“input.txt”文件中读取中缀表达式，并应用运算符栈OpHolder把中缀表达式转换为后缀表达式，将输出结果（转换后得到的后缀表达式）存放在一个temp文件中。第二步，从temp文件中读取后缀表达式，并应用操作数栈Operands计算后缀表达式结果，将结果输出到“output.txt”文件中。本程序中的栈采用前面所述的带头节点的链式存储结构，涉及两种类型：用于存储运算符号的char类型的链栈以及用于存储操作数的float类型的链栈。本程序将整个求值过程分解为两个步骤：中缀表达式转换为后缀表达式、计算后缀表达式结果值。其实，可以将这两个过程统一合并在一起完成，当然也同样需要操作数和运算符这两类栈。另外，本程序中，应用函数OperatorValue来判别运算符的优先级，一种更灵活的方式是应用数组来记录各运算符的优先级。读者可应用以上思路对本程序进一步改进。3设计实践3.1实现要求本程序的输入形式是“input.txt”文件，输出结果存放到“output.txt”文件中。在输入文件中等式的格式必须是中缀格式，例如1+2*3，而且每一行只允许一个表达式。本程序将读入的中缀表达式转换为后缀表达式，并存放在temp,txt文件中；随后从temp.txt中读取后缀表达式，并将计算结果输入到output.txt中。一个char类型的栈“Whereat”用来记录后缀表达式中操作数和运算符号的顺序，以决定需要多少次计算。3.2 中缀表达式求值中缀表达式：每个二目运算符在两个运算量的中间，假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、结束符“”，如：(7+15)*(23-28/4)。要对一个简单的算术表达式求值，首先要了解算术四则运算的规则，即： (1) 从左到右； (2) 先乘除，后加减； (3) 先括号内，后括号外。 运算符和界限符可统称为算符，它们构成的集合命名为OPS。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符1和2之间的优先关系必为下面三种关系之一： 12，1的优先权高于2。 实现算符优先算法时需要使用两个工作栈：一个称作operator，用以存放运算符；另一个称作operand，用以存放操作数或运算的中间结果。算法的基本过程如下：首先初始化操作数栈operand和运算符栈operator，并将表达式起始符“”压入运算符栈； 依次读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理： (1) 若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈； (2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行运算后，将运算结果作为中间结果推入operand栈； (3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。operator栈的栈顶元素和当前读入的字符均为“#”时，说明表达式起始符“#”与表达式结束符“#”相遇，整个表达式求解结束。 3.3后缀表达式求值计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。这是因为表达式中即无括号又无优先级的约束。具体做法：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。 下面是后缀表达式求值的算法，在下面的算法中假设，每个表达式是合乎语法的，并且假设后缀表达式已被存入一个足够大的字符数组A中，且以#为结束字符，为了简化问题，限定运算数的位数仅为一位且忽略了数字字符串与相对应的数据之间的转换问题。3.4 中缀表达式转换成后缀表达式将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组A中，转换后的后缀表达式存储在字符数组B中。具体做法：遇到运算对象顺序向存储后缀表达式的B数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其送入B中存放，程序的整体算法分两步： 第一步，从”input.txt”文件中读取中缀表达式，并应用运算符栈OpHolder把中缀表达式转换为后缀表达式，将输出结果存放在一个temp文件中。第二步，从temp文件中读取中缀表达式，并应用操作栈Operands计算后缀表达式结果，将结果输出到”output.txt”文件中。4测试方法测试项目测试实例期望测试结果基本测试3.003.001+2+3-42.001 + 23.004.99+5.99+6.99*1.0618.39（3*5*（4+8）%2）0.00223256.0022.5350535.16(2-4)3-8.00扩展测试2.5-3.4/2+1*22.80(2.5)*(3-2)+5.6-190%32(1+1)-19.901+2+36.001*2*36.00(1+2)*3+4/(5+1*4)+3.2612.703+4-6.7+88.302.9*1.2+0.5-4%3/2+4(5-5)4.4823-(5+2)/7*9-1.0050-322+4%2-7*(3)-52.00(2)-3)-1.002.526.252(4.4-2.4)4.002(4.4-3.1)2.46(2-4)3-8.00(2-4)(5-8)-0.13容错测试1+2（ERROR IN INFIX NOTATION2/0ERROR IN INFIX NOTATION2%0ERROR IN INFIX NOTATION（2-4）3.1ERROR IN INFIX NOTATION2.5%2ERROR IN INFIX NOTATION2%2.5ERROR IN INFIX NOTATION2+3)(-5ERROR IN INFIX NOTATION(2)-3)ERROR IN INFIX NOTATION(2)-3)ERROR IN INFIX NOTATION3.5/(1-1)ERROR IN INFIX NOTATION(5.6-2)%3ERROR IN INFIX NOTATION5%(3.2-2.1)ERROR IN INFIX NOTATION3.0.2+1ERROR IN INFIX NOTATION1+1ERROR IN INFIX NOTATION1#1ERROR IN INFIX NOTATION2 2ERROR IN INFIX NOTATION+-+ERROR IN INFIX NOTATION 5程序运行效果输入如下:输出如下：6 设计心得通过这次课程设计，增加了我对数据结构知识的了解。在具体操作中，也发现自己的不足之处，对于所学知识的理解还不够深刻，运用起来也不够熟练。发现上机调试的重要作用，特别是对对栈处理的基本算法如判空、压栈、弹栈、栈元素倒置等知识的运用有了有了更深的理解。通过实际操作，学会 利用数据结构进行编程的基本思想与方法同时也了解了实验报告撰写的基本要求。回顾起此次课程设计，从拿到题目到完成整个编程，从理论到实践，在这些日子里，可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。同时，我们不能只局限于将书本上的代码看懂，会调试运行，我们要善于发现问题，提出自己的想法，联系实际生活，开拓思维，对程序进行改进和完善。我们要学会通过网络、书籍等多途径。通过这次课程设计使我们懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论。7 附录#include #include #include 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 Nodechar 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 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(sizeof(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,InputFile); /* 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)Reverse(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);/* 在输出文件中换行*/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(Stack 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-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, Stack 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 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 (!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-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; /*操作数的计数器*/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) /*如果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);elsedigitcounter = 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(OperatorValue(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,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) = OperatorValue(holder)while(IsEmpty(OpHolder) != 1) & (OperatorValue(Top(OpHolder) = OperatorValue(holder) & (OperatorValue(Top(OpHolder)!=6)putc( ,Temp);putc(Top(OpHolder),Temp);Push(B,Whereat);Pop(OpHolder);Push(holder,OpHolder);else if(OperatorValue(Top(OpHolder) Next= NULL;while (IsEmpty(Whereat) != 1) & PrintError != 1) /*循环直到Whereat空，或者遇到错误*/if (Top(Whereat) = A)fscanf(Temp, ,&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)|(NumA0) & (NumB - (int)NumB != 0)PrintError = 1;elseanswer = pow(NumA,NumB);FPush(answer,Operands);break;case %: /*取模运算*/NumB = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands)/*错误处理*/PrintError = 1;elseNumA = FTop(Operands);FPop(Operands);if (NumA - (int)NumA != 0) | (NumB - (int)NumB != 0) | (NumB = 0)PrintError = 1;elseanswer = (int)NumA % (int)NumB; /* x mod b*/FPush(answer,Operands);break;case *: /*乘法运算*/NumB = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands)PrintError = 1;elseNumA = FTop(Operands);FPop(Operands);answer = NumA * NumB; /* x * y*/FPush(answer,Operands);break;case /: /*除法运算*/NumB = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands)PrintError = 1;elseNumA = FTop(Operands);FPop(Operands);if (NumB = 0)PrintError = 1; /*分母不为0*/elseanswer = (float)(NumA / NumB); /* x / y*/FPush(answer,Operands);break;case +: /*加法运算*/NumB = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands)PrintError = 1;elseNumA = FTop(Operands);FPop(Operands);answer = NumA + NumB;/* x + y*/FPush(answer,Operands);break;case -: /*减法运算*/NumB = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands) PrintError = 1;elseNumA = FTop(Operands);FPop(Operands);answer = NumA - NumB;/* x - y*/FPush(answer,Operands);break;default:PrintError = 1;break; /*判断结束*/Pop(Whereat); /*循环结束*/if (!PrintError)answer = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands) != 1)fprintf(Change,Error in infix notation.); /*如果还有操作数*/PrintError = 0;elsefprintf(Change,%.2f,answer);elsefprintf(Change,Error in infix notation.);PrintError = 0;FMakeEmpty(Operands);free(Operands);