表达式类型的实现毕业设计（论文）（已处理）

表达式类型的实现毕业 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 （论文）（已处理） 课程设计 表达式类型的实现 学 院 计算机学院 专 业 计算机科学与技术 年级班别 2006级01班 学 号 3106006394 学生姓名 方锐洲 辅导教师__ 吴伟民_______ 成 绩_______ ______ 2008年7月 3 日 表达式类型的实现 目录 一需求分析 二概要设计 1数据类型的声明 2表达式的抽象数据类型定义 3整体设计 三详细设计 1二叉树的存储类型 2顺序栈的存储类型 3表达式的基本操作 4主程序和其他伪码算法 5函数的调用关系 四设计和调试分析 五用户手册 六测试 七课程设计的心得和心得以及问题-----18 八参考文献 九附录程序清单 一需求分析课程设计要求 问题的描述 一个表达式和一棵二叉树之间存在着自然的对应关系写一个程序实现 基于二叉树表示的算术表达式Expression的操作 基本要求 一必做部分 假设算术表达式Expression内可以含有变量a-z常量0-9和二元运算 符-乘幂实现以下操作 1ReadExpr E ――以字符序列的形式输入语法正确的前缀表达式并构造 表达式E 2WriteExpr E ――用带括号的中缀表达式输出表达式E 3Assign Vc ――实现对变量V的赋值V c变量的初值为0 4Value E ――对算术表达式E求值 5CompoundExpr pE1E2 ――构造一个新的复合表达式E1pE2 二选做部分 1以表达式的原书写形式输入支持大于0的正整数常量 2增加常数合并操作MergeConst E 合并表达式E中所有常数运算例如对表 达式E 23-a b34 进行合并常数的操作后求得E 5-a b12 测试数据 分别输入0a-91abc5x28x32x2x6并输出 每当输入一个表达式后对其中的变量赋值然后对表达式求值 还有很多测试的数据详细请见附上的文件Testtxt 二概要设计 1数据类型的声明 在这个课程设计中采用了链表二叉树的存储结构以及两个顺序栈的辅助 存储结构 头文件以及存储结构 include include include include define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define OVERFLOW 0 typedef int Status 2表达式的抽象数据类型定义 ADT Expression 数据对象DD是具有数值的常量C和没有数值的变量V 数据关系R V或者C P V或者C VC?D V或者C P V或者C 表示由运算符P结合起来的表达式E 基本操作 Status Input_Expr stringflag 操作结果以字符序列的形式输入语法正确的前缀表达式保存到字符串string 参数flag表示输出的提示信息是什么输入成功返回OK否则返回ERROR void judge_value Estringi 初始条件树E存在表达式的前缀字符串string存在 操作结果判断字符string[i]如果是0-9常量之间二叉树结点E存为整型否则存为字符型 Status ReadExpr Eexprstring 初始条件表达式的前缀形式字符串exprstring存在 操作结果以正确的前缀表示式exprstring并构造表达式E构造成功返回OK否则返回ERROR Status Pri_Compare c1c2 初始条件c1和c2是字符 操作结果如果两个字符是运算符比较两个运算符的优先级c1比c2优先返回OK否则返回ERROR void WriteExpr E 初始条件表达式E存在 操作条件用带括弧的中缀表达式输入表达式E void Assign EVcflag 初始条件表达式E存在flag为标志是否有赋值过 操作结果实现对表达式E中的所有变量V的赋值 V c long Operate opr1opropr2 初始条件操作数opr1和操作数opr2以及操作运算符opr 操作结果运算符运算求值参数opr1opr2为常量opr为运算符根据不同的运 算符实现不同的运算返回运算结果 Status Check E 初始条件表达式E存在 操作结果检查表达式E是否还存在没有赋值的变量以便求算数表达式E的值 long Value E 初始条件表达式E存在 操作结果对算术表达式求值返回求到的结果 void CompoundExpr PE1E2 初始条件表达式E1和E2存在 操作条件构造一个新的复合表达式 E1 P E2 Status Read_Inorder_Expr stringpre_expr 操作结果以表达式的原书写形式输入表达式的原书写形式字符串string变 为字符串pre_expr后调用reversal_string 函数反转得到前缀表达式 pre_expr得到正确的前缀表达式返回OK否则返回ERROR void MergeConst E 操作结果常数合并操作合并表达式E中所有常数运算 ADT Expression 3整体设计 在这个课程设计中有两个源代码文件expressionh和expressionc 在expressionh文件中包含了各个存储结构的声明和辅助存储结构的两个栈的基本操作在expressionc文件中是实现课程设计要求的各个函数 《一》expressionh文件的整体结构 1各个存储结构的声明 2两个除了栈名和栈存储的元素不一样的顺序栈的基本操作其基本操作如下 对于栈SqStack Status InitStack SqStack S 构造一个空栈S Status StackEmpty SqStack S 若栈S为空栈则返回TRUE否则返回FALSE Status Push SqStack SSElemType e 插入元素e为新的栈顶元素 Status Pop SqStack SSElemType e 若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR Status GetTop SqStack SSElemType e 若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR 对于栈SqStack1 Status InitStack1 SqStack1 S 构造一个空栈S Status StackEmpty1 SqStack1 S 若栈S为空栈则返回TRUE否则返回FALSE Status Push1 SqStack1 SSElemType1 e 插入元素e为新的栈顶元素 Status Pop1 SqStack1 SSElemType1 e 若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR Status GetTop1 SqStack1 SSElemType1 e 若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR 顺序栈的基本操作的算法见程序清单 《二》expressionc文件的整体结构 1主程序模块的整体流程 可以从主菜单函数可以明了的了解的程序的整体流程主菜单函数menu 如下 char menu char choice printf "\n" printf "\n 1 输入正确的前缀表达式" printf "\n 2 带括弧的中缀表示式输出" printf "\n 3 对变量进行赋值" printf "\n 4 对算数表达式求值" printf "\n 5 构造一个新的复合表达式" printf "\n 6 以表达式的原书写形式输入" printf "\n 7 合并表达式中所有常数运算" printf "\n 0 退出" printf "\n" printf "\n请输入你的选择 " choice getche return choice 在主函数中采用多分支程序设计语句switch 使程序产生不同的流向从而 达到实现课程设计的各个要求 void main while 1 清屏 switch 主菜单 根据不同的选择调用不同的操作函数完成各个操作 2本程序有四个模块主程序模块二叉树模块两个顺序栈模块四者的调用关 系如下 主程序模块中的对于表达式的存储结构调用了二叉树模块而在构造表达式的二叉树模块中又调用了顺序栈SqStack模块主程序中在将原表达式形式输入表达式转换为前缀表达式操作中调用了顺序栈SqStack1模块 三详细设计 1二叉树的存储类型 二叉树结点类型 typedef enum INTCHAR ElemTagINT为整型数据numCHAR为字符型数据c typedef struct TElemType ElemTag tag INTCHAR 指示是整型还是字符型 union int numtag INT时为整型 char ctag CHAR时为字符型 TElemType 二叉树的二叉链表存储表示 typedef struct BiTNode TElemType data struct BiTNode lchildrchild 左右孩子指针 BiTNodeBiTree 二叉树的基本操作已经在构造表达式和表达式中的基本操作中根据不同的 功能和实际情况修改了详细见各个函数操作的算法设计 2顺序栈的存储类型 栈的顺序存储表示 define STACK_INIT_SIZE 10 存储空间初始分配量 define STACKINCREMENT 2 存储空间分配增量 两个顺序栈 typedef struct SqStack SElemType base 在栈构造之前和销毁之后base的值为NULL SElemType top 栈顶指针 int stacksize 当前已分配的存储空间以元素为单位 SqStack 顺序栈SqStack typedef struct SqStack1 SElemType1 base 在栈构造之前和销毁之后base的值为NULL SElemType1 top 栈顶指针 int stacksize 当前已分配的存储空间以元素为单位 SqStack1 顺序栈SqStack1 相关的基本操作见上面的expressionh文件的整体结构的说明详细的算法 设计见附录的程序清单 3表达式的基本操作 Status Input_Expr char stringint flag 以字符序列的形式输入语法正确的前缀表达式保存到字符串string 参数flag 0表示输出的提示信息是"请输入正确的前缀表示式" flag 1表示输出的提示信息为"请以表达式的原书写形式输入正确表示式" void judge_value BiTree Echar stringint i 判断字符string[i]如果是0-9常量之间二叉树结点存为整型否则存为字符型 Status ReadExpr BiTree Echar exprstring 以正确的前缀表示式并构造表达式E Status Pri_Compare char c1char c2 如果两个字符是运算符比较两个运算符的优先级c1比c2优先返回OK否则返回ERROR void WriteExpr BiTree E 用带括弧的中缀表达式输入表达式 void Assign BiTree Echar Vint cint flag 实现对表达式中的所有变量V的赋值 V c 参数flag为表示是否赋值过的标志 long Operate int opr1char oprint opr2 运算符运算求值参数opr1opr2为常量opr为运算符根据不同的运算符实现不同的运算返回运算结果 Status Check BiTree E 检查表达式是否还存在没有赋值的变量以便求算数表达式的值 long Value BiTree E 对算术表达式求值 void CompoundExpr char PBiTree E1BiTree E2 构造一个新的复合表达式 Status Read_Inorder_Expr char stringchar pre_expr 以表达式的原书写形式输入表达式的原书写形式字符串string变为字符串 pre_expr后调用reversal_string 函数反转得到前缀表达式pre_expr void MergeConst BiTree E 常数合并操作函数合并表达式E中所有常数运算 下面列出部分基本操作的伪码算法未列出的请见程序清单 其中部分基本操作的伪码算法如下 4主程序和其他伪码算法 void main while 1 switch menu case 1输入正确的前缀表达式 if Input_Expr Expr_String0 输入正确的前缀表达式 if ReadExpr EExpr_String 构造表达式 flag 1printf "\n表达式构造成功" case 2带括弧的中缀表示式输出 if flag 1 WriteExpr E else printf "\n表达式未构造成功请构造成功的表达式" case 3对变量进行赋值 if flag 1 flushall 清理缓冲区 V getchar scanf c Assign EVcAssign_flag else printf "\n表达式未构造成功请构造成功的表达 式" case 4对算数表达式求值 if flag 1 if Check E result Value E WriteExpr E printf result else printf "\n表达式未构造成功请构造成功的表达 式" case 5构造一个新的复合表达式 if flag 1 flushall 清理缓冲区 if Input_Expr string1 if Read_Inorder_Expr stringExpr_String 按原表达式形式输入 reversal_string Expr_String if ReadExpr E1Expr_String flag 1P getchar CompoundExpr PEE1 else printf "\n复合新的表达式失败请按 任意键返回主菜单" case 6以表达式的原书写形式输入 if Input_Expr string1 if Read_Inorder_Expr stringExpr_String reversal_string Expr_String if ReadExpr EExpr_String flag 1printf "\n表达式构造成功" case 7合并表达式中所有常数运算 if flag 1 MergeConst E case 0退出 5函数的调用关系 除了主函数main 外其他各个函数相对于其它函数来说是独立的函数的使用都由主函数main 调用使用的可以简单的说各个函数都是主函数下的从函数 四设计和调试分析 1在起初设计上针对前缀表达式的要求构造表达式E常量的范围限定在0-9之间后在这个构造表达式的架构上逐个逐个实现对表达式上的操作后扩展到以表达式的原书写形式输入整体架构是不变的只是增加一些细节的处理功能这样的设计从开始到最后都处于可扩展的模块化设计 2在算法设计中构造表达式树的时候本来以为使用递归构造表达式会很难做到出错处理的所以采用了顺序栈辅助构造方法并且尽可能地对程序进行完善出错处理但是经过与同学的相互讨论和研究发现自己的想法犯了很大的错误递 归构造表达式对于出错处理很简单也很完善这一点让我加深了递归的使用和理解 3在对各个功能操作的实现上时间复杂度大多数是O n 空间上增加了辅助栈空间复杂度为O ns 而在以原表达式形式输入操作上实际上是对字符串的操作将一串原表达式字符串处理为前缀表达式字符串而已算法时间复杂度取决于输入的字符串的长度n即O n 空间复杂度为O 2ns 整体的算法设计没有什么可取之处对于减少时间复杂度和空间复杂度上没有什么细细考虑 4在调试的过程中花费时间最为多的是对输入错误表达式的出错处理更改增加的代码几乎都是为了出错处理但是觉得这样的调试才更能锻炼一个人的编程能力课程设计注重的不单单只是基本程序的完成更多注重的是出错处理和界面的美化 五用户手册 1本程序的运行环境为DOS操作系统执行文件为expressionexe 2进入演示程序后首先出现一个主菜单主菜单界面如下 3之后输入你的选择进入你所要进行的操作中 六测试 《一》选择1进入测试输入正确的前缀表达式操作 1输入的前缀表达式为一个不大于9常量8 2输入前缀表达式为一个变量Z 3输入前缀表达式为一个简单的运算表达式-91 4输入前缀表达式为一个较为复杂的带有变量的表达式3x32x2x6 5输入前缀表达式-23ab34输出带括弧的表达式 6输入错误的前缀表达式999和5x28x 《二》选择3进入测试对变量的赋值 1对前缀表达式3x32x2x6中变量x进行赋值赋值为5 2对前缀表达式abc中的变量b进行赋值赋值为6 3对前缀表达式5x28x中不存在的变量y进行赋值赋值为4 《三》选择4进入测试求算数表达式的值 1求算数表达式98的值 2求算数表达式659892 21-96 输出的结果少了括弧这个是程序中的一个BUG程序的判定带括弧输出表达 式时判断两个优先级别时的一个很大的BUG一个本人自己没法解决的BUG 2构造表达式 32 9 - 63 91 8183 输出的结果简化了多余的括弧这一点是一个很大的优化 3构造表达式66出错处理 4构造表达式6-b99出错处理 5构造表达式9a 65 a出错处理多余输入的括弧 6构造表达式6986出错处理输入非运算符和非变量常量的表达式 《六》选择7进入合并常数操作 1构造表达式 23-a b34 后合并常数操作 2构造表达式334经过多次合并得出最后结果 这个合并常数操作唯一的缺点就是要多次操作但是这个缺点也不能说为缺 点它可以很清晰的反映出表达式求值的步骤 经过对各个操作的测试可以这样总结的说基本完成了课程设计的要求虽说 其中有一些操作还存在BUG需要去完善改进 七课程设计的心得和体会以及问题 此次课程设计相对于我来说难度适中相对于这个学期写的那些小算法来说这个课程设计能充分发挥出学习数据结构后的能力而相对于之前做的设计性实验又有了实际的应用现实应用度增加 从接触C语言编程到现在我就觉得编程不是简简单单的写出程序更多的是出错处理和界面设计这次课程设计中更让我深刻体会到这个道理编出大体的程序架构花费了我的时间不多而花费了我很多时间的是在调试和测试数据上这次课程设计不仅训练了我对Visual C60的调试器的操作的熟练度而且让我在发现问题解决问题中深刻地理解到完善程序的重要性 这次课程设计在技术上的学习上我觉得让我更懂得递归递归的使用更加熟练递归的分析更加清晰递归的思想更加深化 做课程设计我觉得第一点是架构一个好的架构可以让细节更完善在这次课程设计中我首先确定的是一个架构前缀表达式构造表达式为架构其余的操作都是在这个架构上增加扩充第二点是调试测试分析一个完善的程序是要经过千锤百炼的也能做到更加完善第三点是心得的总结 总的来说这次课程设计让我学了很多总结了很多 八参考文献 严蔚敏吴伟民著数据结构C语言版北京清华大学出版社2007 谭浩强著C程序设计第三版北京清华大学出版社2005 九附录程序清单 源程序文件名清单 expressionh 包含头文件存储结构的声明以及两个顺序栈的基本操作 exprssionc 包含主程序和表达式的基本操作 《一》文件expressionh 头文件以及存储结构 include include include include define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define OVERFLOW 0 typedef int Status 二叉树结点类型 typedef enum INTCHAR ElemTagINT为整型数据numCHAR为字符型数据c typedef struct TElemType ElemTag tag INTCHAR 指示是整型还是字符型 union int numtag INT时为整型 char ctag CHAR时为字符型 TElemType 二叉树的二叉链表存储表示 typedef struct BiTNode TElemType data struct BiTNode lchildrchild 左右孩子指针 BiTNodeBiTree typedef BiTree SElemType栈SqStack的元素 typedef char SElemType1 栈SqStack1的元素 栈的顺序存储表示 define STACK_INIT_SIZE 10 存储空间初始分配量 define STACKINCREMENT 2 存储空间分配增量 两个顺序栈 typedef struct SqStack SElemType base 在栈构造之前和销毁之后base的值为NULL SElemType top 栈顶指针 int stacksize 当前已分配的存储空间以元素为单位 SqStack 顺序栈 typedef struct SqStack1 SElemType1 base 在栈构造之前和销毁之后base的值为NULL SElemType1 top 栈顶指针 int stacksize 当前已分配的存储空间以元素为单位 SqStack1 顺序栈 顺序栈的基本操作 Status InitStack SqStack S 构造一个空栈S S base SElemType malloc STACK_INIT_SIZEsizeof SElemType if S base exit OVERFLOW 存储分配失败 S top S base S stacksize STACK_INIT_SIZE return OK Status StackEmpty SqStack S 若栈S为空栈则返回TRUE否则返回FALSE if Stop Sbase return TRUE else return FALSE Status Push SqStack SSElemType e 插入元素e为新的栈顶元素 if S top- S base S stacksize 栈满追加存储空间 S base SElemType realloc S base S stacksizeSTACKINCREMENT sizeof SElemType if S base exit OVERFLOW 存储分配失败 S top S base S stacksize S stacksize STACKINCREMENT S top e return OK Status Pop SqStack SSElemType e 若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR if S top S base return ERROR e -- S top return OK Status GetTop SqStack SSElemType e 若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR if Stop Sbase e Stop-1 return OK else return ERROR 顺序栈的基本操作 Status InitStack1 SqStack1 S 构造一个空栈S S base SElemType1 malloc STACK_INIT_SIZEsizeof SElemType1 if S base exit OVERFLOW 存储分配失败 S top S base S stacksize STACK_INIT_SIZE return OK Status StackEmpty1 SqStack1 S 若栈S为空栈则返回TRUE否则返回FALSE if Stop Sbase return TRUE else return FALSE Status Push1 SqStack1 SSElemType1 e 插入元素e为新的栈顶元素 if S top- S base S stacksize 栈满追加存储空间 S base SElemType1 realloc S base S stacksizeSTACKINCREMENT sizeof SElemType1 if S base exit OVERFLOW 存储分配失败 S top S base S stacksize S stacksize STACKINCREMENT S top e return OK Status Pop1 SqStack1 SSElemType1 e 若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR if S top S base return ERROR e -- S top return OK Status GetTop1 SqStack1 SSElemType1 e 若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR if Stop Sbase e Stop-1 return OK else return ERROR 《二》文件expressionc include"expressionh" 全局变量 int save_number[31]在按原表达式输入形式中输入的常量保存到数组 save_number中常量最多为30个0单元不用 char Expr_String[30]存放表达式的字符串 以字符序列的形式输入语法正确的前缀表达式保存到字符串string 参数flag 0表示输出的提示信息是"请输入正确的前缀表示式" flag 1表示输出的提示信息为"请以表达式的原书写形式输入正确表示 式" Status Input_Expr char stringint flag if flag 0 printf "\n请输入正确的前缀表示式" else printf "\n请以表达式的原书写形式输入正确表示式" flushall 清理缓冲区 gets string 从键盘输入一串字符串作为表达式 if strlen string 1 输入的表达式字符串长度为1 if string[0] string[0] -string[0] string[0] string[0] 输入的表达式只有一个运算符 printf "\n表达式只有一个字符为运算符错误" return ERROR else if string[0] 0string[0] 9 string[0] astring[0] z string[0] Astring[0] Z 输入的表达式只有一个数字或字符 printf "\n表达式只有一个字符" return OK else printf "\n输入的字符不是运算符也不是变量常量错误" return ERROR return OK 判断字符string[i]如果是0-9常量之间二叉树结点存为整型否则存为 字符型 void judge_value BiTree Echar stringint i if string[i] 0string[i] 9 为常量 E - datatag INT E - datanum string[i]-48 else if string[i] 1string[i] 20 为常量常量存于数组 save_number中 E - datatag INT E - datanum save_number[string[i]] else为变量 E - datatag CHAR E - datac string[i] 以正确的前缀表示式并构造表达式E Status ReadExpr BiTree Echar exprstring SqStack S int ilenlen为表达式的长度 BiTree pq E BiTree malloc sizeof BiTNode 申请二叉树的根结点的空间 E - lchild NULL E - rchild NULL len strlen exprstring len赋值为表达式的长度 if len 1 表达式长度为1时二叉树只有根结点 judge_value Eexprstring0 将exprstring[0]存入二叉树的结 点中 else judge_value Eexprstring0 将exprstring[0]存入二叉树的结 点中 InitStack S 初始化栈 q E Push Sq 入栈 Push Sq 入栈根结点入栈两次是为判断先序输入的表达式是不是正确的表达式 for i 1i lenStackEmpty S i p BiTree malloc sizeof BiTNode judge_value pexprstringi 将exprstring[i]存入二叉树的结点中 p- lchild NULL p- rchild NULL if exprstring[i] exprstring[i] -exprstring[i] exprstring[i] exprstring[i] 为运算符运算符入栈左孩子不空向左孩子走否则如果右孩子不空向右孩子走 if q- lchild q- lchild pPush Sp q p else q- rchild pPush Sp q p else不是运算符运算符出栈 if q- lchild q- lchild pPop Sq else q- rchild pPop Sq if StackEmpty S i len return OK栈空且i len说明输入的表达式是正确的 else 输入的表达式是错误的 printf "\n输入的表达式有误" return ERROR 如果两个字符是运算符比较两个运算符的优先级c1比c2优先返回OK否则返回ERROR Status Pri_Compare char c1char c2 if c1 c1 c1 -c1 c1 c2 c2 c2 -c2 c2 c1和c2为运算符 if c1 c1为指数运算符则当c2不为时c1比c2优先 if c2 return OK else return ERROR else if c1 c1 c1为乘法或除法运算符则当c2为或-c1比c2优先 if c2 c2 c2 return ERROR else return OK else return ERROR其余c1不比c2优先 else return ERRORc1和c2不是运算符 用带括弧的中缀表达式输入表达式 void WriteExpr BiTree E if E 树不为空 先递归左子树 if E- lchildE- lchild- datatag CHAR E的左孩子不为空且左孩子为字符 if Pri_Compare E- datacE- lchild- datac E- datac比E- lchild- datac优先 printf " " WriteExpr E- lchild printf " " 带括弧输出左子树 else WriteExpr E- lchild 否则不带括弧输出左子树 else WriteExpr E- lchild 否则输出左子树 访问输出根结点的值 if E- datatag INT printf "d"E- datanum else printf "c"E- datac 后递归右子树 if E- rchildE- rchild- datatag CHAR E的右孩子不为空且右孩子为字符 if Pri_Compare E- datacE- rchild- datac E- datac比E- rchild- datac优先 printf " " WriteExpr E- rchild printf " " 带括弧输出右子树 else WriteExpr E- rchild 否则不带括弧输出右子树 else WriteExpr E- rchild 否则输出右子树 实现对表达式中的所有变量V的赋值 V c 参数flag为表示是否赋值过的标志 void Assign BiTree Echar Vint cint flag if E if E - datatag CHAR E - datac V 如果找到要赋值的变量 赋值 E - datatag INT E - datanum cflag 1 Assign E - lchild Vcflag 递归左子树 Assign E - rchild Vcflag 递归左子树 指数运算函数底数为x指数为exp long power int xint exp long result int i for i 1result 1i expi result x return result 运算符运算求值参数opr1opr2为常量opr为运算符根据不同的运算符实 现不同的运算返回运算结果 long Operate int opr1char oprint opr2 long result switch opr case 加法 result opr1opr2 return resultbreak case -减法 result opr1-opr2 return resultbreak case 乘法 result opr1opr2 return resultbreak case 除法除法是在整型类型上的除法 result opr1opr2 return resultbreak case 指数运算 result power opr1opr2 return resultbreak defaultbreak 检查表达式是否还存在没有赋值的变量以便求算数表达式的值 Status Check BiTree E if EE- datatag CHAR 树不为空 if E- datac E- datac E- datac -E- datac E- datac printf "\n表达式中仍存在变量没有赋值没法求出表达式 的值" return ERROR 存在变量提示信息后返回ERROR if Check E- lchild 递归左子树 Check E- rchild 递归右子树 对算术表达式求值 long Value BiTree E if E 树不为空 if E- lchildE- rchildE- datatag INT return E- datanum 结点的左孩子和右孩子为空为叶子结点返回结点的值 return Operate Value E- lchild E- datacValue E- rchild 运算求值后根遍历的次序对表达式求值其中参数递归调用了 Value 函数求左子树的值和右子树的值 构造一个新的复合表达式 void CompoundExpr char PBiTree E1BiTree E2 BiTree E E BiTree malloc sizeof BiTNode 申请一个结点存放运算符P E- datatag CHAR E- datac P申请到的结点值为P E- lchild E1 结点的左孩子为E1 E- rchild E2结点的右孩子为E2 E1 E E1 为根结点 printf "\n表达式E复合成功其表达式变为\n" WriteExpr E 输出复合好的表达式 以表达式的原书写形式输入表达式的原书写形式字符串string变为字 符串pre_expr 后调用reversal_string 函数反转得到前缀表达式pre_expr Status Read_Inorder_Expr char stringchar pre_expr int ijlenchar_number 1len表示字符串string的长度char_number 是 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 数组save_number[]的个数 int number保存大于9的常量 char cc1 SqStack1 S栈定义 InitStack1 S 初始栈 Push1 S 先将字符入栈用来表示作为栈的最底一个元素 len strlen string len为字符串string的长度 c string[len-1]从字符串的最后一个字符开始向前扫描 i len-1 while StackEmpty1 S i 0 栈不为空且i大于等于0 if c 字符为 Pop1 Sc 出栈赋值给c while c 假如c不为 出栈 pre_expr c if StackEmpty1 S GetTop1 Sc1 c1 Pop1 Sc else printf "\n输入的表达式有误" return ERROR else if c 字符为 入栈 Push1 Sc else if c 0c 9 字符为0-9之间循环扫描string前一个字符后确定常量的大小 number c-48number为第一个常量字符的ASCII码-48 for c1 string[i-1]j 1 c1 0c1 9 i 0ji-- 循环扫描string前一个字符求出常量后 赋给number number c1-48 power 10j numbernumber为扫描到的常量 c1 string[i-2] save_number[char_number] number将number存入到数组save_number中下标为 char_number pre_expr char_number else if c ac z c Ac Z 字符为a-z或A-Z之间的变量 string下一个字符不能为常量或变量否则出错 if string[i-1] 0string[i-1] 9 string[i-1] Astring[i-1] Z string[i-1] astring[i-1] z printf "\n输入的表达式有误" return ERROR else pre_expr c else if c c 字符为运算符或 while GetTop1 Sc1 c1 将c与栈顶的字符c1比较优先 级 Pop1 Sc1 pre_expr c1 如果c1比c优先出栈 Push1 Sc 入栈字符c else if c c - 字符为运算符或- while GetTop1 Sc1 c1 c1 c1 将c与栈顶的字符c1 比较优先级 Pop1 Sc1 pre_expr c1 如果c1比c优先出栈 Push1 Sc 入栈运算符c else if c 字符为运算符 Push1 Sc 入栈运算符 else printf "\n输入的表达式有误" return ERROR 其他字符 错误返回ERROR i--下一个字符 if i 0 c string[i]i不小于0c string[i]循环下一个字符 else 否则将清空栈 while StackEmpty1 S GetTop1 Sc1 c1 Pop1 Sc pre_expr c Pop1 Sc 将出栈 pre_expr \0字符串结束符 if i 0StackEmpty1 S return OK else return ERROR 将字符串exprstring反转过来 void reversal_string char exprstring int lenij char temp len strlen exprstring len为exprstring的长度 for i 0j len-1i jij-- 字符串前后两个字符对换 temp exprstring[i] exprstring[i] exprstring[j] exprstring[j] temp 常数合并操作函数合并表达式E中所有常数运算 void MergeConst BiTree E long result if E - lchild E - rchild 左右孩子不为空 if E - lchild- datatag INT E - rchild- datatag INT 假如左右孩子为常量合并 result Operate E - lchild- datanum E - datac E - rchild- datanum 常数合并运算调用 Operate 函数求值 E - datatag INT E - datanum result修改之前的运算符为常量 free E - lchild 释放左孩子 free E - rchild 释放右孩子 E - lchild E - rchild NULL左右孩子置空 else MergeConst E - lchild 递归左孩子 MergeConst E - rchild 递归右孩子 主菜单 char menu char choice printf "\n\t" printf "\n\t 计算机学院 计算机科学与技术06级01班" printf "\n\t 学号3106006394 姓名方锐洲" printf "\n\t" printf "\n\t表达式类型的实现" printf "\n\t 1 输入正确的前缀表达式" printf "\n\t 2 带括弧的中缀表示式输出" printf "\n\t 3 对变量进行赋值" printf "\n\t 4 对算数表达式求值" printf "\n\t 5 构造一个新的复合表达式" printf "\n\t 6 以表达式的原书写形式输入" printf "\n\t 7 合并表达式中所有常数运算" printf "\n\t 0 退出" printf "\n\t" printf "\n\t请输入你的选择 " choice getche return choice 主函数 void main BiTree EE1两个表达式E和E1 int flag 0表达式E构造标志为0表示未构造为1表示已构造 long result保存算数表达式运算结果 char VP int c char string[30] while 1 system "cls" switch menu case 11 输入正确的前缀表达式 printf "\n\t输入提示信息" printf "\n\t输入正确的前缀表达式的要求" printf "\n\t\t变量 a-z或A-Z" printf "\n\t\t常量 0-9不能超过9" printf "\n\t\t运算符 - 乘幂 " printf "\n\t请输入正确的前缀表达式后按回车键存入缓冲区否则可能会出错" printf "\n\t" if Input_Expr Expr_String0 if ReadExpr EExpr_String flag 1printf "\n表达式构造成功\n输入的带括弧的中缀表达式" WriteExpr E getch break case 22 带括弧的中缀表示式输出 printf "\n\t输出说明信息" printf "\n\t输出带括弧的中缀表达式" printf "\n\t1如果表达式已经构造成功的输出表达式" printf "\n\t2如果表达式还未构造成功的请返回主菜单选择构造表达式" printf "\n\t注其中要注意的是可能有一些表达式构造时没有办法判断为有误" printf "\n\t 如果输出不是你想得到的说明你之前输入的表达式有误请重新构造" printf "\n\t" if flag 1 printf "\n带括弧的中缀表达式为" WriteExpr E else printf "\n表达式未构造成功请构造成功的表达式" getch break case 33 对变量进行赋值 printf "\n\t赋值操作说明信息" printf "\n\t赋值操作实现对表达式中的某一个变量V的赋值即使V CC为一整数" printf "\n\t 1根据输出的表达式输入要赋值的变量V只能输入一个字符否则出错" printf "\n\t 2输入要将变量V赋值为的整数C只能是整数否则出错" printf "\n\t 注如果表达式未构造请回到主菜单选择构造表达式" printf "\n\t" if flag 1 int Assign_flag 0 printf "\n表达式E为" WriteExpr E flushall 清理缓冲区 printf "\n请输入要赋值的值" V getchar printf "请输入要将赋值为" scanf "d"c Assign EVcAssign_flag if Assign_flag printf "\n赋值成功\n赋值后的表达式为" WriteExpr E else printf "\n表达式里没有c这个变量"V else printf "\n表达式未构造成功请构造成功的表达式" getch break case 44 对算数表达式求值 printf "\n\t算数表达式求值说明信息" printf "\n\t 注如果表达式还有变量未赋值即表达式不是算数表达式" printf "\n\t 不能求出表达式的值请回到主菜单选择赋值操作后再求值" printf "\n\t" if flag 1 printf "\n算数表达式" WriteExpr E if Check E result Value E printf "\n求算数表达式的值\t" WriteExpr E printf " ld"result else printf "\n表达式未构造成功请构造成功的表达式" getch break case 55 构造一个新的复合表达式 printf "\n\t构造新的复合表达式说明信息" printf "\n\t 1构造一个新的表达式E1采用表达式的原书写形式输入" printf "\n\t 2构造表达式E1成功后输入要复合表达式E和E1的操作运算符 - " printf "\n\t 注如表达式E未构造不能复合表达式如构造表达式E1错误复合失败" printf "\n\t" if flag 1 printf "\n表达式E1为" WriteExpr E printf "\n请构造新的表达式E2" flushall 清理缓冲区 if Input_Expr string1 if Read_Inorder_Expr stringExpr_String reversal_string Expr_String if ReadExpr E1Expr_String flag 1printf "\n表达式E1构造成功" WriteExpr E1 printf "\n请输入要构造新的复合表达式的操作运算符 " P getchar while P P P P -P flushall 清理缓冲区 printf "\n输入的操作运算符有误请重新输入 " P getchar CompoundExpr PEE1 else printf "\n复合新的表达式失败请按任意键返回主菜单" else printf "\n表达式未构造成功请构造成功的表达式" getch break case 66 以表达式的原书写形式输入 printf "\n\t以表达式的原书写形式输入说明信息" printf "\n\t输入正确的原书写形式表达式" printf "\n\t 变量 a-z或A-Z" printf "\n\t 常量 大于等于0的正整数" printf "\n\t 运算符 - 乘幂 " printf "\n\t 括弧 左括弧 右括弧 " printf "\n\t 注 表示式中常量最多只能是30个超过30个出错" printf "\n\t按原书写形式输入中请按照正确的方式输入否则可能会出错" printf "\n\t" if Input_Expr string1 if Read_Inorder_Expr stringExpr_String reversal_string Expr_String if ReadExpr EExpr_String flag 1printf "\n表达式构造成功\n输入的带括弧的中缀表达式" WriteExpr E getch break case 77 合并表达式中所有常数运算 printf "\n合并表达式中的所有常数运算" printf "\n 注合并表达式中的所有常数运算并不能一次性将常数都合并" printf "\n例如表达式12 33493 的常数合并选择7进行合并结果变为\n12 3123 " printf "根据优先级先后合并的如果要合并到最后需多次选择7\n进行合并又合并一次12 153 " printf "再次合并1218再次合并136\n再次合并37后无法合并" printf "\n" if flag 1 printf "\n原表达式为" WriteExpr E MergeConst E printf "\n合并表达式中所有的常数运算后的表达 式" WriteExpr E else printf "\n表达式未构造成功请构造成功的表达 式" getch break case 00 退出 printf "\n请按任意键退出" getch exit 0 default printf "\n输入有误请按任意键回到主菜单重新选择" getch break 数据结构课程设计报告 第 2 页 共 35 页 主程序模块 二叉树模块 顺序栈SqStack模块 顺序栈SqStack1模块 Status ReadExpr BiTree Echar exprstring 以正确的前缀表示式并构造表达式E 申请根结点空间 E BiTree malloc sizeof BiTNode 并且左右孩子指 针置空 表达式只有一个字符二叉树只有根结点 否则 judge_value Eexprstring0 将exprstring[0]存入二叉树的结点中 InitStack S 初始化栈 Push Sq Push Sq 入栈根结点入栈两次是为判断先序输入的表达式是不是正确的表达式 for i 1i lenStackEmpty S i 申请根结点空间p BiTree malloc sizeof BiTNode 并且左右孩子指针置空 if exprstring[i]为运算符 运算符入栈左孩子不空向左孩子走否则如果右孩子不空向右孩子走 else 不是运算符运算符出栈 根据StackEmpty S i len判断输入的表达式是正确的 正确返回OK错误返回ERROR void WriteExpr BiTree E 用带括弧的中缀表达式输入表达式 if E 树不为空 先递归左子树 WriteExpr E- lchild 其中要考虑何时带括弧输出 if Pri_Compare E- datacE- lchild- datac E- datac比E- lchild- datac优先带括弧输出左子树 访问输出根结点的值 后递归右子树 WriteExpr E- lchild 其中要考虑何时带括弧输出 if Pri_Compare E- datacE- lchild- datac E- datac比E- lchild- datac优先带括弧输出右子树 void Assign BiTree Echar Vint cint flag 实现对表达式中的所有变量V的赋值 V c 参数flag为表示是否赋值过的 标志 if E 树不空 if E - datatag CHAR E - datac V 如果找到要赋值的变量赋值flag 1 Assign E - lchild Vcflag 递归左子树 Assign E - rchild Vcflag 递归左子树 long Operate int opr1char oprint opr2 运算符运算求值参数opr1opr2为常量opr为运算符根据不同的运算符实现 不同的运算返回运算结果 switch opr 根据不同的运算符进入不同分支求出result 后返回result Status Check BiTree E 检查表达式是否还存在没有赋值的变量以便求算数表达式的值 if EE- datatag CHAR 树不为空 如果找到没有赋值的变量返回ERROR if Check E- lchild 递归左子树 Check E- rchild 递归右子树 long Value BiTree E 对算术表达式求值 if E 树不为空 如果是叶子结点返回叶子的结点的值 return Operate Value E- lchild E- datacValue E- rchild 后根遍 历的次序对表达式求值 void CompoundExpr char PBiTree E1BiTree E2 构造一个新的复合表达式 E BiTree malloc sizeof BiTNode 申请一个结点存放运算符P E- lchild E1 结点的左孩子为E1 E- rchild E2结点的右孩子为E2 E1 E E1 为根结点 Status Read_Inorder_Expr char stringchar pre_expr 以表达式的原书写形式输入表达式的原书写形式字符串string变为字符 串pre_expr后调用reversal_string 函数反转得到前缀表达式pre_expr InitStack1 S 初始栈 c string[len-1]从字符串的最后一个字符开始向前扫描 len strlen string while StackEmpty1 S i 0 栈不为空且i大于等于0 if c 字符为 Pop1 Sc while c 假如c不为 出栈 else if c 字符为 入栈 Push1 Sc else if c 0c 9 字符为0-9之间循环扫描string前一个字符后确定常量的大小 else if c ac z c Ac Z 字符为a-z或A-Z之间的变量 else if c c 字符为运算符或 比较优先级后确定是入栈还是出栈 else if c c - 字符为运算符或- 比较优先级后确定是入栈还是出栈 else if c 字符为运算符 优先级最大不用比较直接入栈 else printf "\n输入的表达式有误" return ERROR 其他字符错误返回ERROR 下一个字符继续循环 pre_expr \0字符串结束符 判断构造是否成功成功返回OK否则返回ERROR void MergeConst BiTree E 常数合并操作函数合并表达式E中所有常数运算 if E - lchild E - rchild 左右孩子不为空 if E - lchild- datatag INT E - rchild- datatag INT 假如左右孩子为常量合并并且删除常量的结点 else MergeConst E - lchild 递归左孩子 MergeConst E - rchild 递归右孩子