表达式求值课程设计.doc

数据结构课程设计设计说明书算术表达式求值问题学生姓名白子健学号1318014057班级计本1302成绩指导教师李军计算机科学与技术系2015年9月10日数据结构课程设计评阅书题 目算术表达式求值算法的实现学生姓名白子健学号1318014057指导教师评语及成绩成绩： 教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日课程设计任务书20152016学年第一学期专业： 计算机科学与技术 学号： 1318014057 姓名： 白子健 课程设计名称： 课程设计-数据结构课程设计 设 计 题 目： 表达式求值算法的实现 完 成 期 限：自 2015 年 9 月 1 日至 2015 年 9 月 12 日共 2 周设计内容及要求:算术表达式求值是程序设计语言编译中的一个基本问题，通过栈实现表达式运算优先级的匹配和运算。用C/C+语言编程实现任意算术表达式的求值，设计内容要求如下：（1）表达式共有三种基本表示方法：前缀法、中缀法、后缀法。从表达式的这三种基本方法中任选一种方法进行编程求值。（2）分析所选的表示方法，根据选定的表示方法确定对应的存储结构和相关算法。（3）算法要能正确处理算术运算的优先级规则，即: 先括号内，后括号外的规则；运算先乘除，后加减；同级运算从左到右。如下表达式：50+（6*3+2）要求：(1)用C/C+语言编写一个程序将这组学生成绩输入到计算机中，数据运算的存储逻辑结构为栈。(2)程序要能正确处理表达式的优先级、输出正确运算结果。最终设计成果形式为：1、 设计好的软件一套；2、 撰写一份课程设计说明书一份，打印并装订成册。指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日目 录1 课题描述12 设计思路23 算法设计34 程序代码55 测试及分析.126 总结.13参考文献.13第14页 1 课题描述表达式求值是程序设计语言编译中的一个最基本问题。表达式求值在计算机中的实现是栈结构在计算机中的一个典型应用。这里使用“算符优先算法”实现表达式求值。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。例如对表达式求值：50+（6*3+2）首先要了解算术四则运算的规则。即：先算括号内，后算括号外；先乘除后加减；同级运算顺序从左到右；所以，这个表达式的运算顺序为：50+（6*3+2）=50+（18+2）=50+20=70算符优先算法就是根据这个运算优先关系来编译或者解释执行的。2 设计思路2.1表达式的输入：表达式从键盘输入，存入字符串数组中。2.2运算的实现：任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。可以把运算符和界限符统称为算符，根据算术运算规则，在运算的每一步中，任意两个相继出现的算符opt1和opt2之间的优先关系至多是下面三种关系之一：opt1opt2，即opt1的优先级高于opt2。表1定义了算符间的优先关系： Opt2Opt1+-*/（）#+-*/（NULL#NULL=表1输入的表达式（包含运算符和操作数）以字符串的形式输入，故需要一个字符串数组存储键盘的输入。在对输入的表达式求值前，应先检查输入的合法性。只有正确的输入才能输出正确的计算结果。算符优先算法运算需要两个栈：操作数栈（OPND）和运算符栈（OPTR）。栈可以采用数组实现，并定义栈的相关操作：初始化、压栈、出栈、判断栈满、判断栈空等相关操作。输入的字符串解析分离出操作数和运算符，分别进入操作数栈和运算符栈。运算始终在栈顶实现，最终操作数栈只剩一个元素，即运算结果。3算法设计使用两个工作栈：一个称作OPTR，用以寄存运算符；另一个称作OPTD，用以寄存操作数或运算结果。算法的基本思想是：（1）置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2）依次读入表达式中的每个字符，若是操作数则进入OPND栈，若是运算符则和OPTR栈的栈顶元素比较优先级后进行相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前字符串读入的字符均为“#”）。算法如下：OperandType EvaluateExpression()/算术表达式求值的算符优先算法。OPTR和OPND分别为运算符栈和运算数栈/OP为运算符集合+、-、*、/、（、）、#、.InitStack(OPTR);Push(OPTR, #);InitStack(OPND);c = getchar();while (c!=# | GetTop(OPTR)!=#)if (!IsOpt(c)Push(OPND, c); c = getchar();/不是运算符则进栈；elseswitch (Precede(GetTop(OPTR), c)case :/退栈并将运算结果入栈Pop(OPTR, theta);Pop(OPND, b);Pop(OPND, a);Push(OPND, Operate(a, theta, b);break;/switch/whileReturn GetTop(OPND);/EvaluateExpression算法中还调用了两个函数。其中Precede是判定运算符栈的栈顶运算符opt1与读入的运算符opt2之间优先关系的函数；Operate为进行二元运算a opt b的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算的结果。程序流程图如下：4程序代码#if 0/*2015年9月8日09:10:14表达式求值算法算符优先算法的实现*/#endif#define Debuging 0/当值为一时，开启调试#include #include #include #define OVERFLOW-2#define ERROR0#define INFEASIBLE-1#define OK1#define TRUE1#define FALSE0#define OPERANDdouble#define OPERATOR char#define STACK_INIT_SIZE100#define STACKINCREMENT10#defineMAX_QUEUE_SIZE100#define OPERATORNUM 8/操作符的数量typedefstruct/*定义操作数栈*/OPERAND * base;OPERAND * top;int iStackSize;OPNDStack, *pOPNDStack;typedef struct/*定义运算符栈*/OPERATOR * base;OPERATOR * top;int iStackSize; OPTRStack, *pOPTRStack;char cOpt = +, -, *, /, (, ), #, .;char cPriority77 = , , , , , , , , , , , , , , , , , , , , , , , , , , , , NULL, , , , , , base = (OPERAND *)malloc(STACK_INIT_SIZE * sizeof(OPERAND);if (!S-base)exit(OVERFLOW);/这么写错误处理显然还不成熟S-top = S-base;S-iStackSize = STACK_INIT_SIZE;return OK;/InitOPNDStackOPERAND GetOPNDTop(pOPNDStack S)/读取栈顶元素，不删除栈顶元素if (S-top = S-base)exit(OVERFLOW);/栈空return *(S-top - 1);/GetOPNDTopint PushOPND(pOPNDStack S, OPERAND e)/将新的OPND元素入栈，栈满则增加空间if (S-top - S-base = S-iStackSize)S-base=(OPERAND*)realloc(S-base,(S-iStackSize+STACKINCREMENT)*sizeof(OPERAND);if (!S-base)exit(OVERFLOW);/空间不够了S-top = S-base + S-iStackSize;S-iStackSize += STACKINCREMENT;#if Debugingprintf(增加OPND空间辣！n);system(pause);#endif/if*(S-top+) = e;return OK;/PushOPNDint PopOPND(pOPNDStack S, OPERAND * e)/若栈不空，删除S栈顶元素，并用e返回其值if (S-top = S-base)return ERROR;*e = *(-S-top);return OK;/PopOPNDint InitOPTRStack(pOPTRStack S)/构造一个空栈，栈内数据类型为OPTRS-base = (OPERATOR *)malloc(STACK_INIT_SIZE * sizeof(OPERATOR);if (!S-base)exit(OVERFLOW);/这么写错误处理显然还不成熟S-top = S-base;S-iStackSize = STACK_INIT_SIZE;return OK;/InitOPTRStackOPERATOR GetOPTRTop(pOPTRStack S)/读取栈顶元素，不删除栈顶元素if (S-top = S-base)exit(OVERFLOW);/栈空return *(S-top - 1);/GetOPTRTop/哎。重复造轮子int PushOPTR(pOPTRStack S, OPERATOR e)/将新的OPTR元素入栈，栈满则增加空间if (S-top - S-base = S-iStackSize)S-base=(OPERATOR*)realloc(S-base,(S-iStackSize + STACKINCREMENT)*sizeof(OPERATOR);if (!S-base)exit(OVERFLOW);/空间不够S-top = S-base + S-iStackSize;S-iStackSize += STACKINCREMENT;#if Debugingprintf(增加OPTR空间辣！n);system(pause);#endif/if*(S-top+) = e;return OK;/PshOPTRint PopOPTR(pOPTRStack S, OPERATOR * e)/若栈不空，删除S栈顶元素，并用e返回其值if (S-top = S-base)return ERROR;*e = *(-S-top);return OK;/PopOPTROPERAND Operate(OPERAND fOperandA, OPERATOR cOperator, OPERAND fOperandB)/将操作数计算后返回switch (cOperator)case +:return (fOperandA + fOperandB);break;case -:return (fOperandA - fOperandB);break;case *:return (fOperandA * fOperandB);break;case /:return (fOperandA / fOperandB);break;default:printf(运算出了BUG。中彩蛋了。n);system(pause);return ERROR;/OperateOPERAND EvaluateExpression(char * Expression)/算符优先算法OPNDStack NumStack;OPTRStack OptStack;char c = ;int i = 0;OPERATOR opt = 0;OPERAND tmp = 0.0, fTmp = 0.0, iTmp, j = 0.0, fOperandB, fOperandA;InitOPNDStack(&NumStack);InitOPTRStack(&OptStack);PushOPTR(&OptStack, #);c = Expressioni+;while(c != # | GetOPTRTop(&OptStack) != #)if (!IsOpt(c)fTmp = 0.0;iTmp = c-0;c = Expressioni+;while(!IsOpt(c)iTmp = iTmp * 10 + c-0;c = Expressioni+;if (c = .)c = Expressioni+;for (j = 0.1; !IsOpt(c); j *= 0.1)fTmp += j * (c - 0);c = Expressioni+;/这里不需要了elsetmp = iTmp + fTmp;PushOPND(&NumStack, tmp);elseswitch (cPriorityWhichOptNum(GetOPTRTop(&OptStack)WhichOptNum(c)case :PopOPTR(&OptStack, &opt);PopOPND(&NumStack, &fOperandB);PopOPND(&NumStack, &fOperandA);PushOPND(&NumStack, Operate(fOperandA, opt, fOperandB);break;/switchtmp = GetOPNDTop(&NumStack);free(NumStack.base);free(OptStack.base);return tmp;/EvaluateExpressionint WhichOptNum(char opt)/检测操作符所在的位置int i = 0;for (i = 0; iOPERATORNUM; +i)if (cOpti = opt)return i;/WhichOptNumint IsOpt(char opt)/判断是不是操作符int i = 0;for (i = 0; i= 0 & Expressioni = 9) | IsOpt(Expressioni)if (IsOpt(Expressioni)&IsOpt(Expressioni+1)&(E