算法表达式语法检查(数据结构课程设计)

课程设计报告题目：算术表达式求值一、需求分析1、设计要求：给定一个算术表达式，通过程序求出最后的结果1>、从键盘输入要求解的算术表达式；2>、采用栈结构进行算术表达式的求解过程；3>、能够判断算术表达式正确与否；4>、对于错误表达式给出提示；5>、对于正确的表达式给出最后的结果；2、设计构想：为了实现算符优先算法使用两个工作栈，一个称作OPTR，以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。

在操作数和操作符入栈前，通过一个函数来判别，输入的是操作数还是操作符，操作数入OPND，操作符入OPTR。

在输入表达式的最后输入‘#’，设定‘#’的优先级最低，代表表达式输入结束。

在表达式输入过程中，遇操作数则直接入栈，遇到运算符则与栈顶运算符比较优先级,若当前运算符优先级高，则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符与新栈顶运算符。

如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。

二、概要设计1、本程序包含的模块：（1）栈模块——实现栈抽象数据类型（2）运算模块——实现数据表达式的运算（3）主程序模块三、详细设计（1）栈模块1、定义栈结构struct Sqstack{elemtype *top;//栈顶元素elemtype *base; //栈底元素int stacksize;//栈的大小};2、栈的基本操作①初始化栈status initstack(struct Sqstack &s){s.base=(elemtype *)malloc(stack_size*sizeof(elemtype)); if(!s.base)return OVERFLOW;s.top=s.base;s.stacksize=stack_size;return OK;}②入栈status push(struct Sqstack &s,elemtype e){if(s.top-s.base>=s.stacksize){s.base=(elemtype*)realloc(s.base,(s.stacksize+stack_increase ment)*sizeof(elemtype));if(!(s.base))return OVERFLOW;s.top=s.base+s.stacksize;s.stacksize+=stack_increasement;}* s.top++=e;return OK;}③出栈elemtype pop(struct Sqstack &s){elemtype e;if(s.top= =s.base)return ERROR;e=*--s.top;return e;}④取栈顶元素elemtype gettop(struct Sqstack &s){elemtype e;if(s.top==s.base)return ERROR;e=*(s.top-1);return e;}（2）运算模块1、判断输入字符c是否为操作符：若是，则返回1；否则，返回0int In(int c){char p[10]="+-*/()#^";int i=0;while(p[i]!='\0'){if(p[i]==c)return 1;i++;}return 0;}2、判断运算符的优先级char precede(char top,char c)//该函数为判断当前运算符与前一个运算符的优先级，前一个运算符高于或等于当前运算符的优先级则返回‘>’，前一个运算符小于当前运算符的优先级则返‘<’，当前一个运算符为‘（’当前运算符为‘）’时返回‘=’，用于去除表达式的括号。

算术表达式的求解-数据结构课程设计报告数据结构》课程设计报告书题目：算术表达式的求解系别：计算机科学与应用数据结构课程设计目录一、需求分析1、设计要求：本程序需要实现对算术表达式的求解功能，可以支持基本的四则运算，包括加、减、乘、除，同时还需要支持括号的使用。

2、设计构想：我们将使用栈来实现算术表达式的求解。

具体地，我们将把中缀表达式转换为后缀表达式，然后再利用栈来求解后缀表达式。

二、概要设计1、本程序包含的模块：本程序包含两个模块：中缀表达式转后缀表达式模块和后缀表达式求解模块。

三、详细设计1、定义栈结构我们定义一个栈结构，用来存储算术表达式中的运算符和操作数。

具体地，栈中的每个元素都包含两个属性：元素的值和元素的类型。

元素的值可以是一个数字或一个运算符，元素的类型可以是数字或运算符。

我们使用一个数组来实现栈的结构。

为了方便起见，我们还需要定义一些基本的栈操作，如入栈、出栈、判断栈是否为空等。

2、栈的基本操作栈是一种常见的数据结构，具有后进先出（LIFO）的特点。

栈的基本操作包括初始化栈、入栈、出栈、取栈顶元素和运算模块。

1) 初始化栈初始化栈是指将栈的各项属性设置为初始状态。

通常包括将栈顶指针设为-1，表示栈为空。

2) 入栈入栈是指将元素压入栈顶。

入栈操作需要将栈顶指针加1，并将元素存入栈顶位置。

3) 出栈出栈是指将栈顶元素弹出。

出栈操作需要将栈顶元素取出，并将栈顶指针减1.4) 取栈顶元素取栈顶元素是指获取栈顶元素的值，但不将其弹出。

取栈顶元素操作只需要返回栈顶元素的值即可。

5) 运算模块栈可以用于实现各种运算，例如中缀表达式的转换和计算、括号匹配等。

运算模块需要根据具体需求进行设计和实现。

3、判断运算符的优先级在进行中缀表达式的转换和计算时，需要判断运算符的优先级。

通常采用栈来实现这一功能。

具体实现方法是将运算符入栈，当遇到新的运算符时，将其与栈顶运算符进行比较，如果新运算符的优先级高于栈顶运算符，则将其入栈，否则将栈顶运算符弹出并输出，直到新运算符可以入栈为止。

算法分析与设计数据结构实践课程设计1. 课程简介本课程旨在让学生了解算法分析与设计的基本概念，理解数据结构的各种操作原理和实现方式，掌握基础的算法设计技巧和算法分析方法，并实践运用所学知识解决实际问题。

2. 课程设计要求2.1 实践项目本课程设计要求学生设计一个实践项目，项目内容可以是任何与数据结构相关的实际问题。

同时，要求学生采用所学的算法分析与设计方法，设计和实现一个高效、正确、可靠的解决方案，并进行评估和测试。

2.2 项目报告学生需要撰写一份详细的项目报告，内容包括但不限于：•项目背景和问题描述•解决方案设计思路和方法•程序实现细节和代码结构说明•性能测试和评估结果分析•可能的改进和优化建议2.3 课程答辩学生需要在课程结束前，进行项目答辩。

答辩内容包括但不限于：•项目背景和问题描述•解决方案设计思路和方法•程序实现细节和代码结构说明•性能测试和评估结果分析•学生自己的总结和评估3. 简要算法分析与设计3.1 算法分析算法分析是评估一个算法效率的方法，通常使用时间复杂度和空间复杂度等指标来衡量。

时间复杂度表示算法的运行时间和问题规模之间的关系，空间复杂度表示算法需要占用的内存空间大小和问题规模之间的关系。

常见的算法分析方法包括递归求解、迭代求解和分治法等。

3.2 算法设计算法设计是指解决问题的过程中，构建一个高效、正确、可靠的计算机程序的方法。

通常使用问题建模、设计思维和常用算法等工具来完成。

常见的算法设计方法包括贪心算法、动态规划、分支界定法等。

同时，为了有效提高算法效率，通常需要采用数据结构等相关工具。

4. 数据结构简介数据结构是计算机科学中的重要基础，它是指将数据和相应的操作进行组织的方法。

数据结构可以分为线性结构和非线性结构，线性结构包括栈、队列和链表等，非线性结构包括树和图等。

数据结构的选择通常依据问题的特点和算法需求来考虑。

常见的数据结构包括数组、链表、栈、队列、树、图等。

5. 结语算法分析与设计和数据结构实践是计算机科学中的重要基础，它们与计算机科学的其他领域息息相关。

《数据结构》课程设计利用栈求表达式的值班级： 2学号： 100171021330姓名：吴迪指导老师：王方利用栈求表达式的值1、设计思路这个程序的关键是对数字与运算符的判断和运算符优先级的判断，以及出栈的运算。

建立两个栈，分别存储数字与运算符，栈1存运算符，栈2存数字。

依次读取表达式的字符串，先判断是数字还是运算符，如果是数字不能马上压入栈2，因为可能是大于10的数字，应该继续循环，如果还是数字，则利用计算保存数值，直到指到运算符时停止，将计算后的数字压入栈2。

压入运算符之前先将要压入的与栈顶的运算符优先级相比较，如果栈顶是‘（’而当前不是‘）’，则不需比较优先级，直接压入；如果栈顶是‘（’，当前是‘）’，则抵消（弹出‘（’，指向表达式下一个字符）；若当前的运算符优先级大于栈顶的，则压入；若当前的运算符优先级小于栈內时，弹出栈顶的运算符，同时弹出两组数字，经过运算符的运算后再重新压到栈内。

为了方便判断运算结束，在存储运算符之前先将‘#’压入栈1中，在输入表达式时以‚#‛结束，所以可以以运算符==‘#’并且栈1顶==‘#’来结束运算，弹出栈2的数值，即为表达式求值的最终结果。

上述操作的算法步骤：（1）初始化算符S1,数字栈S2;，将‘#’压入算符栈S1中。

（2）读表达式字符=>w。

（3）当栈顶为‘#’并且w也是‘#’时结束；否则循环做下列步骤：（3-1）如果w是数字，存储到m，再经过计算存储到num中。

m=w-‘0’;num=num*pow(10,n)+m;n++;读下一个字符=>w，如果是运算符，则跳出循环；转3-2。

（3-2）w若是运算符，则：（3-2-1）如果栈顶为‘（’并且w为‘）’则‘（’出栈，读下一个字符=>w；转（3）。

（3-2-2）如果栈顶为‘（’或者栈顶优先级小于w优先级，则w入栈，读下一个字符=>w；转（3）。

否则：从算符栈中出栈，并从数字栈中弹出两组数字进行运算，将结果重新压入数字栈，转（3）。

《数据结构》课程设计报告书题目：算术表达式的求解系别：计算机科学与应用目录一、需求分析 (3)1、设计要求： (3)2、设计构想： (3)二、概要设计 (4)1、本程序包含的模块： (4)三、详细设计 (4)1、定义栈结构 (5)2、栈的基本操作 (5)(1)初始化栈 (5)(2)入栈 (5)(3)出栈 (6)(4)取栈顶元素 (6)(5)运算模块 (6)3、判断运算符的优先级 (7)4、运算函数 (8)(1) 基础运算函数： (8)(2)运算函数 (9)(3)主程序模块 (12)四、调试分析 (12)1、测试结果 (12)2、程序时间复杂度为O（n）； (13)3、设计中出现的问题： (13)4、算法改进： (14)五、课程设计总结 (15)课程设计报告一、需求分析1、设计要求：给定一个算术表达式，通过程序求出最后的结果1>、从键盘输入要求解的算术表达式；2>、采用栈结构进行算术表达式的求解过程；3>、能够判断算术表达式正确与否；4>、对于错误表达式给出提示；5>、对于正确的表达式给出最后的结果；2、设计构想：为了实现算符优先算法使用两个工作栈，一个称作OPTR，以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。

在操作数和操作符入栈前，通过一个函数来判别，输入的是操作数还是操作符，操作数入OPND，操作符入OPTR。

在输入表达式的最后输入‘#’，设定‘#’的优先级最低，代表表达式输入结束。

在表达式输入过程中，遇操作数则直接入栈，遇到运算符则与栈顶运算符比较优先级,若当前运算符优先级高，则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符与新栈顶运算符。

如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。

二、概要设计1、本程序包含的模块：（1）栈模块——实现栈抽象数据类型（2）运算模块——实现数据表达式的运算（3）主程序模块三、详细设计（1）栈模块1、定义栈结构struct Sqstack{int *top;//栈顶元素int *base; //栈底元素int stacksize;//栈的大小};2、栈的基本操作(1)初始化栈int initstack(struct Sqstack &s){s.base=(int *)malloc(stack_size*sizeof(int));if(!s.base)return OVERFLOW;s.top=s.base;s.stacksize=stack_size;return OK;}(2)入栈int push(struct Sqstack &s,int e){if(s.top-s.base>=s.stacksize){s.base=(int*)realloc(s.base,(s.stacksize+stack_increasement)*sizeof(int));if(!(s.base))return OVERFLOW;s.top=s.base+s.stacksize;s.stacksize+=stack_increasement;}* s.top++=e;return OK;}(3)出栈int pop(struct Sqstack &s){int e;if(s.top==s.base)return ERROR;e=*--s.top;return e;}(4)取栈顶元素int gettop(struct Sqstack &s){int e;if(s.top==s.base)return ERROR;e=*(s.top-1);return e;}(5)运算模块1、判断输入字符c是否为操作符：若是，则返回1；否则，返回0int In(int c){char p[10]="+-*/()#^";int i=0;while(p[i]!='\0'){if(p[i]==c)return 1;i++;}return 0;}3、判断运算符的优先级char precede(char top,char c)//该函数为判断当前运算符与前一个运算符的优先级，前一个运算符高于或等于当前运算符的优先级则返回'>'，前一个运算符小于当前运算符的优先级则返'<'，当前一个运算符为'（'当前运算符为'）'时返回'='，用于去除表达式的括号。

ＸＸXＸXX大学《数据结构》课程设计报告班级：学号：姓名：指导老师:目录一算术表达式求值一、需求分析二、程序得主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(oｐeranｄ）、运算符(operator）与界限符（deｌimiter)组成得。

假设操作数就是正整数，运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”，如：＃(7+15）*（2３—２8/４）#。

引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能（1）从键盘读入一个合法得算术表达式，输出正确得结果。

(2）显示输入序列与栈得变化过程。

三、程序运行平台Ｖｉsｕaｌ C＋+6、0版本四、数据结构本程序得数据结构为栈。

（1）运算符栈部分：struct SqStaｃk ／/定义栈{char *base； //栈底指针ｃｈａr *toｐ; ／/栈顶指针inｔstacｋsiｚe； //栈得长度};inｔInitSｔack (SqＳｔack &ｓ) //建立一个空栈S{ｉf （!(s、ｂａse= (char ＊）ｍalloc(5０＊ｓizeof（chａr）)）)exｉt（0）；ｓ、ｔop=s、bａse;s、staｃksiｚｅ=５0；retuｒn OK；}ｃhar GeｔTop（SqStack s,char &e) /／运算符取栈顶元素｛iｆ (s、ｔop==s、ｂase) //栈为空得时候返回EＲROR｛ﻩ prｉntf(＂运算符栈为空！＼n")；ﻩ reｔurn ERＲＯR;｝elsee＝*（s、ｔoｐ-1); //栈不为空得时候用ｅ做返回值，返回S得栈顶元素，并返回OK returnＯＫ;｝ｉnt Push(SqStacｋ＆s，cｈａr ｅ） //运算符入栈｛if （s、tｏp—s、baｓe >= ｓ、ｓtacksｉzｅ）ﻩ{ｐriｎtf（＂运算符栈满!＼n"）;ﻩs、basｅ=（cｈaｒ*）reａlloｃ(s、bａｓe，(s、sｔackｓｉze+5)*ｓizeoｆ(cｈar））；//栈满得时候,追加5个存储空间ｉf(！s、basｅ)exｉt （OVERＦＬOW）；s、top=s、ｂａsｅ+s、ｓｔacｋsize;s、ｓtaｃksiｚｅ+=５;}ﻩ＊(s、ｔop）＋＋=e；／/把e入栈ﻩｒeturn OK;}ｉnｔ Pop(SqStaｃk &ｓ，char ＆ｅ） /／运算符出栈｛ｉｆ (s、toｐ==s、base) ／/栈为空栈得时候，返回ERＲOＲ｛ｐrintf（＂运算符栈为空!\n”）;ﻩ return ERROＲ;}else｛ﻩﻩe=＊-—ｓ、tｏp；/／栈不为空得时候用e做返回值，删除S得栈顶元素，并返回ＯK return OK；}}iｎt StackTｒaｖerse（ＳqStacｋ&ｓ)／/运算符栈得遍历｛ﻩchar ＊t；ﻩt=s、ｂａｓｅ；ﻩif (s、top＝=s、baｓe）｛ﻩ printｆ（”运算符栈为空！\ｎ”)； //栈为空栈得时候返回ＥＲRORｒeturn ERＲOＲ;}ｗhile（t！＝s、tｏp)｛ﻩﻩｐrｉｎｔf（" %c",＊t)； //栈不为空得时候依次取出栈内元素t++;ﻩ}ｒeturｎ EＲRＯR；｝（2）数字栈部分：strｕｃt SqSｔackn//定义数栈｛ｉnt *bａse; //栈底指针ｉnt＊tｏp； //栈顶指针ｉnｔ sｔacksｉze； //栈得长度｝;inｔIｎｉtStackｎ (SqSｔackn &s) //建立一个空栈Ｓ{s、base=（int＊）malｌoc（50*sｉzeof(int）);if(！ｓ、ｂase）eｘiｔ（OVEＲFLＯW）；//存储分配失败s、top=s、base；s、stacksizｅ=5０;reｔuｒn OK；｝ｉｎt GｅtToｐn(ＳqＳtａcｋn s,inｔ＆e) //数栈取栈顶元素{if（s、ｔop=＝s、base）{prinｔｆ(＂运算数栈为空!\ｎ＂);//栈为空得时候返回ERRORﻩ rｅturｎ ERROR;}eｌseﻩe＝＊（s、toｐ-1);／/栈不为空得时候，用e作返回值，返回S得栈顶元素，并返回OＫreturｎＯK；｝int Pｕshn（SｑStａckn ＆s，int ｅ) //数栈入栈｛if（s、tｏp—s、ｂasｅ＞＝s、stacksiｚe)｛ﻩﻩprｉｎｔf（"运算数栈满!\ｎ"）；／/栈满得时候,追加5个存储空间ﻩs、base=(int＊）realloc (s、baｓe,(s、stａcksize＋5)＊sｉzｅof（ｉnt));ｉf（!s、base) ｅxit (ＯＶERFLOW)；ﻩs、top=ｓ、bａsｅ＋ｓ、stacｋsize;//插入元素e为新得栈顶元素s、stacksｉｚe+=5；}*（s、top）++=e; /／栈顶指针变化returｎOK;}ｉｎt Popｎ(ＳｑSｔacｋn ＆s，iｎt &e)//数栈出栈｛ﻩif （s、top=＝ｓ、base）｛ﻩ pｒiｎtｆ（"运算符栈为空！\n＂);//栈为空栈得视时候，返回ERRＯＲﻩ retｕrn ERROR；ﻩ｝ｅlse｛ﻩﻩe=＊—-ｓ、tｏp；／/栈不空得时候，则删除S得栈顶元素,用e返回其值，并返回OK ﻩreturｎOK；｝}ｉnt StacｋＴraveｒsｅn（SqStackn &s)/／数栈遍历{ﻩiｎｔ＊t;ﻩｔ=s、basｅ ;ﻩif（s、top==s、basｅ）ﻩ｛pｒinｔf(＂运算数栈为空！\n”）；//栈为空栈得时候返回ERRORﻩ rｅｔｕrn ERＲＯＲ；ﻩ｝ﻩwｈile（t！=ｓ、ｔop)ﻩ{priｎtf(” ％d”，*ｔ); /／栈不为空得时候依次输出t＋＋;｝return ERRＯR；｝五、算法及时间复杂度１、算法:建立两个不同类型得空栈,先把一个‘＃’压入运算符栈。

数据结构课程设计四则运算表达式求值（C语⾔版）　明⼈不说暗话，直接上，输⼊提取码z3fy即可下载。

⽂件中包含程序，程序运⾏⽂件，设计报告和测试样例，应有尽有，欢迎⼩伙伴们在中下载使⽤。

本课程设计为四则运算表达式求值，⽤于带⼩括号的⼀定范围内正负数的四则运算标准（中缀）表达式的求值。

注意事项：1、请保证输⼊的四则表达式的合法性。

输⼊的中缀表达式中只能含有英⽂符号“+”、“-”、“*”、“/”、“(”、“)”、“=”、数字“0”到“9”以及⼩数点“.”，输⼊“=”表⽰输⼊结束。

例如9+(3-1)*3.567+10/2=，特别是请勿输⼊多余空格和中⽂左右括号。

2、输⼊的中缀表达式默认限定长度是1001，可根据具体情况调整字符串数组的长度。

3、请保证输⼊的操作数在double数据类型范围内，单个数字有效数字长度不可超过15位。

本课程设计中操作数是C语⾔中的双精度浮点数类型。

4、本课程设计中的运算数可以是负数，另外如果是正数可直接省略“+”号（也可带“+”号）。

　下⾯的程序正常运⾏需要在上⾯的百度⽹盘中下载相应⽂件，否则⽆法正常使⽤哦。

1/*本程序为四则运算表达式求值系统，⽤于计算带⼩括号的四则运算表达式求值。

2具体算法：3先将字符串处理成操作单元（操作数或操作符），再利⽤栈根据四则运算4的运算法则进⾏计算，最后得出结果。

*/56 #include<stdio.h>7 #include<ctype.h>8 #include<stdlib.h>9 #include<string.h>10 #include<stdlib.h>11 #include<ctype.h>1213const int Expmax_length = 1001;//表达式最⼤长度，可根据适当情况调整14struct Ope_unit15 {//定义操作单元16int flag;//=1表⽰是操作数 =0表⽰是操作符 -1表⽰符号单元17char oper;//操作符18double real;//操作数，为双精度浮点数19 };2021void Display();//菜单22void Instru(); //使⽤说明23int Check(char Exp_arry[]);24void Evalua(); //先调⽤Conver操作单元化，再调⽤Calculate函数计算结果并输出25int Conver(struct Ope_unit Opeunit_arry[],char Exp_arry[]);//将字符串处理成操作单元26int Isoper(char ch);//判断合法字符（+ - * / ( ) =）27int Ope_Compar(char ope1,char ope2);//操作符运算优先级⽐较28double Calculate(struct Ope_unit Opeunit_arry[],int Opeunit_count,int &flag);//⽤栈计算表达式结果29double Four_arithm(double x,double y,char oper);//四则运算3031int main()32 {33int select;34while(1)35 {36 Display();37 printf("请输⼊欲执⾏功能对应的数字：");38 scanf("%d",&select);39 printf("\n");40switch(select)41 {42case1: Evalua(); break;43case2: Instru(); break;44case0: return0;45default : printf("⽆该数字对应的功能，请重新输⼊\n");46 system("pause");47 }48 }49return0;50 }5152int Check(char Exp_arry[])53 {//检查是否有⾮法字符，返回1表⽰不合法，0表⽰合法54int Explength=strlen(Exp_arry),i;55for(i=0;i<Explength;i++)56 {57if(!Isoper(Exp_arry[i]) && Exp_arry[i] != '.' && !isdigit(Exp_arry[i]))58return1;59if(isdigit(Exp_arry[i]))60 {61int Dig_number=0,Cur_positoin=i+1;62while(isdigit(Exp_arry[Cur_positoin]) || Exp_arry[Cur_positoin]=='.')63 {64 Dig_number++;65 Cur_positoin++;66 }67if(Dig_number >= 16)//最多能够计算15位有效数字68return1;69 }70 }71return0;72 }7374void Evalua()75 {//先调⽤Conver函数将字符串操作单元化，再调⽤Calculate函数计算结果并输出76char Exp_arry[Expmax_length];77int flag=0;//假设刚开始不合法，1表达式合法，0不合法78struct Ope_unit Opeunit_arry[Expmax_length];7980 getchar();//吃掉⼀个换⾏符81 printf("请输⼊四则运算表达式，以=结尾：\n");82 gets(Exp_arry);83 flag=Check(Exp_arry);84if(flag)85 printf("该表达式不合法！\n");86else87 {88int Opeunit_count = Conver(Opeunit_arry,Exp_arry);89double ans = Calculate(Opeunit_arry,Opeunit_count,flag);90if(flag)91 {92 printf("计算结果为：\n");93 printf("%s%lf\n",Exp_arry,ans);94 }95else96 printf("该表达式不合法！\n");97 }98 system("pause");99 }100101int Conver(struct Ope_unit Opeunit_arry[],char Exp_arry[])102 {//将字符串操作单元化103int Explength=strlen(Exp_arry);104int i,Opeunit_count=0;105for(i=0;i<Explength;i++)106 {107if(Isoper(Exp_arry[i]))//是操作符108 {109 Opeunit_arry[Opeunit_count].flag=0;110 Opeunit_arry[Opeunit_count++].oper=Exp_arry[i];111 }112else//是操作数113 {114 Opeunit_arry[Opeunit_count].flag=1;115char temp[Expmax_length];116int k=0;117for(; isdigit(Exp_arry[i]) || Exp_arry[i]=='.' ;i++)118 {119 temp[k++]=Exp_arry[i];120 }121 i--;122 temp[k]='\0';123 Opeunit_arry[Opeunit_count].real=atof(temp);//将字符转化为浮点数124125//负数126if(Opeunit_count == 1 && Opeunit_arry[Opeunit_count-1].flag==0127 && Opeunit_arry[Opeunit_count-1].oper=='-')128 {129 Opeunit_arry[Opeunit_count-1].flag = -1;130 Opeunit_arry[Opeunit_count].real *= -1;131 }// -9132if(Opeunit_count >= 2 && Opeunit_arry[Opeunit_count-1].flag==0133 && Opeunit_arry[Opeunit_count-1].oper=='-' && Opeunit_arry[Opeunit_count-2].flag==0 134 && Opeunit_arry[Opeunit_count-2].oper !=')')135 {136 Opeunit_arry[Opeunit_count-1].flag = -1;137 Opeunit_arry[Opeunit_count].real *= -1;138 }// )-9139140//正数141if(Opeunit_count == 1 && Opeunit_arry[Opeunit_count-1].flag==0142 && Opeunit_arry[Opeunit_count-1].oper=='+')143 {144 Opeunit_arry[Opeunit_count-1].flag = -1;145 }// +9146if(Opeunit_count >= 2 && Opeunit_arry[Opeunit_count-1].flag==0147 && Opeunit_arry[Opeunit_count-1].oper=='+' && Opeunit_arry[Opeunit_count-2].flag==0148 && Opeunit_arry[Opeunit_count-2].oper !=')')149 {150 Opeunit_arry[Opeunit_count-1].flag = -1;151 }// )+9152 Opeunit_count++;153 }154 }155/*for(i=0;i<Opeunit_count;i++)156 {//查看各操作单元是否正确,1是操作数，0是操作符157 if(Opeunit_arry[i].flag == 1)158 printf("该单元是操作数为：%lf\n",Opeunit_arry[i].real);159 else if(Opeunit_arry[i].flag == 0)160 printf("该单元是操作符为：%c\n",Opeunit_arry[i].oper);161 else162 printf("该单元是负号符为：%c\n",Opeunit_arry[i].oper);163 }*/164return Opeunit_count;165 }166167double Calculate(struct Ope_unit Opeunit_arry[],int Opeunit_count,int &flag)168 {//根据运算规则，利⽤栈进⾏计算169int i,dS_pointer=0,oS_pointer=0;//dS_pointer为操作数栈顶指⽰器，oS_pointer为操作符栈顶指⽰器170double Dig_stack[Expmax_length];//操作数栈（顺序存储结构）171char Ope_stack[Expmax_length];//操作符栈172173for(i=0;i<Opeunit_count-1;i++)174 {175if( Opeunit_arry[i].flag != -1 )176 {177if(Opeunit_arry[i].flag)//是操作数178 {179 Dig_stack[dS_pointer++]=Opeunit_arry[i].real;//⼊操作数栈180//printf("%lf\n",Digit[dS_pointer-1]);181 }182else//是操作符 + - * / ( )183 {184//操作符栈为空或者左括号⼊栈185if(oS_pointer==0 || Opeunit_arry[i].oper=='(')186 {187 Ope_stack[oS_pointer++]=Opeunit_arry[i].oper;188//printf("%oS_pointer\Ope_u_count",Operator[oS_pointer-1]);189 }190else191 {192if(Opeunit_arry[i].oper==')')//是右括号将运算符⼀直出栈，直到遇见左括号193 {194 oS_pointer--;//指向栈顶195 dS_pointer--;//指向栈顶196while(Ope_stack[oS_pointer] != '(' && oS_pointer != 0)197 {198 Dig_stack[dS_pointer-1] = Four_arithm(Dig_stack[dS_pointer-1],Dig_stack[dS_pointer], 199 Ope_stack[oS_pointer--]);//oS_pointer--为操作符出栈200201 dS_pointer--;//前⼀个操作数出栈202//printf("操作数栈顶元素等于%lf\n",Digit[dS_pointer]);203 }204 oS_pointer--;//左括号出栈205206 oS_pointer++;//恢复指向栈顶之上207 dS_pointer++;208 }209else if(Ope_Compar(Opeunit_arry[i].oper,Ope_stack[oS_pointer-1]))//和栈顶元素⽐较210 {211 Ope_stack[oS_pointer++]=Opeunit_arry[i].oper;212//printf("%oS_pointer\Ope_u_count",Operator[oS_pointer-1]);213 }214else//运算符出栈，再将该操作符⼊栈215 {216 oS_pointer--;//指向栈顶217 dS_pointer--;//指向栈顶218while(Ope_Compar(Opeunit_arry[i].oper,Ope_stack[oS_pointer])==0 && oS_pointer != -1) 219 {//当前操作符⽐栈顶操作符优先级⾼220 Dig_stack[dS_pointer-1]=Four_arithm(Dig_stack[dS_pointer-1],Dig_stack[dS_pointer], 221 Ope_stack[oS_pointer--]);222 dS_pointer--;223//printf("操作数栈顶元素等于%lf\n",Digit[dS_pointer]);224 }225 oS_pointer++;//恢复指向栈顶之上226 dS_pointer++;227 Ope_stack[oS_pointer++]=Opeunit_arry[i].oper;228 }229 }230 }231 }232 }233/*for(i=0;i<oS_pointer;i++)234 printf("操作符栈%oS_pointer\Ope_u_count",Operator[i]);235 for(i=0;i<dS_pointer;i++)236 printf("操作数栈%lf\n",Digit[i]);*/237 oS_pointer--;//指向栈顶元素238 dS_pointer--;//指向栈顶元素239while(oS_pointer != -1)240 {241 Dig_stack[dS_pointer-1]=Four_arithm(Dig_stack[dS_pointer-1],Dig_stack[dS_pointer], 242 Ope_stack[oS_pointer--]);//oS_pointer--为操作符出栈243 dS_pointer--;//前⼀个操作数出栈244//printf("操作数栈顶元素为%lf\Ope_u_count",Digit[dS_pointer]);245 }246//printf("%dS_pointer,%dS_pointer\n",oS_pointer,dS_pointer);247if(oS_pointer==-1 && dS_pointer==0)248 flag=1;//为1表⽰表达式合法249return Dig_stack[0];250 }251252int Ope_Compar(char ope1,char ope2)253 {//操作符运算优先级⽐较254char list[]={"(+-*/"};255int map[5][5]={//先⾏后列，⾏⽐列的运算级优先级低为0，⾼为1256// ( + - * /257/* ( */1,0,0,0,0,258/* + */1,0,0,0,0,259/* - */1,0,0,0,0,260/* * */1,1,1,0,0,261/* / */1,1,1,0,0 };262int i,j;263for(i=0;i<5;i++)264if(ope1==list[i]) break;265for(j=0;j<5;j++)266if(ope2==list[j]) break;267return map[i][j];268 }269270double Four_arithm(double x,double y,char oper)271 {//四则运算272switch(oper)//保证不含其它运算符273 {274case'+': return x+y;275case'-': return x-y;276case'*': return x*y;277case'/': return x/y;//y不能为0278default : return0;279 }280 }281282int Isoper(char ch)283 {//判断合法字符 + - * / ( ) =284if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='(' || ch==')' || ch=='=')285return1;286return0;287 }288289void Display()290 {//打印菜单291 system("cls");292 printf("/******************************************************************************/\n");293 printf("\t\t 欢迎使⽤本四则运算表达式求值系统\n");294 printf("\n\t说明：建议请您先阅读使⽤说明，再输⼊相应的数字进⾏操作，谢谢配合！\n"); 295 printf("\n\t\t1 四则运算表达式求值\n");296 printf("\n\t\t2 使⽤说明\n");297 printf("\n\t\t0 退出\n");298 printf("/******************************************************************************/\n");299 }300301void Instru()302 {//打印使⽤说明303 FILE *fp;304char ch;305if( ( fp=fopen("使⽤说明.txt","r") ) == NULL)306 {307 printf("⽂件打开失败！\n");308 exit(0);309 }310for(; (ch = fgetc(fp)) != EOF; )311 putchar(ch);312 fclose(fp);313 printf("\n");314 system("pause");315 }。

课程设计任务书学生姓名：专业班级：指导教师：工作单位：题目: 算术表达式的语法分析及语义分析程序设计1．目的通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。

2．设计内容及要求算术表达式的文法：（1）选择算符优先分析法完成以上任务，中间代码选用逆波兰式。

（2）写出算术表达式的符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。

（3）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。

3.课程设计报告书的内容应包括：（1）设计题目、班级、学号、姓名、完成日期；（2）给出算术表达式的语法分析和语义分析的设计。

（3）简要的分析与概要设计；（4）详细的算法描述；（5）源程序清单；（6）给出软件的测试方法和测试结果；（7）设计的评价、收获与体会。

时间安排：第18周，周1-周3下午，周5全天指导教师签名：年月日系主任（或责任教师）签名：年月日1 课设要求设计题目算术表达式转换成逆波兰式（用算符优先分析法）1.1课程设计的目的课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。

通常，设计题中的问题比平时的练习题要复杂，也更接近实际。

编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。

要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。

1.2 设计内容及要求算术表达式的文法：〈无符号整数〉∷＝〈数字〉{〈数字〉}〈标志符〉∷＝〈字母〉{〈字母〉｜〈数字〉}〈表达式〉∷＝ [＋｜－]〈项〉{〈加法运算符〉〈项〉}〈项〉∷＝〈因子〉{〈乘法运算符〉〈因子〉}〈因子〉∷＝〈标志符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’〈加法运算符〉∷＝＋｜－〈乘法运算符〉∷＝＊｜／1.选择算符优先分析法完成以上任务，中间代码选用逆波兰式。

编译原理课程设计_算术表达式的语法分析及语义分析程序设计（模版）第一篇：编译原理课程设计_算术表达式的语法分析及语义分析程序设计（模版）设计题一：算术表达式的语法分析及语义分析程序设计。

1.目的通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。

2.设计内容及要求：算术表达式的文法：〈无符号整数〉∷＝〈数字〉{〈数字〉} 〈标志符〉∷＝〈字母〉{〈字母〉｜〈数字〉} 〈表达式〉∷＝[＋｜－]〈项〉{〈加法运算符〉〈项〉} 〈项〉∷＝〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷＝〈标志符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’ 〈加法运算符〉∷＝＋｜－〈乘法运算符〉∷＝＊｜／选择算符优先分析方法完成以上任务，生成逆波兰式的中间代码；（1）写出算术表达式的符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。

（2）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。

源代码#define _CRT_SECURE_NO_WARNINGS #include “stdio.h” #include “stdlib.h” #include using namespace std;char data[20][20];//算符优先关系char s[100];//模拟符号栈s char lable[20];//文法终极符集char input[100];//文法输入符号串char str[20][10];//用于输入串的分析 int k,j;char a,q;int r;//文法规则个数int r1;int m, n, N;//转化后文法规则个数 char st[10][30];//用来存储文法规则char first[10][10];//文法非终结符FIRSTVT集char last[10][10];//文法非终结符LASTVT集int fflag[10] = { 0 };//标志第i个非终结符的FIRSTVT集是否已求出 int lflag[10] = { 0 };//标志第i个非终结符的LASTVT集是否已求出int deal();//对输入串的分析int terminal_symbol(char c);//判断字符c是否是终极符int location(char c);//求字符c在算符优先关系表中的下标void out(int j, int k, char *s);//打印s栈void firstvt(char c);//求非终结符c的FIRSTVT集void lastvt(char c);//求非终结符c的LASTVT集void table();//创建文法优先关系表 char output[10];//存储逆波兰式 void main(){ int i, j, k = 0;printf(“请输入文法规则数：”);scanf(“%d”, &r);printf(“请输入文法规则：n”);for(i = 0;i} for(i = 0;i} for(i = 0;ifor(j = 0;st[i][j]!= '';j++)if((st[i][j]'Z')&& st[i][j]!= '-'&&st[i][j]!= lable[k++] = st[i][j];for(j = 0;st[i][j]!= '';j++){ } if(st[i][0]'Z'){} if(st[i][j] >= 'A'&&st[i][j] <= 'Z'){} if(st[i][j + 1] >= 'A'&&st[i][j + 1] <= 'Z'){} printf(“文法error!n”);exit(-1);printf(“文法error!n”);exit(-1);scanf(“%s”, st[i]);//存储文法规则，初始化FIRSTVT集和LASTVT集*/first[i][0] = 0;/*first[i][0]和last[i][0]分别表示st[i][0]非终极符的last[i][0] = 0;FIRSTVT集和LASTVT集中元素的个数*/'>'&&st[i][j]!= '|')lable[k] = '#';lable[k + 1] = '';} table();//printf(“FIRST集为：n”);//输出每个非终结符的FIRST集for(i = 0;i} printf(“LAST集为：n”);//输出每个非终结符的LAST集for(i = 0;i} printf(“算符优先分析表如下:n”);for(i = 0;lable[i]!='';i++)printf(“t%c”, lable[i]);printf(“n”);for(i = 0;i} printf(“请输入文法输入符号串以#结束:”);scanf(“%s”, input);deal();cout << “逆波兰式为：”;for(i = 0;lable[i]!= '';i++)cout << output[i] << '';// cout << endl;printf(“%ct”, lable[i]);for(j = 0;jchar text[20][10];//存储改写后的文法int i, j, k, t, l, x = 0, y = 0;int m, n;x = 0;for(i = 0;ifirstvt(st[i][0]);lastvt(st[i][0]);} for(i = 0;i{text[x][y] = st[i][0];y++;for(j = 1;st[i][j]!= '';j++){if(st[i][j] == '|')//{text[x][y] = '';x++;y = 0;text[x][y] = st[i][0];y++;text[x][y++] = '-';text[x][y++] = '>';}else{text[x][y] = st[i][j];y++;}}text[x][y] = '';x++;y = 0;} r1 = x;//printf(“转化后的文法为:n”);for(i = 0;iprintf(“%sn”, text[i]);} for(i = 0;i{//输出转化后的文法规则串/*求每个终结符的推导结果(去掉“->”后的} str[i][0] = text[i][0];for(j = 3, l = 1;text[i][j]!= '';j++, l++)str[i][l] = text[i][j];str[i][l] = '';for(i = 0;ifor(j = 1;text[i][j + 1]!= '';j++){if(terminal_symbol(text[i][j])&& terminal_symbol(text[i][j + 1])){} if(text[i][j + 2]!= ''&&terminal_symbol(text[i][j])&& {} if(terminal_symbol(text[i][j])&&!terminal_symbol(text[i][j + 1]))//终结{} if(!terminal_symbol(text[i][j])&& terminal_symbol(text[i][j + 1]))//非终{ for(k = 0;k} m = location(text[i][j]);for(t = 0;t} n = location(first[k][t + 1]);data[m][n] = 'break;m = location(text[i][j]);n = location(text[i][j + 2]);data[m][n] = '=';m = location(text[i][j]);n = location(text[i][j +1]);data[m][n] = '=';terminal_symbol(text[i][j +2])&&!terminal_symbol(text[i][j + 1]))符和非终结符相接，用后于关系填表结符和终结符相接，用先于关系填表if(st[k][0] == text[i][j])break;}n = location(text[i][j + 1]);for(t = 0;t{m = location(last[k][t + 1]);data[m][n] = '>';}}} } m = location('#');//#后于所有的终结符规约for(t = 0;tn = location(first[0][t + 1]);data[m][n] = 'for(t = 0;tm = location(last[0][t + 1]);data[m][n] = '>';} data[n][n] = '=';}void firstvt(char c){ int i, j, k, m, n;for(i = 0;i {if(st[i][0] == c)break;} if(fflag[i] == 0){n = first[i][0] + 1;m = 0;do{if(m == 2 || st[i][m] == '|'){ if(terminal_symbol(st[i][m + 1]))//求FIRSTVT集}}} {} else {} if(terminal_symbol(st[i][m + 2])){} if(st[i][m + 1]!= c){firstvt(st[i][m + 1]);for(j = 0;j}for(k = 0;k}int t;for(t = 0;t}if(t == n){}first[i][n] = first[j][k + 1];n++;if(first[i][t] == first[j][k + 1])break;if(st[j][0] == st[i][m + 1])break;first[i][n] = st[i][m + 2];n++;first[i][n] = st[i][m + 1];n++;m++;} while(st[i][m]!= '');first[i][n] = '';first[i][0] =--n;fflag[i] = 1;void lastvt(char c)//求LASTVT集 {int i, j, k, m, n;for(i = 0;i} if(lflag[i] == 0){n = last[i][0] + 1;m = 0;do {if(st[i][m + 1] == '' || st[i][m + 1] == '|'){if(terminal_symbol(st[i][m])){} else {if(terminal_symbol(st[i][m1];n++;last[i][n] = st[i][m];n++;if(st[i][0] == c)break;}}}}}}if(t == n){}last[i][n] = last[j][k + 1];n++;m++;} while(st[i][m]!= '');last[i][n] = '';last[i][0] =--n;lflag[i] = 1;int deal(){int i, j;int size = 0;// int x, y;int z;//输入串的长度 k = 1;s[k] = '#';//栈置初值for(i = 0;input[i]!= '';i++);//计算输入串的长度z = i--;// i = 0;while((a = input[i])!= '')//a表示要输入的字符 {if(terminal_symbol(s[k]))j = k;j = k1]))j = j2;x = location(s[j]);y = location(q);} while(data[x][y]!= '} k = j + 1;if(k == 2 && a == '#'){out(1, k, s);printf(“%c”, a);out(i + 1, z, input);printf(“结束n”);for(N = 0;N} if(!terminal_symbol(s[m])&&!terminal_symbol(str[N][n])){} elseif(terminal_symbol(s[m]))if(s[m] == str[N][n]){}s[j + 1] = str[N][0];break;if(terminal_symbol(s[m + 1])&& terminal_symbol(str[N][n + 1]){}s[j + 1] = str[N][0];break;&& s[m + 1] == str[N][n + 1])}} printf(“规约成功!n”);return 1;//输入串符合文法的定义elseif(data[x][y] == 'out(1, k, s);printf(“%c”, a);out(i + 1, z, input);printf(“移进n”);k++;s[k] = a;i++;}else{printf(“n规约失败n”);return 0;} } printf(“n规约失败n”);//return 0;}void out(int j, int k, char *s){ int n = 0;int i;for(i = j;i <= k;i++){ printf(“%c”, s[i]);n++;} for(;n<15;n++){printf(“ ”);} }int location(char c){ int i;for(i = 0;lable[i]!= '';i++)//求字符c在算符优先关系表中的下标} {} return-1;if(c == lable[i])return i;int terminal_symbol(char c)//判断字符c是否是终极符 {} int i;for(i = 0;lable[i]!= '';i++){} return 0;if(c == lable[i])return 1;第二篇：编译原理语法分析实验报告实验2：语法分析1.实验题目和要求题目：语法分析程序的设计与实现。

实验课程名称专业班级学生姓名学号指导教师20 至 20 学年第学期第至周算术表达式求值演示一、概述数据结构课程设计.要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面.加深对课程基本内容的理解。

同时.在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

在这次的课程设计中我选择的题目是算术表达式求值演示。

表达式计算是实现程序设计语言的基本问题之一.也是栈的应用的一个典型例子。

设计一个程序.演示用算符优先法对算术表达式求值的过程。

深入了解栈和队列的特性.以便在解决实际问题中灵活运用它们.同时加深对这种结构的理解和认识。

二、系统分析1．以字符列的形式从终端输入语法正确的、不含变量的整数表达式。

利用已知的算符优先关系.实现对算术四则混合运算表达式的求值.并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。

2．一般来说.计算机解决一个具体问题时.需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型.然后设计一个解决此数学模型的算法.最后编出程序.进行测试.调试直至得到想要的答案。

对于算术表达式这个程序.主要利用栈.把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法.可以使用两个栈.一个用以寄存运算符.另一个用以寄存操作数和运算结果。

3．演示程序是以用户于计算机的对话方式执行.这需要一个模块来完成使用者与计算机语言的转化。

4．程序执行时的命令：本程序为了使用具体.采用菜单式的方式来完成程序的演示.几乎不用输入什么特殊的命令.只需按提示输入表达式即可。

（要注意输入时格式.否者可能会引起一些错误）5. 测试数据。

三、概要设计一个算术表达式中除了括号、界限符外.还包括运算数据和运算符。

由于运算符有优先级别之差.所以一个表达式的运算不可能总是从左至右的循序执行。

每次操作的数据或运算符都是最近输入的.这与栈的特性相吻合.故本课程设计借助栈来实现按运算符的优先级完成表达式的求值计算。

一、设计思想（一）中缀转后缀的设计思想设计一个能实现表达式自动求值计算，算术表达式由操作数、算符和括号组成。

由于运算符的优先级不同还要考虑括号。

所以表达式不可能一直的从左到右进行，所以就借助栈来实现这个表达式的求值。

首先要把算术表达式变换成与之等值的无括号表达式，也就是中缀转后缀，它也是这个算法的关键。

设计两个栈，一个为字符型的，存放运算符，用以将算术表达式变成无括号的表达式；另一个浮点型的，存放操作数，用以对无符号的表达式进行求值。

我们要假设运算符的优先级：( ) , * /, + - 。

首先将一左括号‘(’入栈，作为栈底元素；接着从左到右对算术表达式进行扫描。

每次读一位，若遇到左括号‘（’，则进栈；若遇到的是操作数，则立即输出；若又遇到运算符，如果它的优先级比栈顶元素的优先级数高的话，则直接进栈，否则输出栈顶元素，直到新的栈顶元素的优先级数比它低的，然后将它压栈；若遇到是右括号‘）’，则将栈顶的运算符输出，直到栈顶的元素为‘（’，然后，左右括号互相底消；到设计的结束标志的时候表示表达式已经扫描完毕，表达式已经全部输入，将栈中的运算符全部输出，删除栈底的左括号。

以上完成了中缀表达式转后缀表达式，输出无括号的后缀表达式。

读后缀表达式，若遇数值，操作数进栈；若遇运算符，让操作数栈的栈顶和次栈顶依次出栈并与此运算符进行运算，运算结果入操作数栈；重复这个步骤，直到遇到结束标志，则此时栈中的结果便是所求的后缀表达式的值，接着输出结果。

以上就是设计这个算法的主要的思想。

(二) 直接计算的设计思想直接计算其实跟上一个相似，它是在上面扫两遍的思想进行修改的得来。

首先，要建立两个栈，一个为字符型的，存放运算符，另一个浮点型的，存放操作数，我们开始对表达式进行扫描。

首先要确定运算符的优先级：（、）、*、/、+、-。

如果扫描到的是数字符号，把它们转换成浮点型数据或其他可运算的数据类型，存入操作数栈中。

如果扫描到的是运算符号，第一个运算符进栈，遇到‘（’存入运算符栈中，我们按照第一种算法的方法将表达式依次扫描。

课程设计报告课程名称数据结构课题名称中缀算术表达式求值专业通信工程班级通信0902学号姓名指导教师2011 年07 月01 日湖南工程学院课程设计任务书课程名称数据结构课题中缀算术表达式求值专业班级通信工程0902学生姓名学号指导老师审批任务书下达日期2011 年06 月27日任务完成日期2011 年07 月01日设计要求：1. 课程设计报告规范（1）需求分析a.程序的功能。

b.输入输出的要求。

（2）概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。

b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。

（3）详细设计a.采用C语言定义相关的数据类型。

b．写出各模块的类C码算法。

c.画出各函数的调用关系图、主要函数的流程图。

（4）调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。

b.程序调试中遇到的问题以及解决问题的方法。

c.课程设计过程经验教训、心得体会。

（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。

（6）书写格式a.设计报告要求用A4纸打印成册：b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。

（7）附录源程序清单（带注释）2. 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。

具体考核标准包含以下几个部分：（1）平时出勤（占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。

、实验的目的和要求1.采用算符优先数算法, 能正确求值表达式;2.熟练掌握栈的应用;3•熟练掌握计算机系统的基本操作方法，了解如何编辑、编译、链接和运行一个C++程序; 4.上机调试程序,掌握查错、排错使程序能正确运行。

三、实验的环境:指硬件和软件环境1.硬件环境: Intel 奔腾双核T2390 双核处理器(1.86GHz 主频/1MB 二级缓存/533MHz 前端总线)， RAM:2G .2.软件环境: 操作系统：windows vista编译软件：Microsoft Viual C++6.03.软件环境介绍:Visual C++是一个功能强大的可视化软件开发工具。

自1993年Microsoft公司推出Visual C++1.0后，随着其新版本的不断问世，Visual C++已成为专业程序员进行软件开发的首选工具。

虽然微软公司推出了Visual C++.NET(Visual C++7.0) ，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP 和Windows NT4.0。

所以实际中，更多的是以Visual C++6.0 为平台。

Visual C++6.0不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境( integrated development environment,IDE )。

Visual C++6.0 由许多组件组成，包括编辑器、调试器以及程序向导AppWizard 、类向导Class Wizard 等开发工具。

这些组件通过一个名为Developer Studio 的组件集成为和谐的开发环境。

四、算法描述:1.头文件:Stack.hCalculator.hMethod:Stack method:Push(); // 进栈操作Pop(); // 出栈操作GetHead(); // 返回栈中的最顶层元素MakeEmpty(); // 清空栈操作Calculator method:Calculator();// 计算主体celarstream(); // 清空输入流Prior();// 返回运算符的优先级done(); // 做一次二元运算output(); // 打印结果并输出EnEmpty(); // 调用MakeEmpty(), 并清空栈2.cpp 文件Calculator.cppMethod:int main(); // 主程序3.程序流程图优先级比较算法Data 算法存放操作字符 存放数据调用 Calculator 。

中南民族大学计算机科学学院课程设计报告课程数据结构题目算法表达式语法检查年级 2014专业软件工程学生柳真学号 201421092073指导教师刘赛2015年12月20 日中南民族大学计算机科学学院本科课程设计任务书设计名称：算术表达式语法检查指导教师：下达时间： 2015-11-30 学生姓名：学号：年级专业： 2014级软件工程一、课程设计的基本要求利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。

通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。

具体要求如下：1、对现实复杂问题中的数据对象特性及组织方法进行分析和研究，设计适当的数据逻辑结构、存贮结构以及相应运算操作，把现实世界问题建模转化为计算机内部表示并进行处理。

2、采取模块化方式进行程序设计，要求程序的功能设计、数据结构设计及整体结构设计合理。

学生也可根据自己对题目的理解增加新的功能模块（视情况可另外加分）。

3、系统以菜单界面方式（至少采用文本菜单界面，如能采用图形菜单界面更好）工作，运行界面友好，演示程序以用户和计算机的对话方式进行，利用文件进行数据的提取与存储。

4、程序算法说明清晰，理论分析与计算正确，运行情况良好，实验测试数据无误，容错性强（能对错误输入进行判断控制）。

5、编程风格良好（包括缩进、空行、适当注释、变量名和函数名见名知意，程序容易阅读等）；6、写出规范的课程设计报告，具体要求见相关说明文档。

二、课程设计的主要内容题目描述：算术表达式语法检查。

功能要求及说明：（1）键盘读入一个四则运算算术表达式，对其进行语法检查；（2）算术表达式允许嵌套，如果出错，指出出错位置；（3）不需要计算结果；（4）尽量不使用栈。

数据结构算法实现及解析课程设计一、课程设计背景随着信息技术的不断发展，计算机科学技术在各个领域中扮演着越来越重要的角色。

数据结构和算法是计算机科学的基础和核心。

在当前的大数据时代，高效的数据结构和算法设计显得尤为重要，能够有效提高计算机应用的执行效率。

为了加强学生对数据结构和算法的掌握，促进其学科素养和综合能力的提升，本课程设计旨在帮助学生逐步掌握数据结构和算法的基本概念、基本操作和常用实现方法，并训练学生综合运用所学知识解决实际问题的能力。

二、课程设计目标•掌握数据结构和算法的基本概念、基本操作和常用实现方法；•熟悉数据结构和算法在实际问题中的应用；•能够运用所学知识和技能解决实际问题。

三、教学内容1.数据结构基础–数组、链表、栈、队列、树、图等基本数据结构–数据结构的存储结构及常用实现方法2.基本算法设计和分析方法–递归、分治、贪心、动态规划等基本算法思想–常用算法的具体实现方法以及时间复杂度分析3.高级数据结构及算法设计–堆、并查集、哈希表、字典树等高级数据结构–基于高级数据结构的算法设计四、教学方法本课程设计采用案例教学法和综合实践教学法相结合的教学方法。

在课堂上，老师将通过案例演示的方式，深入浅出地解释数据结构和算法的基本概念和基本操作，并通过练习和作业等方式让学生在实践中巩固所学知识。

同时，学生也需要完成一些小组或个人的课程设计项目，并在课堂上进行展示和讲解，以帮助他们更好地理解和掌握所学知识。

五、课程设计评价课程设计的评价主要包括学生的课程成绩、小组或个人课程设计项目的评分以及课堂表现等。

其中，学生的课程成绩将主要通过期末考试来体现；小组或个人课程设计项目的评分将由老师和同学共同评定；课堂表现将从课堂参与度、作业完成情况等多个方面进行评价。

六、结语通过本课程设计的学习，相信能够让学生更好地掌握数据结构和算法的基本概念、基本操作和常用实现方法，并锻炼他们的综合能力和实际问题解决能力。

计算机科学系《数据结构课程设计》报告课题名称：算术表达式求值目录1.问题描述-----------------------------------------------------------32.基本要求-----------------------------------------------------------33.工具/准备工作----------------------------------------------------34.分析与实现--------------------------------------------------------45. 课程设计体会与感悟------------------------------------------161．问题描述从键盘上输入中缀算术表达式，包括括号，计算出表达式的值。

2.基本要求（1）程序能对所输入的表达式做简单的判断，如表达式有错，能给适当提示。

（2）能处理单目运算符：+，-。

3.工具/准备工作在开始项目之前，应回顾复习相关内容。

需要一台计算机装有visual C++。

4.分析与实现对于中缀表达式，一般运算规则如下：（1）先乘方，再乘除，最后加减；（2）同级运算从左算到右；（3）先括号内再括号外；（4）用到的头文件”utility.h”,”lk_stack.h”,”node.h”,”calculator.h”.根据实践经验，可以对运算符设置统一的优先级，从而方便比较。

表中给出了包括加、上面讨论的的+、—为双目运算符，如为单目运算符，编程实现时，可在前面加上0而转化为双目运算符。

如在+、—的前一个字符（如当前字符不是运算符时，规定用0表示）为‘=’或‘（’，则为单目运算符。

具体实现算法时，可设置两个工作栈，一个为操作栈，一个为操作符栈optr，另外一个为操作数栈opnd,算法基本思路如下：（1）将optr栈和opnd栈清空，在optr栈中加入一个‘=‘。

算术表达式的语法及语义分析程序设计概述1.1设计题目算术表达式的语法及语义分析程序设计。

1.2设计目的通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。

1.3设计任务内容(1)利用递归下降分析方法和思想对某些语句进行语法分析与语义分析，生成相应的中间代码。

(2) 学会正确运用语法规则，并能应用所学的方法解决存在的问题，给出语法分析方法及中间代码形式的描述、文法和属性文法的设计。

2设计环境与工具本课程设计程序采用VC++开发，其可执行文件能在Window界面上运行良好。

3设计原则3.1语法分析方法采用递归下降分析方法进行语法分析。

3.2中间代码形式描述在描述中间代码的时候，应用四元式。

3.3文法和属性文法设计算术表达式的文法：〈无符号整数〉∷＝〈数字〉{〈数字〉}〈标识符〉∷＝〈字母〉{〈字母〉｜〈数字〉}〈表达式〉∷＝[＋｜－]〈项〉{〈加法运算符〉〈项〉}〈项〉∷＝〈因子〉{〈乘法运算符〉〈因子〉}〈因子〉∷＝〈标识符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’〈加法运算符〉∷＝＋｜－〈乘法运算符〉∷＝＊｜／4简要分析与概要设计4.1简要分析首先应该把用文字表示的文法改写为数学符号。

（其中关于无符号整数和标识符，由于可以在词法分析的过程中给以确定，所以就不必抽象其表达式。

）设：indentifer ：标识符digit : 无符号整数E：表达式T：项F：因子则一个简单的术表达式的文法G1中包含以下产生式：E -> E+E | E-E | E*E | E/E | (E) | indentifer | digit为了明确运算符的优先权（括号的优先权高于乘除法，乘除法的优先权高于加减法），可改写文法G1如下：改写后的文法G2:E -> E+T | E-T | TT -> T*F | T/F | FF -> (E) | indentifer | digit为了避免左递归的发生，可进一步将文法改成：文法G[E]：（1）E -> [+|-]TG（2）G -> +TG|—TG（3）G -> ε（4）T -> FS（5）S -> *FS|/FS（6）S -> ε（7）F -> (E)（8）F -> indentifer | digit4.2概要设计由于程序在执行的过程中分为词法、语法、语义，故在程序设计的时候也按照这种方式，把整个程序分成三个大的部分，即词法分析部分，语法分析部分和语义分析部分。

表达式求值一目的利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。

通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。

设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果二需求分析设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果。

对于这个程序我们从输入，输出，和功能三方面来分析。

1.程序输入：从键盘上输入表达式，一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量）。

为了简化，操作数只能为浮点数，操作符为“ +”、“-”、“*”、“/”、“（”、“）”，用“#“表示结束。

2.程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程，如运算符栈、运算数栈的出入记录，字符出入栈的过程，打印出完整的过程。

3.功能要求及说明：从键盘上输入表达式。

分析该表达式是否合法（包含分母不能为零的情况）：（1）是数字，则判断该数字的合法性。

（2）是规定的运算符，则根据规则进行处理。

在处理过程中，将计算该表达式的值。

（3）若是其它字符，则返回错误信息。

若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。

三概要设计1.数据结构的选择：任何一个表达式都是由操作符，运算符和界限符组成的。

我们分别用顺序栈来寄存表达式的操作数和运算符。

栈是限定于紧仅在表尾进行插入或删除操作的线性表。

为了实现算符优先算法，可以使用两个工作栈。

一个称做SqStack1，用以寄存运算符；另一个称做SqStack2，用以寄存操作数或运算结果。

首先置操作数栈为空栈，表达式起始符“＃”作为运算符栈的栈底元素，然后依次读入表达式的每个字符，若是操作数则进入SqStack2栈，若是运算符则和SqStack1栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕。