表达式类型的实现——实习报告一．需求分析1.编写一个程序，通过前缀表达式来构造一个与之对应的算术表达式并存入二叉树中，通过中序遍历二叉树输出表达式及对其进行变量赋值，通过后序遍历二叉树计算表达式的值。2.本程序功能有：存储表达式、对表达式进行赋值计算、求偏导、计算三角函数、合并常数及接受原书写形式的表达式。3.测试数据（1）.分别输入0;a;-91;+a*bc;+*5^x2*8x;+++*3^x3*2^x2x6并输出。（2）.每输入一个表达式，对其中的变量进行赋值，再对表达式求值。二．概要设计按照要求，需要以二叉树来存储表达式，但在构造过程中还需要用到栈来实现前缀表达式与二叉树之间的转换。1.抽象数据类型栈的定义：ADTSqStack{数据对象：D={ai|ai为整型或字符型}数据关系：R={<ai,ai-1>|ai,ai-1∈D}基本操作：StatusInitStack(SqStackS);此函数用于创建一个空栈StatusStackEmpty(SqStackS);此函数用于判断栈是否为空StatusStackFull(SqStackS);此函数用于判断栈是否已满StatusPush(SqStackS,SElemTypee);将数据元素e入栈StatusPop(SqStackS,SElemTypee);出栈，并以e返回出栈的元素StatusGetTop(SqStackS,SElemTypee);若栈不空，则以e返回栈顶元素}ADTSqStack2.二叉树表达式数据类型ATDBiTNode{数据对象：D={ai|ai∈SqStack}数据关系：R={<ai,ai-1>|ai,ai-1∈D}基本操作：StatusInputExpr(char*string,intflag);以字符串形式读取输入voidJudgeValue(BiTree*E,char*string,inti);判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点存为整型；否则，存为字符型StatusReadExpr(BiTree*E,char*exprstring);以正确的前缀表示式并构造表达式EStatusPriCmp(charc1,charc2);如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERRORvoidWriteExpr(BiTreeE);用带括弧的中缀表达式输出表达式voidAssign(BiTree*E,charV,intc,int*flag);实现对表达式中的所有变量V的赋值(V=c)，参数flag为表示是否赋值过的标志longOperate(intopr1,charopr,intopr2);运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果doubleOperate1(charopr,doubleopr1);三角函数运算求值，参数opr为常量，opr1为运算符，根据不同的运算符，实现不同的运算，返回运算结果StatusCheck(BiTreeE);检查表达式是否还存在没有赋值的变量，以便求算数表达式的值longValue(BiTreeE);对算术表达式求值voidCompoundExpr(charP,BiTreeE1,BiTreeE2);构造一个新的复合表达式StatusReadInorderExpr(char*string,char*pre_expr);以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_exprvoidReversalString(char*exprstring);将字符串exprstring反转过来voidMergeConst(BiTree*E);常数合并操作函数，合并表达式E中所有常数运算intIsOperator(charc);判断是否操作符voidDiff(BiTreeE,charv);求偏导数}ADTBiTNode3.主程序intmain(){while(TRUE){判断用户选择的操作；执行所选操作，并适时提示用户输入及输出运算结果；若用户选择退出，则执行exit(0)退出程序；}；4.程序调用关系：主程序模块表达式计算单元模块栈操作模块三．详细设计1.数据类型：二叉树数据类型：typedefenum{INT,CHAR}ElemTag;/*INT为整型数据num，CHAR为字符型数据c*/typedefstructTElemType{ElemTagtag;/*{INT,CHAR}指示是整型还是字符型*/intnum;/*tag=INT时，为整型*/charc;/*tag=CHAR时，为字符型*/}TElemType;二叉树节点类型：typedefstructBiTNode{TElemTypedata;/*二叉树存储的数据*/structBiTNode*lchild,*rchild;/*左右孩子指针*/}BiTNode,*BiTree;2.函数实现：（以伪码表示）StatusInputExpr(char*string,intflag)//此函数用于表达式的输入与存储{if(flag==0)cout<<"\n请输入正确的前缀表示式：";elsecout<<"\n请以表达式的原书写形式输入正确表示式：";fflush(stdin);/*清理缓冲区*/gets(string);/*从键盘输入一串字符串作为表达式*/if(strlen(string)==1)/*输入的表达式字符串长度为1*/if(string[0]...