数据结构之表达式求值课程设计（源代码 报告）.doc

表达式求值 一 目的 通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。 二 需求分析 此次课程设计的目标是能够设计一个程序，演示算术表达式求值的过程。 ①输入的形式和输入值的范围：以字符串的形式输入表达式，以换行符结束； ②输出的形式：在计算过程中遇到的问题或最终的答案将回显到屏幕上，同时所计算的表达式和最终的显示也将保存至文件中； ③程序所能达到的功能：能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理负数与小数，判断表达式是否语法正确（包含分母不能为零的情况），正确实现对算术四则混合运算表达式的求值，能够将计算中遇到的问题和结果以文件的形式予以存储； ④初步的测试计划：当输入正确表达式时，以换行符结束，能得到最终的正确结果；当输入含有非正常符号的错误表达式时，以换行符结束，能得到最终的提示语句；当遇到分数为0的轻快是，能得到提示语句。 三 概要设计 1、本程序中用到的数据类型 该设计主要运用的是栈的知识。为实现表达式求值的功能，需分别定义数字栈与符号栈。其结构体定义如下： typedef struct tagstack1{ /*数据栈*/ double* base; /*栈底指针*/ int top; /*栈顶*/ int len; /*栈的容量*/ }STACK1; typedef struct tagstack2{ /*符号栈*/ char* base; /*栈底指针*/ int top; /*栈顶*/ int len; /*栈的容量*/ }STACK2; 为了便于标记程序运行的正确与否，为了便于文件指针的应用，该程序定义了两个全局变量，如下： int wr=0; /*wr用于标记是否出错*/ FILE* fp; /*指向文件的指针*/ 2、程序的简单流程与主要函数 该设计主要在主函数中通过while循环来多次调用对一个表达式的处理函数ss（）；函数ss（）调用了多个函数来实现对一个表达式的处理功能，其中，主要的函数如下： char DealNbr(STACK1* S,char a,char* * pstr,int *i) /* 若字符a是数字字符，则从字符串*pstr中继续读取字符，将数字整体的读出后，进行处理，并将最后的数字如数字栈S */ char Compare(char a,char b) /* 比较两字符的优先级，若a较高则返回字符，相同则返回=，较低则返回 */ double calculate(double a,double b,char c) /* 计算数字a与数字b经运算符c计算后的结果，并返回 */ int change(char c) /* 获得符号c的优先级 */ void Init1(STACK1 * S) /* 初始化数据栈S */ void Full1(STACK1 *S) /* 判断栈是否已满 若满 则追加空间*/ int Empty1(STACK1 S) /*判断栈是否为空 若为空 则返回真值*/ void Push1(STACK1 *S,double e) /*数据e入栈*/ void Pop1(STACK1 *S,double* e) /*数据出栈 用e返回*/ double GetTop1(STACK1 S) /*返回栈顶数据*/ 符号栈的有关符号与数字栈相似，不重复记录。 3、函数之间的调用关系 main( ) -ss( ); ss( ) -DealNbr( ); Compare( ); calculate( ); change( ); Init1( ); Push1( ); Empty1( ); Pop1( ); GetTop1( );等一系列栈的函数 四 详细设计 1、Init1(STACK1 * S)： void Init1(STACK1 * S){ /*初始化数据栈*/ (*S).len=StackSize; (*S).base=(double *)malloc(sizeof(double)*StackSize); if(!(*S).base){ wr=1; printf(\n\nSpace!!); fprintf(fp,Space!!\n\n); return; }(*S).top=-1; } 令栈初始容量为StackSize，并为栈底指针分配相应空间。若未分配成功，则标记出错