数据结构课程设计
设计说明书
算术表达式求值问题
学生姓名白子健
学号1318014057 班级计本1302 成绩
指导教师李军
计算机科学与技术系
2015年9月10日
数据结构课程设计评阅书
课程设计任务书
2015—2016学年第一学期
专业：计算机科学与技术学号：1318014057 姓名：白子健
课程设计名称：课程设计Ⅰ---数据结构课程设计
设计题目：表达式求值算法的实现
完成期限：自2015 年9 月 1 日至2015 年9 月12 日共 2 周
设计内容及要求:
算术表达式求值是程序设计语言编译中的一个基本问题，通过栈实现表达式运算优先级的匹配和运算。用C/C++语言编程实现任意算术表达式的求值，设计内容要求如下：（1）表达式共有三种基本表示方法：前缀法、中缀法、后缀法。从表达式的这三种基本方法中任选一种方法进行编程求值。
（2）分析所选的表示方法，根据选定的表示方法确定对应的存储结构和相关算法。
（3）算法要能正确处理算术运算的优先级规则，即: 先括号内，后括号外的规则；运算先乘除，后加减；同级运算从左到右。
如下表达式：
50+（6*3+2）
要求：
(1)用C/C++语言编写一个程序将这组学生成绩输入到计算机中，数据运算的存储
逻辑结构为栈。
(2)程序要能正确处理表达式的优先级、输出正确运算结果。
最终设计成果形式为：
1、设计好的软件一套；
2、撰写一份课程设计说明书一份，打印并装订成册。
指导教师（签字）：教研室主任（签字）：
批准日期：年月日
目录
1 课题描述 (1)
2 设计思路 (2)
3 算法设计 (3)
4 程序代码 (5)
5 测试及分析 (12)
6 总结 (13)
参考文献 (13)
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之间的优先关系至多是下面三种关系之一：opt1 opt1=opt2，即opt1的优先级等于opt2； opt1>opt2，即opt1的优先级高于opt2。 表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();} //不是运算符则进栈； else{ switch (Precede(GetTop(OPTR), c)){ case ‘<’://栈顶元素优先级低 Push(OPTR, c); c = getchar(); break; case ‘=’://脱括号并接收下一字符 Pop(OPTR, x); c = getchar(); break; case ‘>’://退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b)); break; }//switch }//while Return 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 ERROR 0 #define INFEASIBLE -1 #define OK 1 #define TRUE 1 #define FALSE 0 #define OPERAND double #define OPERATOR char #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define MAX_QUEUE_SIZE 100 #define OPERATORNUM 8 //操作符的数量 typedef struct{ /*定义操作数栈*/ OPERAND * base; OPERAND * top; int iStackSize; }OPNDStack, *pOPNDStack; typedef struct{ /*定义运算符栈*/ OPERATOR * base; OPERATOR * top; int iStackSize; }OPTRStack, *pOPTRStack; char cOpt[] = {'+', '-', '*', '/', '(', ')', '#', '.'}; char cPriority[7][7] = { {'>', '>', '<', '<', '<', '>', '>'}, {'>', '>', '<', '<', '<', '>', '>'}, {'>', '>', '>', '>', '<', '>', '>'}, {'>', '>', '>', '>', '<', '>', '>'}, {'<', '<', '<', '<', '<', '=', NULL}, {'>', '>', '>', '>', NULL, '>', '>'}, {'<', '<', '<', '<', '<', NULL, '='} }; int InitOPNDStack(pOPNDStack S); OPERAND GetOPNDTop(pOPNDStack S); int PushOPND(pOPNDStack, OPERAND e); int PopOPND(pOPNDStack S, OPERAND * e); int InitOPTRStack(pOPTRStack S); OPERATOR GetOPTRTop(pOPTRStack S); int PushOPTR(pOPTRStack S, OPERATOR e); int PopOPTR(pOPTRStack S, OPERA TOR * e); OPERAND Operate(OPERAND fOperandA, OPERATOR cOperator, OPERAND fOperandB); OPERAND EvaluateExpression(char * Expression); int WhichOptNum(char opt); int IsOpt(char opt); int CheckExpression(char *Expression); int main(void){ //表达式求值——算符优先算法 OPERAND e = 0.0; char Expression[50] = " "; system("color f0"); while(OK) { fflush(stdin); printf("输入表达式："); gets(Expression); strcat(Expression, "#"); //printf("%s", cPriority); if (CheckExpression(Expression)){ e = EvaluateExpression(Expression); printf("Answer = %f\n", e); } else{ printf("输入中缀表达式有误！\n"); continue; } } return 0; }//main int InitOPNDStack(pOPNDStack S){ //构造一个空栈，栈内数据类型为OPND（浮点数据） S->base = (OPERAND *)malloc(STACK_INIT_SIZE * sizeof(OPERAND)); if (!S->base) exit(OVERFLOW); //这么写错误处理显然还不成熟S->top = S->base; S->iStackSize = STACK_INIT_SIZE; return OK; }//InitOPNDStack OPERAND GetOPNDTop(pOPNDStack S){ //读取栈顶元素，不删除栈顶元素 if (S->top == S->base) exit(OVERFLOW);//栈空 return *(S->top - 1); }//GetOPNDTop int 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 Debuging printf("增加OPND空间辣！\n"); system("pause"); #endif }//if *(S->top++) = e; return OK; }//PushOPND int PopOPND(pOPNDStack S, OPERAND * e){ //若栈不空，删除S栈顶元素，并用e返回其值 if (S->top == S->base) return ERROR; *e = *(--S->top); return OK; }//PopOPND int InitOPTRStack(pOPTRStack S){ //构造一个空栈，栈内数据类型为OPTR S->base = (OPERATOR *)malloc(STACK_INIT_SIZE * sizeof(OPERATOR)); if (!S->base) exit(OVERFLOW); //这么写错误处理显然还不成熟 S->top = S->base; S->iStackSize = STACK_INIT_SIZE; return OK; }//InitOPTRStack OPERATOR 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(OPERA TOR)); if (!S->base) exit(OVERFLOW); //空间不够 S->top = S->base + S->iStackSize; S->iStackSize += STACKINCREMENT; #if Debuging printf("增加OPTR空间辣！\n"); system("pause"); #endif }//if *(S->top++) = e; return OK; }//PshOPTR int PopOPTR(pOPTRStack S, OPERA TOR * e){ //若栈不空，删除S栈顶元素，并用e返回其值 if (S->top == S->base) return ERROR; *e = *(--S->top); return OK; }//PopOPTR OPERAND 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; }//Operate } OPERAND 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 = Expression[i++]; while(c != '#' || GetOPTRTop(&OptStack) != '#'){ if (!IsOpt(c)){ fTmp = 0.0; iTmp = c-'0'; c = Expression[i++]; while(!IsOpt(c)){ iTmp = iTmp * 10 + c-'0'; c = Expression[i++]; } if (c == '.'){ c = Expression[i++]; for (j = 0.1; !IsOpt(c); j *= 0.1){ fTmp += j * (c - '0'); c = Expression[i++]; } } //这里不需要了else tmp = iTmp + fTmp; PushOPND(&NumStack, tmp); } else switch (cPriority[WhichOptNum(GetOPTRTop(&OptStack))][WhichOptNum(c)]) { case '<': PushOPTR(&OptStack, c); c = Expression[i++]; break; case '=': PopOPTR(&OptStack, &c); //脱括号接收下一字符 c = Expression[i++]; break; case '>': PopOPTR(&OptStack, &opt); PopOPND(&NumStack, &fOperandB); PopOPND(&NumStack, &fOperandA); PushOPND(&NumStack, Operate(fOperandA, opt, fOperandB)); break; }//switch } tmp = GetOPNDTop(&NumStack); free(NumStack.base); free(OptStack.base); return tmp; }//EvaluateExpression int WhichOptNum(char opt){ //检测操作符所在的位置 int i = 0; for (i = 0; i if (cOpt[i] == opt){ return i; } } }//WhichOptNum int IsOpt(char opt){ //判断是不是操作符 int i = 0; for (i = 0; i if (opt == cOpt[i]) return TRUE; } return ERROR; }//IsOpt int CheckExpression(char *Expression){ //检查输入的合法性，合法返回1，否则返回0； int i = 0; while (Expression[i]){ if ((Expression[i] >= '0' && Expression[i] <= '9') || IsOpt(Expression[i])){ if (IsOpt(Expression[i])&&IsOpt(Expression[i+1]) \ &&(Expression[i]!=')'&&Expression[i+1]!='(')) return 0; else{ ++i; continue; } } else{ return 0; } } if (!Expression[i]) return 1; }//CheckExpression 5 测试及分析 在数据范围不溢出的情况下本设计仅可能出现两种情况：（1）输入正确的中缀表达式，输出正确的计算结果。 （2）输入错误的中缀表达式，报告输入错误并要求重新输入。 从实验的输入和输出来看，本程序实现了： （1）对正确的中缀表达式求值； （2）对输入错误的中缀表达式提示错误并放弃计算。 6 总结 本次课程设计使用Ｃ语言为编程语言，用数据结构——栈，实现了对字符串形式的算术表达式的求值。在本次课程设计中，涉及到对字符串输入字符进行解释分离和对栈存储结构的相关操作。在对字符串中的数据进行操作时，要区分操作的对象是操作符还是操作数，并且操作数要能存储浮点型数据，这在编程实现时要尤其注意。在对栈进行操作的时候，要注意对栈满、栈空的处理，对于栈满的情况下的入栈操作要能追加新空间从而存入新的数据。在书写课程设计说明书时，暴露了我书写文档能力弱的缺点，本次课程设计锻炼了我书写技术文档的能力和描述项目的能力。 参考文献 [1] 严蔚敏、吴伟民《数据结构 C语言版》清华大学出版社 数理学院 课程设计报告书 课程名称数据结构课程设计 设计题目算术表达式求值演示 专业班级 学号 姓名 指导教师 2014 年12 月 4.2.2 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S 已存在。 操作结 果： 用P 返回S的栈顶元素。Push(&S 初始条 件：，ch) 栈S 已存在。 操作结 果：插入元素ch 为新的栈顶元素。 Pop(&S) 初始条件：栈S 已存在。 操作结 果：删除S 的栈顶元素。 In(ch) 操作结果：判断字符是否是运算符，运算符即返回1 Precede(c1, c2) 初始条件：c1,c2 为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b) 初始条件：a,b 为整数，op为运算符。操作结果： a 与 b 进行运算，op 为运算符，返回其值。num(n) 操作结果：返回操作数的长度。EvalExpr() 初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADT Stack 主程序的流程： EvaluateExpression() 函数实现了对表达式求值的功能，main() 函数直接调用EvaluateExpression() 对输入的表达式求值输出。 4.2.3 函数的调用关系图 4.3 详细设计 4.3.1 ① . Precede(char c1,char c2)判断运算符优先权，返回优先权高的 算符间的优先关系 如下： 算法伪代码如下： char Precede(char c1,char c2) { static char array[49]={ >', '>', '<', '<', '<', '>', '>', >', '>', '<', '<', '<', '>', '>', >', '>', '>', '>', '<', '>', '>', >', '>', '>', '>', '<', '>', '>', <', '<', '<', '<', '<', '=', '!', >', '>', '>', '>', '!', '>', '>', <', '<', '<', '<', '<', '!', '='}; // 用一维数组存储 49 种情况 switch(c1) { /* i 为下面 array 的横标 */ case '+' : i=0;break; case '-' : i=1;break; case '*' : i=2;break; XXXXXX大学《数据结构》课程设计报告 班级： 学号： 姓名： 指导老师： 目录 一算术表达式求值 一、需求分析 二、程序的主要功能 三、程序运行平台 四、数据结构 五、算法及时间复杂度 六、测试用例 七、程序源代码 二感想体会与总结 算术表达式求值 一、需求分析 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 二、程序的主要功能 （1）从键盘读入一个合法的算术表达式，输出正确的结果。 （2）显示输入序列和栈的变化过程。 三、程序运行平台 Visual C++ 6.0版本 四、数据结构 本程序的数据结构为栈。 （1）运算符栈部分： struct SqStack //定义栈 { char *base; //栈底指针 char *top; //栈顶指针 int stacksize; //栈的长度 }; int InitStack (SqStack &s) //建立一个空栈S { if (!(s.base = (char *)malloc(50 * sizeof(char)))) exit(0); s.top=s.base; s.stacksize=50; return OK; } char GetTop(SqStack s,char &e) //运算符取栈顶元素 { if (s.top==s.base) //栈为空的时候返回ERROR { printf("运算符栈为空!\n"); return ERROR; } else e=*(s.top-1); //栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OK 一、设计思想 首先，将中缀表达式转换为后缀表达式。转换算法思路：设中缀表达式已存入数组E[n]；由于后缀表达式中操作数的次序与中缀表达式一致，故扫描到中缀表达式操作数时直接输出到B[n]即可；对于运算符，视其优先级别，优先级高的运算符先输出；设一存放运算符的栈s，先将s置空；依次扫描E[n]中各分量E[i]送x： 若x=“”（结束符），依次输出栈s中运算符，转换结束； 若x=操作数，直接输出x到B[n]中； 若x=‘）’，反复退栈输出栈s中子表达式运算符，直到栈顶符=‘（’，并退掉栈顶的‘（’； 若x=操作符，反复退栈输出栈s中运算符，直到栈顶符 三、源代码 下面给出的是用后缀表达式求值算法实现的程序的源代码： #include 竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告 篇一：数据结构实验二——算术表达式求值实验报告 《数据结构与数据库》 实验报告 实验题目算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系pb0920603 姓学 邮名：李维谷号：pb09206285箱： liwg@https://www.doczj.com/doc/037730366.html,指导教师：贾伯琪 实验时间：20XX年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个(:数据结构表达式求值实验报告)算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 用栈进行表达式求值并输出逆波兰式（源代 码） #include "stdio.h" #include "malloc.h" #include "string.h" #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ char *top,*base; int csize; }*charstack,cstack; typedef struct{ float *top,*base; int fsize; }*floatstack,fstack; charstack initcharstack(){ charstack s; s=(charstack)malloc(sizeof(cstack)); s->base=s->top=(char*)malloc(STACK_INIT_SIZE * sizeof(char)); s->csize=STACK_INIT_SIZE; return s; } floatstack initfloatstack(){ floatstack s; s=(floatstack)malloc(sizeof(fstack)); s->base=s->top=(float*)malloc(STACK_INIT_SIZE * sizeof(float)); *(s->top)=-1; s->fsize=STACK_INIT_SIZE; return s; } char chargettop(charstack s){ return *(s->top-1); } float floatgettop(floatstack s){ return *(s->top-1); } void charpush(charstack s,char c){ if((s->top-s->base)>=s->csize){ s->base =(char *)realloc(s->base ,(s->csize +STACKINCREMENT)*sizeof(char)); s->top=s->base +s->csize ; s->csize +=STACKINCREMENT; } 数据结构课程设计 设计说明书 算术表达式求值问题 学生姓名白子健 学号1318014057 班级计本1302 成绩 指导教师李军 计算机科学与技术系 2015年9月10日 数据结构课程设计评阅书 课程设计任务书 2015—2016学年第一学期 专业：计算机科学与技术学号：1318014057 姓名：白子健 课程设计名称：课程设计Ⅰ---数据结构课程设计 设计题目：表达式求值算法的实现 完成期限：自2015 年9 月 1 日至2015 年9 月12 日共 2 周 设计内容及要求: 算术表达式求值是程序设计语言编译中的一个基本问题，通过栈实现表达式运算优先级的匹配和运算。用C/C++语言编程实现任意算术表达式的求值，设计内容要求如下：（1）表达式共有三种基本表示方法：前缀法、中缀法、后缀法。从表达式的这三种基本方法中任选一种方法进行编程求值。 （2）分析所选的表示方法，根据选定的表示方法确定对应的存储结构和相关算法。 （3）算法要能正确处理算术运算的优先级规则，即: 先括号内，后括号外的规则；运算先乘除，后加减；同级运算从左到右。 如下表达式： 50+（6*3+2） 要求： (1)用C/C++语言编写一个程序将这组学生成绩输入到计算机中，数据运算的存储 逻辑结构为栈。 (2)程序要能正确处理表达式的优先级、输出正确运算结果。 最终设计成果形式为： 1、设计好的软件一套； 2、撰写一份课程设计说明书一份，打印并装订成册。 指导教师（签字）：教研室主任（签字）： 批准日期：年月日 目录 1 课题描述 (1) 2 设计思路 (2) 3 算法设计 (3) 4 程序代码 (5) 5 测试及分析 (12) 6 总结 (13) 参考文献 (13) 逆波兰表达式求值 一、需求分析 1、从键盘中输入一个后缀表达式，该表示包括加减乘除等操作符，以及正整数作为操 作数等。 2、用堆栈来实现 3、测试数据 输入：2 3 * 1 – # 输出：2 3 * 1 -- =5 二、概要设计 抽象数据类型 需要一个浮点数栈来存储还没有计算的浮点数或者运算的结果。 ADT Stack 数据成员：int size; int top; //分别用于存储栈大小、栈顶位置 float *listArray;//存储浮点型数字的数组 成员函数： bool push(float it); bool pop(float& it); bool isEmpty(); //判断栈为空 bool isOne();//判断栈是否只有一个元素 算法的基本思想 1.逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+str[i]-48 将数据由字符类型转换为浮点型数据； 2.如果字符是‘.’，则将‘.’转化为小数点，并将‘.’后的数据转化为小数部分； 3.遇到空格前是数据的，将x押入栈； 4.如果该字符是’+’，’-’，’*’或’/’，判断栈里的元素是否少于两个个，如果少于两个， 报错；如果大于等于两个，就弹出两个数据，并进行相应的计算； 程序的流程 输入字符串，程序对字符串依次扫描。扫描一位，处理一位。扫描完成后，判断栈里是不是只有一个数据，若是，得到正确结果；若不是，则表达式出错。 三、详细设计 物理数据类型 用浮点数类型的栈存储运算中要用的数据，需要入栈、出栈，故设计如下的浮点类型的栈： class Stack { private: int size; int top; float *listArray; public: Stack(int sz=20); ~Stack(); 表达式求值课程设计报告 表达式求值 《数据结构》 课程设计报告 题目: 栈的应用:表达式求值 (系): 信息科学与工程学院院 专业班级: 软件工程1102班学生姓名: 学号: 指导教师: 20 13 年 6 月 8 日至20 13 年 6 月 21 日 表达式求值 目录 目录 (2) 1 概述 (1) 1.1 课程设计目的 (1) 1.2 课程设计内容 (1) 2 系统需求分析 ...................................................... 1 2.1 系统目标 (1) 2.2 主体功能 (1) 2.3 开发环境 (1) 3 系统概要设计 .................................................... 2 3.1 系统的功能模块划分 (2) 3.2 系统流程图 (2) 4系统详细设计 ..................................................... 3 5 测试 ............................................................ 6 5.1 测试方案 (6) 5.2 测试结果 (6) 6 小结 ............................................................ 8 参考文献 .......................................................... 9 附录1 源程序清单 (10) 2 数据结构课程设计报告(2012) 表达式求值 1 概述 1.1 课程设计目的 1(要求学生达到熟练掌握C语言的基本知识和技能。 2(了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。 3(提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 4(培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提 高程序设计水平。 一、设计思想 计算算数表达式并求值，采取的共有两种方法： 1.先将算数表达式转化为后缀表达式，然后对后缀表达式进行计算。 2.对算数表达式进行直接的计算。 第一种算法 这种解决方案又分为两步： 1.将表达式先转化为后缀表达式的字符串数组 2.利用后缀表达式进行计算 在转化过程中，第一，建立一个存符号的栈，和一个字符串数组，用来存放转化以后的表达式 然后，对于得到的用户输入的字符串进行逐个的扫描，如果是数组或者小数点，则直接存放到数组中，并且在后面加入一个分隔符，如果是操作符，则和栈中的已存的进行比较，如果比栈中的操作符的优先级高，则直接入栈，如果优先级低或相等，则栈中元素出栈，存到字符串中，然后再次检查栈顶，直到栈中元素的优先级低于扫描操作符，则此操作符入栈，然后扫描下一个字符，直到遇到字符串的结束符号\0，扫描结束。数组中存的就是后缀表达式。得到后缀表达式后，进行计算，要用到数值栈。首先要将字符表示的数字转化为浮点小数，然后进行扫描，遇到数值，放入栈中，遇到操作符，就从栈中取出两个数，进行计算后再放入栈中，扫描下一个，最后的计算结果就存到了栈中，直接取出栈内元素，就是计算的最后结果。 第二种算发 首先要建立两个栈，一个用来存放操作符，一个用来存放数值。开始对用户输入的字符串进行扫描，如果是数字字符或者小数点，则将字符转化为浮点数存到数栈里，如果是操作符，则观察符号栈，如果栈顶元素的优先级低于观察的操作符，则操作符入栈，如果栈顶元素的优先级高于或者等于观察的操作符，则从数值栈中取出两个浮点数，从符号栈中取出栈顶的操作符，然后进行相应的数值计算，所得的结果再存到数值栈中，重复这样的操作，直到符号栈中栈顶元素的优先级低于观察的操作符，则此操作符入栈，然后对下一个字符进行扫描。如果是左括号，则不进行优先级的比较，直接入栈，入栈后优先级为-1。如果是右括号，则从数值栈中取两个操作数，符号栈中取出一个符号，然后进行计算后得数放入数栈中，不断进行此类操作，直到从栈中取出的是左括号为止，左括号去掉，扫描下一个。扫描结束后，计算也结束了，计算的结果就存放在数值栈中，最后把数值栈中的数取出，就是所得的计算结果。 容错的算法简要： 括号匹配：当扫描到左括号是，左括号直接入栈，扫描到右括号时，则左括号出栈，如果栈为空，则右括号多，如果最后栈中还有括号，则左括号多。给出错误提示。 除数不为0：当扫描到'/'时，就判断其后面的数字是否为0，如果为0报错。 取余运算：取余运算时，操作数判断是否为整数，不为整数报错。 二、算法流程图 第一种算法:先将表达式转化为后缀表达式，然后计算 其主函数流程图为： 实验3四则运算表达式求值 背景 在工资管理软件中，不可避免的要用到公式的定义及求值等问题。对于数学表达式的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀表达式转换为逆波兰表达式，这样更容易处理。 问题描述 四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。 基本要求 使用二叉树来实现。 实现提示 利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。 输入输出格式： 输入：在字符界面上输入一个中缀表达式，回车表示结束。 输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。 选作内容 （1）在输入输出方式上要求使用： 输入：将中缀表达式存于文本文件中，程序从该文本文件中读出表达式。 输出：如果该中缀表达式正确，则将后缀表达式输出到该文件中原表达式的后面，它们之间用“---”后相连；如果不正确，请在输出表达式错误提示到该文件原表达式的后面，它们之间用“---”相连。 (2) 利用堆栈来实现中缀表达式转换为后缀表达式。 测试用例 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 程序代码： #include 源代码： //用来存储字符的结点类型 typedef struct CharNode { char c; struct CharNode *next; }CharNode; //用来存储数的结点类型 typedef struct IntNode { long double i; struct IntNode *next; }IntNode; //用来存储数的结点类型 typedef struct Node { long double n; struct Node_ys_char *next; }Node; //用来存储运算符的结点类型 typedef struct Node_ys_char { char c; struct Node_ys_char *next_c; struct Node *next; }Node_ys_char; char Precede(char x,char y)//运算符优先级判断{ int i,j; int from[5][5] ={ {0,0,-1,-1,0}, {0,0,-1,-1,0}, {1,1,0,0,1}, {1,1,0,0,1}, {0,0,-1,-1,0} };//定义一个二维数组存放算术符号的优先级 switch(x) { case '+':i=0;break; case '-':i=1;break; case '*':i=2;break; case '/':i=3;break; case '#':i=4;break; } switch(y) { case '+':j=0;break; case '-':j=1;break; case '*':j=2;break; case '/':j=3;break; case '#':j=4;break; } if(from[i][j]==1)//说明运算符i的优先级比j的优先级高return '>'; if(from[i][j]==-1) return '<'; else return '='; } //输入表达式，并对特殊情况做处理 CharNode *CreatRegister() { CharNode *top,*p,*q,*e; top=(CharNode *)malloc(sizeof(CharNode)); p=q=top; scanf("%c",&p->c); scanf("%c",&p->c); 实验表达式求值问题 1.问题描述 表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3.中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀表达式（如：11 22 7 4 - * 3 / +）和前缀表达式（+ 11 / * 22 - 7 4 3）。后缀表达式 和前缀表达式中没有括号，给计算带来方便。如后缀表达式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。 2.数据结构设计 （1）顺序栈类定义：首先应在类中定义成员函数，以此来完成顺序栈的相关操作，如下： class SqStack { private: T *base; //栈底指针 int top; //栈顶 int stacksize; //栈容量public: SqStack(int m); //构建函数 ~SqStack(){delete [] base;top=0;stacksize=0;} //析构函数 void Push(T x); //入栈 T Pop(); //出栈 T GetTop(); //获取栈顶元素 int StackEmpty(); //测栈空 void ClearStack(); //清空栈 void StackTop(); //返回栈顶指针 void StackTranverse(); //显示栈中元素 }; （2）顺序栈类实现：对顺序栈进行初始化，初始化的首要操作就是创建一个空顺序栈。 Step1：申请一组连续的存空间为顺序栈使用： base=new T[m]; i f(base==NULL) { cout<<"栈创建失败，退出!"< #include 表达式求值 一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题 目，利用C/C++语言进行程序设计，并规地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描 述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果 二需求分析 设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果。对于这个程序我们从输入，输出，和功能三方面来分析。 1.程序输入：从键盘上输入表达式，一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量）。为了简化，操作数只能为浮点数，操作符为“ +”、“-”、“*”、“/”、“（”、“）”，用“#“表示结束。 2.程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程，如运算符栈、运算数栈的出入记录，字符出入栈的过程，打印出完整的过程。 3.功能要求及说明：从键盘上输入表达式。分析该表达式是否合法（包含分母不能为零的情况）： （1）是数字，则判断该数字的合法性。 （2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 （3）若是其它字符，则返回错误信息。 若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。 三概要设计 1.数据结构的选择： 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。 课程设计 教学院 课程名称 题目 专业 班级 姓名 同组人员 指导教师 2013 年 6 月22 日 (完成时间) 目录 一．概述 (2) 二．总体方案设计 (4) 三．详细设计 (6) 四．程序的调试与运行结果说明 (14) 五．课程设计总结 (14) 六．附录 (16) 参考文献 (3233) （“目录”要求必须自动生成） 一概述（宋体，三号，加粗，居中） 1.课程设计的目的（小标题，宋体，四号，加粗，左对齐顶格） （1）．理解和掌握该课程中的有关基本概念，程序设计思想和方法。 （2）．培养综合运用所学知识独立完成课题的能力。 （3）．培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。 （4）．掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。 2.课程设计的要求 算术表达式求值程序实现以下功能： (1)构造一个空栈S,初始条件：栈S已存在 (2)用P返回S的栈顶元素 (3)插入元素ch为新的栈顶元素 (4)删除S的栈顶元素 (5)判断字符是否是运算符，运算符即返回1 (6)判断运算符优先权，返回优先权高的 (7)输入表达式 (8)返回表达式的最终结果。 二总体方案设计 a)需求分析 该程序能实现算术四则运算表达式的求值，显示运算过程。 输入的形式：表达式，例如5*（3+7）#。 包含的运算符只能有'+'、 '-'、'*'、 '/'、 ' (' ') '； 程序所能达到的功能：对表达式求值并输出。 b)总体设计 本程序使用的是编程工具是Visual c++ 6.0，实现了运算器的功能和仿真界面（大体界面如下图所示）。在基本要求的基础上，运算数可以是实数类型，同时增加了乘方运算的功能；可以实现对负数的运算，例如用户输入表达式6* （-0.25）,则程序会在负号的前面自动加上一个0。 1)算符包括加（+）、减（-）、乘（*）、除（/）、乘方（^）；另一个称作 OPND，用以寄存操作数和运算结果，操作数可以是float型的浮点数。 算法的基本思想是： 2)首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素； 依次读入表达式中的每个字符，若是操作数（浮点数）则进OPND栈， 若是运算符（+、—、*、/、^）则和OPTR栈的栈顶运算符比较优先权 后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当 前读入的字符均为“#”）。 3)编写一个原型为void strtofloat(char str[ ],int n,int i)，把一 个数字串转换为一个实型数，并压入运算数栈中。（整个程序的源代码 见附录，并有具体解释） #include 汇编语言实训课程设计任务书 题目：表达式求值程序班级：计算机科学与技术一班 学生姓名：赵旭尧学号： 14730141 题目类型：软件工程（R）指导教师：刘树群 一．题目简介 该设计要求学生使用汇编语言，设计并开发出针对四则运算表达式进行求 值的命令行或窗口程序。 通过该题目的设计过程，可以培养学生结构化程序设计的思想，加深对汇 编语言基本语言要素和流程结构的理解，针对汇编语言中的重点和难点内容进 行训练，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格。 得到软件工程的综合训练，提高解决实际问题的能力。 二．设计任务 1、查阅文献资料，一般在5篇以上； 2、通过键盘输入表达式，进行针对整数的“加减乘除”四则运算表达式 进行求值，有良好的界面； 3、完成软件结构设计和算法设计； 4、完成系统的软件开发和测试工作； 5、撰写设计说明书； 6、做好答辩工作。 三．主要内容、功能及技术指标 1、实现功能及指标：①使用Win32的窗口程序模式，实现表达式求值程序 及测试界面程序的设计与开发；②支持整数的四则运算、位运算和小括号等； ③使用文本框对表达式进行交互式编辑和输出。 2、问题分析及解决方案框架确定：充分地分析和理解问题本身，弄清要求 做什么。在确定解决方案框架过程中，综合考虑系统功能，考虑怎样使系统结 构清晰、合理、简单和易于调试。最后确定每个过程和函数的简单功能，以及 过程（或函数）之间的调用关系，并画出函数之间的调用关系图。 3、详细设计和编码：定义相应的存储结构，确定各个函数的算法，并画出 流程图，在此基础上进行代码设计，每个明确的功能模块程序一般不超过200 行，否则要进一步划分。 目录 1．前言 (2) 2．问题描述 (3) 3．总体设计·····················································································错误！未定义书签。 3.1 概要设计 ······························································································错误！未定义书签。 3.1.1 数据结构的选择 (3) 3.1.2 相关功能函数 (3) 3.1.3 函数模块调用关系 (4) 3.2详细设计和编码 (5) 4．运行与测试 (9) 4.1 上机调试 (9) 4.2 算法时间和空间性能分析 (10) 4.3程序运行测试结果 (11) 5. 总结与心得 (13) 5.1设计中难点的总结以及其它解决方案 (13) 5.2 实验心得 (14) 6. 用户使用说明 (16) 7. 参考文献 (16) 8. 附录1（源代码清单） (16) 9. 附录2（成绩评定表） (25) 1 1.前言 课程设计是实践性教学中的一个重要环节，它以某一课程为基础，它可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。 在数据结构的学习和课程设计过程中，我发现它要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，都必须加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。对于我们专业来说，虽然说对技术要求不是特别高，但是在实际操作过程中，没有足够的专业知识对于编程来说是远远不可以达到要求的，所以对于这次的课程设计，我们必须要通过自己额外补充知识来完成它。 在这次的课程设计中我选择的题目是表达式的求值演示。它的基本要求是：以字符序列的形式从终端输入语法正确的，不含变量的表达式。利用算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。对于表示出栈在每执行一个过程中都要输出它的变化，这点我认为在编程中是比较困难的，以我自身的能力，是不可能在规定的时间内完成任务的，所以我参考了很多有价值的书籍来帮助我完成我的程序设计。 2 #include v.push_back(s[i]); v.push_back(' '); } else if (s[i] == '(') { stk.push(s[i]); } else if (s[i] == ')') { while(stk.top() != '(') { v.push_back(stk.top()); v.push_back(' '); stk.pop(); } stk.pop(); } else if (IsOperator(s[i])) { if (!stk.empty()) { while(!stk.empty() && priority(s[i]) <= priority(stk.top())) { v.push_back(stk.top()); v.push_back(' '); stk.pop(); } } stk.push(s[i]); } i++; } while(!stk.empty()) { v.push_back(stk.top()); v.push_back(' '); stk.pop(); } } bool compute(vector算术表达式求值演示程序
数据结构课程设计_表达式求值【完整版】[精品文档]
后缀表达式求值
数据结构表达式求值实验报告
用栈进行表达式求值并输出逆波兰式(源代码)
表达式求值课程设计
逆波兰表达式求值(实验报告及C 源码)
表达式求值课程设计报告
C语言 后缀表达式计算
四则运算实验报告
C语言_算术表达式求值_代码
数据结构课程设计_表达式求值问题
后缀表达式求值的算法及代码
数据结构课程设计：算术表达式
算术表达式求值课程设计报告
后缀表达式转化为前缀表达式并求值
表达式求值程序设计说明书
数据结构算术表达式求值课程设计
后缀表达式的计算
相关主题
文本预览