数据结构栈的应用—表达式求值课程设计.doc

数据结构课程设计报告题目：栈的应用表达式求值专业计算机科学与技术学生姓名班级B计算机学号指导教师完成日期2012年1月11日一、简介 栈是一种运算受限的线性表，仅允许在表的一端进行插入和删除。对一个栈最基本的操作包括进栈和出栈，即对栈的插入和删除。表达式求值是程序设计语言编译中的一个基本问题，它的实现是栈应用的一个典型例子。本实验的目的是设计一个表达式求值的程序。该程序必须可以接受包括(,),+,-,*,/,%和(求幂运算符)的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。输入要求：程序从“input.txt”文件中读取信息，在这个文件中如果有许多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。输出要求：对于每一个表达式，将结果放在“output.txt”文件中每一行中。这个结果可能是值，也可能是错误信息“ERROR IN INFIX NOTATION”二、算法设计程序的整体算法分两步：1、 从“input。txt”文件中读取中缀表达式，并应用运算符栈OpHolder把中缀表达式转换成后缀表达式，将结果存放在一个temp文件中。2、 从temp文件中读取后缀表达式，并应用操作数栈Operands计算后缀表达式结果将结果输出到“output.txt”文件中。为了实现算法，使用两个工作栈。一个称做OpHolder，用于寄存运算符；另一个称做Operands，用以寄存操作数或运算结果。算法的基本思想是：首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。具体算法如下：OperandType EvaluateExpression()InitStack(Operands); Push(Operands,'#')；InitStack(Operands);c=getchar();While(c!='#'|GetTop(Operands)!='#')if(!In(c,OP)Push(Operands,c);c=getchar();elseswitch(Precede(GetTop(Operands),c)case'<':Push(Operands,c);c=getchar();breakcase'=':Pop(Operands,x); c=getchar();break;case'>':Pop(Operands,theta);Pop(Operands,b); Pop(Operands,a);Push(Operands),Operate(a,theta,b);berakreturn GetTop(OPND);三、测试与结果设计针对程序的input.txt文件，并将运行结果与期望测试结果进行比较 输入数据： 输出数据：测试项目测试实例期望测试结果基本测试3.00 3.00 1+2+3-42.00 1 + 23.00 4.99+5.99+6.99*1.0618.39 (3*5*(4+8)%2)0.00 223256.00 22.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.90 1+2+36.00 1*2*36.00 (1+2)*3+4/(5+1*4)+3.2612.70 3+4-6.7+88.30 2.9*1.2+0.5-4%3/2+4(5-5)4.48 23-(5+2)/7*9-1.00 50-322+4%2-7*(3)-52.00 (2)-3）-1.00 2.526.25 2(4.4-2.4)4.00 2(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四、分析与探讨算术表达式有中缀表示法和后缀表示法，本程序输入的表达式采用中缀表示法。在这种表达式中，二元运算符位于两个操作数之间。因为计算机只能一个字符一个字符的扫描，要想知道那个运算符优先，就必须对整个中缀表达式扫描一遍。而后缀表达式则很容易通过应用栈实现表达式计算，这为实现表达式求值程序提供了一种直接的计算机制。后缀表达式很容易应用栈进行计算，但要处理的是中缀表达式。同样，也可以应用栈将中缀表达式转换为后缀表达式。此时，栈里要保存的是运算符，而在后缀表达式中，栈里保存的是操作数。应用栈将中缀表达式转换成后缀表达式处理过程的关键是不同运算符优先级的设置。在程序实现中，可以用一个数来代表运算符的优先级，优先级数值较大，它的优先级越高，这样优先级的比较就转换成两个数大小的比较。本程序的栈采用带头结点的链式存储结构，涉及两种类型：用于存储运算符号的char类型的链栈以及用于存储操作数的float类型的链栈。栈的操作在链式存储结构上的实现： LinkStack *CreatStack() /初始化栈，并将栈置空LinkStack *S;S=(LinkStack*)malloc(sizeof(LinkStack);if(S=NULL)FatalError("Out of space!");S->next=NULL;return S;int Pop(LinkStack *S) /删除栈顶元素，并返回之LinkStack *FirsCell;if(S->next=NULL)Error("Empty stack!");elseint tempFirsCell=S->next;S->next=S->next->next;temp=FirstCell->data;free(firstCell)；return temp；void Push(int X,LinkStack *S) /元素X进栈LinkStack *TmpCell;TmpCell=(LinkStack *)malloc(sizeof(LinkStack);if(TmpCell=NULL)FatalError("Out of space!");elseTmpCell->data=X;TmpCell->next=S->next;S->next=TmpCell;五：总结 在设计过程中出现了一个cannot convert from “void *”to“struct Node *”Conversion from “void *”to pointer to non_void requires an explicit cast的错误，我通过查阅资料知道了这是由于，所有分配地址要加强制类型转换，因为分配内存后缺省内存是void *.这个错误改正后，程序可以正常运行。通过这次课程设计，我对栈的特性有了清楚的认识，我也深深体会到数据结构真的并不只是书本上的一些知识，上机实践对于这门科目来说真的很重要。平常简简单单的一个运算，也许自己通过加加减减就能得出结果，可是这些算法到底是怎么实现的？平常不会想到，通过实践才发现其中集合了很多我们平时忽略的知识，所以，通过这次实践，我也把书中很多知识巩固了下，加深印象！总之，通过这次课程设计，我确实收益颇多！附录 源代码：#include <stdio.h>#include <stdlib.h>#include <math.h>int PrintError = 0;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;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->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); ConvertToPost(InputFile,Whereat,Temp); /*中缀变后缀*/if (PrintError) /*错误处理*/fprintf(OutputFile,"Error in infix notation."); fscanf(InputFile,"n",&sample);PrintError = 0;else if (IsEmpty(Whereat) = 1) else if (IsEmpty(Whereat) != 1)Reverse(Whereat);if (Top(Whereat) = 'B') /*错误处理，*/ PrintError = 1; fclose(Temp);Temp = fopen("Temp.txt","r+");Calculate(OutputFile, Whereat,Temp);/*计算结果*/fclose(Temp);MakeEmpty(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);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);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);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;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 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; /*指向新的堆栈*/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) 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) if(OperatorValue(holder)=5)Pop(OpHolder);elsePush(holder,OpHolder);else if(OperatorValue(holder) = 6) Push(holder,OpHolder);else if(OperatorValue(holder) = 5) 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(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),Temp); Pop(OpHolder);Push(holder,OpHolder);else if(OperatorValue(Top(OpHolder) >= 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) < OperatorValue(holder) Push(holder,OpHolder);holder=getc(In); /* While循环结束*/while(IsEmpty(OpHolder)!=1) Push('B',Whereat);putc(' ',Temp);putc(Top(OpHolder),Temp);Pop(OpHolder);MakeEmpty(OpHolder); free(OpHolder);int IsOperator(char ToCompare)if (ToCompare = '(' | ToCompare = ')'| ToCompare = '+' | ToCompare = '-' | ToCompare = '*'| ToCompare = '/' | ToCompare = ''| ToCompare = '%')return 1;else if (ToCompare = '1' | ToCompare = '2'| ToCompare = '3' | ToCompare = '4' | ToCompare = '5'| ToCompare = '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 (ValueToGive = '')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 *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) 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)|(NumA<0) && (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; FPush(answer,Operands);break;case '*': NumB = FTop(Operands);FPop(Operands);if (FIsEmpty(Operands)PrintError = 1;elseNumA = FTop(Operands);FPop(Operands);answer = NumA * NumB; 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; 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);