一、需求分析【课程设计要求】 【问题的描述】
一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现
基于二叉树表示的算术表达式Expression的操作。
【基本要求】
【一】【必做部分】
假设算术表达式Expression内可以含有变量（a-z）,常量（0-9）和二元运算符（+，-，*，/，^（乘幂））。实现以下操作：
（1）ReadExpr(E)――以字符序列的形式输入语法正确的前缀表达式并构造表达式E。
（2）WriteExpr(E)――用带括号的中缀表达式输出表达式E。 （3）Assign(V，c)――实现对变量V的赋值（V=c），变量的初值为0。 （4）Value(E)――对算术表达式E求值。
（5）CompoundExpr(p,E1,E2)――构造一个新的复合表达式（E1）p（E2）。 【二】【选做部分】
（1）以表达式的原书写形式输入，支持大于0的正整数常量；
（2）增加常数合并操作MergeConst(E)——合并表达式E中所有常数运算。例如，对表达式E=(2+3-a)*(b+3*4)进行合并常数的操作后，求得E=(5-a)*(b+12) (3)增加对求偏导数的运算Diff（E，V）——求表达式E对V的导数 (4)在表达式内增加对三角函数等初等函数的操作。
【测试数据】
(1)分别输入0；a;-91;+a*bc;+*5x2*8x;+++*3^*2^x2x6并输出。 （2）每当输入一个表达式后，对其中的变量赋值，然后对表达式求值
二 、【整体算法思想】
一个表达式和一棵二叉树之间存在一一对应的关系。本程序我主要用前缀表
达式建树，中序遍历并适当加括号实现中缀输出。具体操作即对树的程序进行处理，再输出。
三、【概要设计】 1、数据类型的声明：
在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构
/*头文件以及存储结构*/ #include - - 1 #include 2、表达式的抽象数据类型定义 ADT Expression{ 数据对象D：D是具有数值的常量C和没有数值的变量V； 数据关系：R={<(V或者C)P(V或者C)>|V,C∈D, <(V或者C)P(V或者C)>表示由运算符P结合起来的表达式E} 基本操作： Status Input_Expr(&string,flag) 操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string； 参数flag表示输出的提示信息是什么，输入成功返回OK，否则，返回ERROR。 void judge_value(&E,&string,i) 初始条件：树E存在，表达式的前缀字符串string存在； 操作结果：判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点E存为整型；否则，存为字符型。 Status ReadExpr(&E,&exprstring) 初始条件：表达式的前缀形式字符串exprstring存在； 操作结果：以正确的前缀表示式exprstring并构造表达式E，构造成功，返回OK，否则返回ERROR。 Status Pri_Compare(c1,c2) 初始条件：c1和c2是字符； 操作结果：如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR。 void WriteExpr(&E) 初始条件：表达式E存在； 操作条件：用带括弧的中缀表达式输入表达式E。 void Assign(&E,V,c,&flag) 初始条件：表达式E存在，flag为标志是否有赋值过； 操作结果：实现对表达式E中的所有变量V的赋值(V=c)。 long Operate(opr1,opr,opr2) 初始条件：操作数opr1和操作数opr2以及操作运算符opr; 操作结果：运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果。 Status Check(E) 初始条件：表达式E存在； - - 2 操作结果：检查表达式E是否还存在没有赋值的变量，以便求算数表达式E的值。 long Value(E) 初始条件：表达式E存在； 操作结果：对算术表达式求值，返回求到的结果。 void CompoundExpr(P,&E1,E2) 初始条件：表达式E1和E2存在； 操作条件：构造一个新的复合表达式(E1)P(E2)。 Status Read_Inorder_Expr(&string,&pre_expr) 操作结果：以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr。得到正确的前缀表达式返回OK，否则，返回ERROR。 void MergeConst(&E) 操作结果：常数合并操作，合并表达式E中所有常数运算。 }ADT Expression 3、整体设计 在这个课程设计中，有两个源代码文件：expression.h和expression.c。 在expression.h文件中，包含了各个存储结构的声明和辅助存储结构的两个栈的基本操作；在expression.c文件中，是实现课程设计要求的各个函数。 《一》expression.h文件的整体结构 1、各个存储结构的声明； 2、两个除了栈名和栈存储的元素不一样的顺序栈的基本操作。其基本操作如下： 对于栈SqStack: Status InitStack(SqStack *S) /* 构造一个空栈S */ Status StackEmpty(SqStack S) /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ Status Push(SqStack *S,SElemType e) /* 插入元素e为新的栈顶元素 */ Status Pop(SqStack *S,SElemType *e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ Status GetTop(SqStack S,SElemType *e) /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */ 对于栈SqStack1: Status InitStack1(SqStack1 *S) /* 构造一个空栈S */ Status StackEmpty1(SqStack1 S) /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ Status Push1(SqStack1 *S,SElemType1 e) /* 插入元素e为新的栈顶元素 */ Status Pop1(SqStack1 *S,SElemType1 *e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ Status GetTop1(SqStack1 S,SElemType1 *e) /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */ 顺序栈的基本操作的算法见程序清单。 《二》expression.c文件的整体结构 1、主程序模块的整体流程 可以从主菜单函数可以明了的了解的程序的整体流程，主菜单函数menu()如下： - - 3 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、本程序有四个模块，主程序模块，二叉树模块，两个顺序栈模块。四者的调用关系如下： 主程序模块 二叉树模块 顺序栈SqStack1模块 顺序栈SqStack模块 - - 4 主程序模块中的对于表达式的存储结构调用了二叉树模块，而在构造表达式的二叉树模块中又调用了顺序栈SqStack模块，主程序中在将原表达式形式输入表达式转换为前缀表达式操作中调用了顺序栈SqStack1模块。 四、【详细设计】 1、二叉树的存储类型 /*二叉树结点类型*/ typedef enum{INT,CHAR}ElemTag;/*INT为整型数据num，CHAR为字符型数据c*/ typedef struct TElemType { ElemTag tag;/*{INT,CHAR}指示是整型还是字符型*/ union { int num;/*tag=INT时，为整型*/ char c;/*tag=CHAR时，为字符型*/ }; } TElemType; /*二叉树的二叉链表存储表示 */ typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指针 */ }BiTNode,*BiTree; 二叉树的基本操作已经在构造表达式和表达式中的基本操作中根据不同的功能和实际情况修改了，详细见各个函数操作的算法设计。 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; /* 当前已分配的存储空间，以元素为单位 */ - - 5 }SqStack1; /* 顺序栈SqStack1 */ 相关的基本操作见上面的“expression.h文件的整体结构”的说明，详细的算法设计见附录的程序清单。 3、表达式的基本操作 Status Input_Expr(char *string,int flag); /*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/ /*参数flag=0表示输出的提示信息是\"请输入正确的前缀表示式：\"*/ /*flag=1表示输出的提示信息为\"请以表达式的原书写形式输入正确表示式：\"*/ void judge_value(BiTree *E,char *string,int i); /*判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点存为整型；否则，存为字符型*/ Status ReadExpr(BiTree *E,char *exprstring); /*以正确的前缀表示式并构造表达式E*/ Status Pri_Compare(char c1,char c2); /*如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR*/ void WriteExpr(BiTree E); /*用带括弧的中缀表达式输入表达式*/ void Assign(BiTree *E,char V,int c,int *flag); /*实现对表达式中的所有变量V的赋值(V=c)，参数flag为表示是否赋值过的标志*/ long Operate(int opr1,char opr,int opr2); /*运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果*/ Status Check(BiTree E); /*检查表达式是否还存在没有赋值的变量，以便求算数表达式的值*/ long Value(BiTree E); /*对算术表达式求值*/ void CompoundExpr(char P,BiTree *E1,BiTree E2); /*构造一个新的复合表达式*/ Status Read_Inorder_Expr(char *string,char *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_String,0))输入正确的前缀表达式 - - 6 if(ReadExpr(&E,Expr_String))构造表达式 {flag=1;printf(\"\\n表达式构造成功！\");} case '2':/*带括弧的中缀表示式输出*/ if(flag==1) WriteExpr(E); else printf(\"\\n表达式未构造成功！请构造成功的表达式！\"); case '3':/*对变量进行赋值*/ if(flag==1) { flushall();/*清理缓冲区*/ V=getchar(); scanf(&c); Assign(&E,V,c,&Assign_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(string,1)) { if(Read_Inorder_Expr(string,Expr_String)) {/*按原表达式形式输入*/ reversal_string(Expr_String); if(ReadExpr(&E1,Expr_String)) { flag=1;P=getchar(); CompoundExpr(P,&E,E1); } else printf(\"\\n复合新的表达式失败！请按任意键返回主菜单！\"); } } } case '6':/*以表达式的原书写形式输入*/ if(Input_Expr(string,1)) if(Read_Inorder_Expr(string,Expr_String)) { - - 7 reversal_string(Expr_String); if(ReadExpr(&E,Expr_String)) {flag=1;printf(\"\\n表达式构造成功！\");} } case '7':/*合并表达式中所有常数运算*/ if(flag==1) MergeConst(&E); case '8'://三角函数操作 printf(\"\\n\***************************三角函数操作(选作)***************************\"); printf(\"\\n\"); printf(\"\\n\[注] 请按要求输入其中 ~代表sin !代表cos @代表tan \"); printf(\"\\n\角度用弧度表示，例如~1 即表示sin 1\"); printf(\"\\n\本操作只可求三角函数值，如需其他操作请将结果带入其它操作中\"); printf(\"\\n\输入一个字符请按回车，确保正确录入\"); printf(\"\\n\************************************************************************\"); double opr1,result1; char opr; printf(\"\\n请按要求输入\"); scanf(\"%c\ scanf(\"%lf\ result1=Operate1(opr,opr1); printf(\"结果为%f\ getch();break; case '0':/*退出*/ } } } 5、函数的调用关系 除了主函数main()外，其他各个函数相对于其它函数来说是独立的，函数的使用都由主函数main()调用使用的，可以简单的说，各个函数都是主函数下的从函数。 五、【设计分析】 1, 开始设计时我设想建树时可以设定五个域，左右孩子，标志tag, int型值域，char型值域。但是在存储时发现每个字符只需占一个域就可以，所以我又采用共同体这样节约了内存。 2. 在算法设计中，构造表达式树的时候，本来以为使用递归构造表达式会很难做到出错处理的，所以采用了顺序栈辅助构造方法，并且尽可能地对程序进行完善，出错处理。但是经过与同学的相互讨论和研究，发现自己的想法犯了很大的 - - 8 错误，递归构造表达式对于出错处理很简单也很完善，这一点让我加深了递归的使用和理解。 3.也就是三角函数问题，我最头疼的地方。首先开始运行时会出现错误，无法输出正确结果。通过网上搜索，我发现对于三角函数的定义类型必须是double，这样的话，如果要改的话，差不多改大半程序，所以我就让此功能单独出来，由提示让用户手动完成。 4、在调试的过程中，花费时间最为多的是对输入错误表达式的出错处理，更改增加的代码几乎都是为了出错处理，但是，觉得这样的调试才更能锻炼一个人的编程能力。 六、【调试分析】 1.进入演示程序主界面 2.第一次输入，需要选择1功能 《一》选择‘1’进入测试输入正确的前缀表达式操作 1、输入的前缀表达式为一个不大于9常量：‘8’ 2、输入前缀表达式为一个变量：‘Z’ 3、输入前缀表达式为一个简单的运算表达式：‘-91’ - - 9 4、输入前缀表达式为一个较为复杂的、带有变量的表达式：‘+++*3^x3*2^x2x6’ 5、输入前缀表达式‘*-+23a+b*34’，输出带括弧的表达式 6、输入错误的前缀表达式：‘+999’和‘+*5^x2*8x&’ 《二》选择‘3’进入测试对变量的赋值 1、对前缀表达式‘3*x^3+2*x^2+x+6’中变量x进行赋值，赋值为5 2、对前缀表达式‘a+b*c’中的变量b进行赋值，赋值为6 3、对前缀表达式‘5*x^2+8*x’中不存在的变量y进行赋值，赋值为4 《三》选择‘4’进入测试求算数表达式的值 - - 10 1、求算数表达式‘9+8’的值 2、求算数表达式‘（65+98）*（9^2+(21-96)）’的值 3、求仍存在变量的表达式‘3+a*9-6’的值 《四》选择‘5’进入构造新的复合表达式 1、未构造表达式E时 2、已构造了表达式E时 《五》选择‘6’进入以原表达式形式输入构造表达式 1、构造表达式‘6*a+9/b-(a+2^3)’ - - 11 输出的结果少了括弧，这个是程序中的一个BUG，程序的判定带括弧输出表达式时判断两个优先级别时的一个很大的BUG，一个本人自己没法解决的BUG。 2、构造表达式‘(((3+2)*9)-(6/3)*9+1)/8+18*3’ 输出的结果简化了多余的括弧，这一点是一个很大的优化。 3、构造表达式‘66++’，出错处理 4、构造表达式‘6+-b+9*9’，出错处理 5、构造表达式‘9+a+(6+5))*a’,出错处理多余输入的括弧 6、构造表达式‘6#9+8*6’，出错处理输入非运算符和非变量常量的表达式 《六》选择‘7’进入合并常数操作 1、构造表达式‘(2+3-a)*(b+3*4)’，后合并常数操作 2、构造表达式‘（3+3*4）*(1*2+8/2)’，经过多次合并，得出最后结果 这个合并常数操作唯一的缺点就是要多次操作，但是，这个缺点也不能说为缺点，它可以很清晰的反映出表达式求值的步骤！ 《七》选择‘8’，进入三角函数操作 - - 12 经过对各个操作的测试，可以这样总结的说，基本完成了课程设计的要求，虽说其中有一些操作还存在BUG需要去完善改进。 七、【实验心得】 1 经过这两周的编译，我感觉对二叉树的掌握更牢固了，整体上我都是用的二叉树处理实现各个功能。我感觉对于一个题目中处理函数尽量让他可以多功能中使用，这样编程效率会高一些。 2. 我开始设计的时候只考虑一个功能一个功能的实现。这样做很没有全局观念。我认为在以后的编程中一定要有全局意识，整体上构思好，有个好的数据结构，这样事半功倍。 3.编程就是要多动手 八、【参考文献】 严蔚敏，吴伟民著，数据结构（C语言版），北京：清华大学出版社，2007 - - 13 附 源代码 expression.cpp #include\"expression.h\" #include\"math.h\" #include /*全局变量*/ int save_number[51];/*在按原表达式输入形式中，输入的常量保存到数组save_number中，常量最多为50个，0单元不用*/ char Expr_String[50];/*存放表达式的字符串*/ /*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/ /*参数flag=0表示输出的提示信息是\"请输入正确的前缀表示式：\"*/ /*flag=1表示输出的提示信息为\"请以表达式的原书写形式输入正确表示式：\"*/ Status Input_Expr(char *string,int 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]>='0'&&string[0]<'9')||(string[0]>='a'&&string[0]<='z')||(string[0]>='A'&&string[0]<='Z')) /*输入的表达式只有一个数字或字符*/ { printf(\"\\n表达式只有一个字符！\");return OK;} else {printf(\"\\n输入的字符不是运算符也不是变量常量，错误！\");return ERROR;} return OK; } /*判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点存为整型；否则，存为字符型*/ void judge_value(BiTree *E,char *string,int i) { if(string[i]>='0'&&string[i]<='9')/*为常量*/ {(*E)->data.tag=INT;(*E)->data.num=string[i]-48;} - - 14 else if(string[i]>=1&&string[i]<=20)/*为常量，常量存于数组save_number中*/ {(*E)->data.tag=INT;(*E)->data.num=save_number[string[i]];} else/*为变量*/ {(*E)->data.tag=CHAR;(*E)->data.c=string[i];} } /*以正确的前缀表示式并构造表达式E*/ Status ReadExpr(BiTree *E,char *exprstring) { SqStack S;//定义顺序栈S int i,len;/*len为表达式的长度*/ BiTree p,q; (*E)=(BiTree)malloc(sizeof(BiTNode));/*申请二叉树的根结点的空间*/ (*E)->lchild=NULL; (*E)->rchild=NULL; len=strlen(exprstring);/*len赋值为表达式的长度*/ if(len==1)/*表达式长度为1时，二叉树只有根结点*/ judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/ else { judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/ InitStack(&S);/*初始化栈*/ q=(*E); Push(&S,q);/*入栈*/ Push(&S,q);/*入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式*/ for(i=1;i judge_value(&p,exprstring,i);/*将exprstring[i]存入二叉树的结点中*/ p->lchild=NULL; p->rchild=NULL; if(exprstring[i]=='+'||exprstring[i]=='-'||exprstring[i]=='*'||exprstring[i]=='/'||exprstring[i]=='^') {/*为运算符，运算符入栈，左孩子不空，向左孩子走，否则，如果右孩子不空，向右孩子走*/ if(!q->lchild) {q->lchild=p;Push(&S,p);q=p;} - - 15 else {q->rchild=p;Push(&S,p);q=p;} } else/*不是运算符，运算符出栈*/ { if(!q->lchild) {q->lchild=p;Pop(&S,&q);} else {q->rchild=p;Pop(&S,&q);} } } if(StackEmpty(S)&&i>=len) return OK;/*栈空且i>=len，说明输入的表达式是正确的*/ else /*输入的表达式是错误的*/ { printf(\"\\n输入的表达式有误！\"); return ERROR; } } } /*如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR*/ Status Pri_Compare(char c1,char 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 ERROR;/*c1和c2不是运算符*/ } /*用带括弧的中缀表达式输出表达式*/ - - 16 void WriteExpr(BiTree E) { if(E)/*树不为空*/ { /*先递归左子树*/ if(E->lchild&&E->lchild->data.tag==CHAR)/*E的左孩子不为空，且左孩子为字符*/ { if(Pri_Compare(E->data.c,E->lchild->data.c))/*E->data.c比E->lchild->data.c优先*/ {printf(\"(\"); WriteExpr(E->lchild); printf(\")\");}/*带括弧输出左子树*/ else WriteExpr(E->lchild);/*否则，不带括弧输出左子树*/ } else WriteExpr(E->lchild);/*否则，输出左子树*/ /*访问输出根结点的值*/ if(E->data.tag==INT){printf(\"%d\ else printf(\"%c\ /*后递归右子树*/ if(E->rchild&&E->rchild->data.tag==CHAR)/*E的右孩子不为空，且右孩子为字符*/ { if(Pri_Compare(E->data.c,E->rchild->data.c))/*E->data.c比E->rchild->data.c优先*/ {printf(\"(\");WriteExpr(E->rchild);printf(\")\");}/*带括弧输出右子树*/ else WriteExpr(E->rchild);/*否则，不带括弧输出右子树*/ } else WriteExpr(E->rchild);/*否则，输出右子树*/ } } /*实现对表达式中的所有变量V的赋值(V=c)，参数flag为表示是否赋值过的标志*/ void Assign(BiTree *E,char V,int c,int *flag) { if(*E) { if((*E)->data.tag==CHAR&&(*E)->data.c==V)/*如果找到要赋值的变量，赋值*/ {(*E)->data.tag=INT;(*E)->data.num=c;*flag=1;} Assign(&((*E)->lchild),V,c,flag);/*递归左子树*/ Assign(&((*E)->rchild),V,c,flag);/*递归左子树*/ - - 17 } } /*指数运算函数，底数为x，指数为exp*/ long power(int x,int exp) { long result; int i; for(i=1,result=1;i<=exp;i++) result*=x; return result; } /*运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果*/ long Operate(int opr1,char opr,int opr2) { long result; switch(opr) { case '+':/*加法*/ result=opr1+opr2; return result;break; case '-':/*减法*/ result=opr1-opr2; return result;break; case '*':/*乘法*/ result=opr1*opr2; return result;break; case '/':/*除法，除法是在整型类型上的除法*/ result=opr1/opr2; return result;break; case '^':/*指数运算*/ result=power(opr1,opr2); return result;break; default:break; } } /*运算符运算求值，参数opr为常量，opr1为运算符，根据不同的运算符，实现不同的运算，返回运算结果*/ double Operate1(char opr,double opr1) { double result1; - - 18 switch(opr) { case '~':/*正玄sin*/ result1=sin(opr1); return result1;break; case '!':/*余弦*/ result1=cos(opr1); return result1;break; case '@':/*正切*/ result1=tan(opr1); return result1;break; default:break; } } /*检查表达式是否还存在没有赋值的变量，以便求算数表达式的值*/ Status Check(BiTree E) { if(E&&E->data.tag==CHAR)/*树不为空*/ { if(E->data.c!='*'&&E->data.c!='^'&&E->data.c!='-'&&E->data.c!='+'&&E->data.c!='/') {printf(\"\\n表达式中仍存在变量没有赋值！没法求出表达式的值！\");return ERROR;} /*存在变量，提示信息，后返回ERROR*/ if(Check(E->lchild))/*递归左子树*/ Check(E->rchild);/*递归右子树*/ } } /*对算术表达式求值*/ long Value(BiTree E) { if(E)/*树不为空*/ { if(!E->lchild&&!E->rchild&&E->data.tag==INT) return (E->data.num); /*结点的左孩子和右孩子为空，为叶子结点，返回结点的值*/ return Operate(Value(E->lchild),E->data.c,Value(E->rchild)); /*运算求值，后根遍历的次序对表达式求值，其中参数递归调用了Value()函数求左子树的值和右子树的值*/ } - - 19 } /*构造一个新的复合表达式*/ void CompoundExpr(char P,BiTree *E1,BiTree E2) { BiTree E; E=(BiTree)malloc(sizeof(BiTNode));/*申请一个结点存放运算符P*/ E->data.tag=CHAR; E->data.c=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 *string,char *pre_expr) { int i,j,len,char_number=1;/*len表示字符串string的长度，char_number是记录数组save_number[]的个数*/ int number;/*保存大于9的常量*/ char c,c1; 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(&S,&c);/*出栈，赋值给c*/ while(c!=')')/*假如c不为')',出栈*/ { *pre_expr++=c; if(!StackEmpty1(S)&&GetTop1(S,&c1)&&c1!='#') Pop1(&S,&c); else {printf(\"\\n输入的表达式有误!\");return ERROR;} } - - 20 } else if(c==')')/*字符为')'，入栈*/ { Push1(&S,c); } else if(c>='0'&&c<='9')/*字符为'0'-'9'之间，循环扫描string前一个字符，后确定常量的大小*/ { number=c-48;/*number为第一个常量字符的ASCII码-48*/ for(c1=string[i-1],j=1;(c1>='0'&&c1<='9')&&i>=0;j++,i--)/*循环扫描string前一个字符，求出常量后 赋给number*/ { number=(c1-48)*power(10,j)+number;/*number为扫描到的常量*/ c1=string[i-2]; } save_number[char_number]=number;/*将number存入到数组save_number中，下标为 char_number*/ *pre_expr++=char_number++; } else if((c>='a'&&c<='z')||(c>='A'&&c<='Z'))/*字符为'a'-'z'或'A'-'Z'之间的变量*/ {/*string下一个字符不能为常量或变量，否则，出错*/ if((string[i-1]>='0'&&string[i-1]<='9')||(string[i-1]>='A'&&string[i-1]<='Z')||(string[i-1]>='a'&&string[i-1]<='z')) {printf(\"\\n输入的表达式有误！\");return ERROR;} else *pre_expr++=c; } else if(c=='*'||c=='/')/*字符为运算符'*'或'/'*/ { while(GetTop1(S,&c1)&&(c1=='^'))/*将c与栈顶的字符c1比较优先级*/ {Pop1(&S,&c1);*pre_expr++=c1;}/*如果c1比c优先，出栈*/ Push1(&S,c);/*入栈字符c*/ } else if(c=='+'||c=='-')/*字符为运算符'+'或'-'*/ { - - 21 while(GetTop1(S,&c1)&&(c1=='^'||c1=='*'||c1=='/'))/*将c与栈顶的字符c1比较优先级*/ {Pop1(&S,&c1);*pre_expr++=c1;}/*如果c1比c优先，出栈*/ Push1(&S,c);/*入栈运算符c*/ } else if(c=='^')/*字符为运算符'^'*/ { Push1(&S,c);/*入栈运算符'^'*/ } else {printf(\"\\n输入的表达式有误！\");return ERROR;}/*其他字符，错误，返回ERROR*/ i--;/*下一个字符*/ if(i>=0) c=string[i];/*i不小于0，c=string[i]循环下一个字符*/ else /*否则，将清空栈*/ while(!StackEmpty1(S)&&GetTop1(S,&c1)&&c1!='#') {Pop1(&S,&c);*pre_expr++=c;} } Pop1(&S,&c);/*将'#'出栈*/ *pre_expr='\\0';/*字符串结束符*/ if(i<0&&StackEmpty1(S))return OK; else return ERROR; } /*将字符串exprstring反转过来*/ void reversal_string(char *exprstring) { int len,i,j; char temp; len=strlen(exprstring);/*len为exprstring的长度*/ for(i=0,j=len-1;i exprstring[i]=exprstring[j]; exprstring[j]=temp; } } /*常数合并操作函数，合并表达式E中所有常数运算*/ void MergeConst(BiTree *E) { long result; if((*E)->lchild&&(*E)->rchild)/*左右孩子不为空*/ { - - 22 if((*E)->lchild->data.tag==INT&&(*E)->rchild->data.tag==INT)/*假如左右孩子为常量，合并*/ { result=Operate((*E)->lchild->data.num,(*E)->data.c,(*E)->rchild->data.num);/*常数合并运算，调用 Operate()函数求值*/ (*E)->data.tag=INT;(*E)->data.num=result;/*修改之前的运算符为常量*/ free((*E)->lchild);/*释放左孩子*/ free((*E)->rchild);/*释放右孩子*/ (*E)->lchild=(*E)->rchild=NULL;/*左右孩子置空*/ } else { MergeConst(&((*E)->lchild));/*递归左孩子*/ MergeConst(&((*E)->rchild));/*递归右孩子*/ } } } //判断是否操作符 int isoperator(char c) { switch(c) { case '+': return TRUE; case '-': return TRUE; case '*': return TRUE; case '/': return TRUE; case '^': return TRUE; default: return FALSE; } } void Diff(BiTree &E,char v)//求偏导数 { /*第一种情况带乘方的 if(((*E)->lchild)&&((*E)->rchild)) { if((*E)->data.tag==CHAR&&(*E)->rchild->lchild->data.tag==CHAR) if(((*E)->rchild->data.c=='^')&&((*E)->rchild->lchild->data.c==v)) { - - 23 (*E)->lchild->data.num=((*E)->lchild->data.num)*((*E)->rchild->rchild->data.num); (*E)->rchild->rchild->data.num=(*E)->rchild->rchild->data.num-1; } //第二种只带单次方 //第三种只为常数*/ // int d,flag3; // printf(\"%c\ if((E->lchild)&&(E->rchild)) { if((E->rchild->data.c=='^')&&(E->rchild->lchild->data.c==v) ) { E->lchild->data.num=(E->lchild->data.num)*(E->rchild->rchild->data.num); E->lchild->data.tag=INT; E->rchild->rchild->data.num=E->rchild->rchild->data.num-1; } if(E->rchild->data.tag==INT&&(E->data.c=='+'||E->data.c=='-')) { E->rchild->data.num=0; E->rchild->data.tag=INT; } if((E->rchild->data.c==v)&&(isoperator(E->lchild->data.c))) { E->rchild->data.num=1; E->rchild->data.tag=INT; // Diff(E->lchild,v); // Diff(E->rchild,v); } if((E->rchild->data.c==v)&&E->lchild->data.tag==INT) { E->data.num=E->lchild->data.num; E->data.tag=INT; free(E->lchild); free(E->rchild); E->lchild=E->rchild=NULL; - - 24 } else { Diff(E->lchild,v); Diff(E->rchild,v); } } // else // { // printf(\"表达式不需要求偏导\\n\"); // } } /*主菜单*/ char menu() { char choice; printf(\"\\n\****************************************\"); printf(\"\\n\***********9.表达式类型的实现***********\"); printf(\"\\n\ 1 >>>输入正确的前缀表达式\"); printf(\"\\n\ 2 >>>带括弧的中缀表示式输出\"); printf(\"\\n\ 3 >>>对变量进行赋值\"); printf(\"\\n\ 4 >>>对算数表达式求值\"); printf(\"\\n\ 5 >>>构造一个新的复合表达式\"); printf(\"\\n\ 6 >>>以表达式的原书写形式输入(选作)\"); printf(\"\\n\ 7 >>>合并表达式中所有常数运算(选作)\"); printf(\"\\n\ 8 >>>三角函数操作 (选作)\"); // printf(\"\\n\ 9 >>>求偏导数 (选作)\"); printf(\"\\n\ 0 >>>退出\"); printf(\"\\n\****************************************\"); printf(\"\\n\请输入你的选择(数字)>>>>>\"); choice=getche(); return choice; } /*主函数*/ void main() { BiTree E,E1;/*两个表达式E和E1*/ int flag=0;/*表达式E构造标志，为0表示未构造，为1表示已构造*/ long result;/*保存算数表达式运算结果*/ char V,P;//V被赋值，P为符合表达式运算符 int c;//C要赋值 - - 25 char string[30];//字符串 while(1) { system(\"cls\");//清屏 switch(menu()) { case '1':/*1 >>>输入正确的前缀表达式*/ printf(\"\\n\*************************输入提示信息************************\"); printf(\"\\n\输入正确的前缀表达式的要求：\"); printf(\"\\n\\【变量】 a-z或A-Z\"); printf(\"\\n\\【常量】 0-9，不能超过9\"); printf(\"\\n\\【运算符】 +,-,*,/,^(乘幂)\"); printf(\"\\n\\例0;5;+a*53\"); printf(\"\\n\请输入正确的前缀表达式，后按回车键存入缓冲区，否则可能会出错！\"); printf(\"\\n\*************************************************************\"); if(Input_Expr(Expr_String,0))//在flag=0时，初始输入 if(ReadExpr(&E,Expr_String))//前缀读入并构造E {flag=1; printf(\"\\n表达式构造成功！\\n输入的带括弧的中缀表达式：\"); WriteExpr(E);}/*带括弧的中缀表示式输出 ，递归实现*/ getch(); break; case '2':/*2 >>>带括弧的中缀表示式输出*/ printf(\"\\n\********************输出说明信息***********************************\"); printf(\"\\n\输出带括弧的中缀表达式：\"); printf(\"\\n\【1】如果表达式已经构造成功的，输出表达式；\"); printf(\"\\n\【2】如果表达式还未构造成功的，请返回主菜单选择构造表达式；\"); printf(\"\\n\【注】其中要注意的是，可能有一些表达式构造时没有办法判断为有误，\"); printf(\"\\n\ 如果输出不是你想得到的，说明你之前输入的表达式有误，请重新构造！\"); printf(\"\\n\********************************************************************\"); if(flag==1) {printf(\"\\n带括弧的中缀表达式为：\"); - - 26 WriteExpr(E); } else printf(\"\\n表达式未构造成功！请重新构造成功的表达式！\"); getch(); break; case '3':/*3 >>>对变量进行赋值*/ printf(\"\\n\********************赋值操作说明信息***********************************\"); printf(\"\\n\赋值操作：实现对表达式中的某一个变量V的赋值，即使V=C，C为一整数\"); printf(\"\\n\ 【1】根据输出的表达式，输入要赋值的变量V，只能输入一个字符，否则出错\"); printf(\"\\n\ 【2】输入要将变量V赋值为的整数C，只能是整数，否则出错\"); printf(\"\\n\ 【注】如果表达式未构造，请回到主菜单选择构造表达式\"); printf(\"\\n\***********************************************************************\"); if(flag==1) { int Assign_flag=0; printf(\"\\n表达式E为：\"); WriteExpr(E); flushall();/*清理缓冲区*/ printf(\"\\n请输入要赋值的字符：\"); V=getchar(); printf(\"请输入要将赋值为：\"); scanf(\"%d\ Assign(&E,V,c,&Assign_flag);//赋值并改变标志 if(Assign_flag) {printf(\"\\n赋值成功！\\n赋值后的表达式为：\");WriteExpr(E);} else printf(\"\\n表达式里没有%c这个变量！\ } else printf(\"\\n表达式未构造成功！请构造成功的表达式！\"); getch(); break; case '4':/*4 >>>对算数表达式求值*/ printf(\"\\n\********************算数表达式求值说明信息************************\"); printf(\"\\n\ 【注】如果表达式还有变量未赋值，即表达 - - 27 式不是算数表达式\"); printf(\"\\n\ 不能求出表达式的值，请回到主菜单选择赋值操作，后再求值\"); printf(\"\\n\******************************************************************\"); if(flag==1) { printf(\"\\n算数表达式：\");WriteExpr(E); if(Check(E)) //检查是否全赋值 {result=Value(E);printf(\"\\n求算数表达式的值:\\");WriteExpr(E);printf(\"=%ld\ } else printf(\"\\n表达式未构造成功！请构造成功的表达式！\"); getch(); break; case '5':/*5 >>>构造一个新的复合表达式*/ printf(\"\\n\*****************构造新的复合表达式说明信息***************************\"); printf(\"\\n\ 【1】构造一个新的表达式E1，采用表达式的原书写形式输入\"); printf(\"\\n\ 【2】构造表达式E1成功后，输入要复合表达式E和E1的操作运算符(+,-,*,/,^)\"); printf(\"\\n\ 【注】如表达式E未构造，不能复合表达式；如构造表达式E1错误，复合失败\"); printf(\"\\n\***********************************************************************\"); if(flag==1) { printf(\"\\n表达式E1为：\"); WriteExpr(E); printf(\"\\n请构造新的表达式E2:\"); flushall();/*清理缓冲区*/ if(Input_Expr(string,1))//标志为1，输入字符串 { if(Read_Inorder_Expr(string,Expr_String))//入栈 { reversal_string(Expr_String);//反转 if(ReadExpr(&E1,Expr_String)) { flag=1;printf(\"\\n表达式E1构造成功！ - - 28 \");WriteExpr(E1); printf(\"\\n请输入要构造新的复合表达式的操作运算符>>>\"); P=getchar(); while(P!='*'&&P!='/'&&P!='+'&&P!='-'&&P!='^') { flushall();/*清理缓冲区*/ printf(\"\\n输入的操作运算符有误！请重新输入>>>\"); P=getchar(); } CompoundExpr(P,&E,E1); } else printf(\"\\n复合新的表达式失败！请按任意键返回主菜单！\"); } } } else printf(\"\\n表达式未构造成功！请构造成功的表达式！\"); getch(); break; case '6':/*6 >>>以表达式的原书写形式输入*/ printf(\"\\n\*************以表达式的原书写形式输入说明信息************************\"); printf(\"\\n\输入正确的原书写形式表达式\"); printf(\"\\n\ 【变量】 a-z或A-Z\"); printf(\"\\n\ 【常量】 大于等于0的正整数\"); printf(\"\\n\ 【运算符】 +,-,*,/,^(乘幂)\"); printf(\"\\n\ 【括弧】 左括弧 ( ,右括弧 ) \"); printf(\"\\n\ 【注】 表示式中常量最多只能是30个，超过30个，出错！\"); printf(\"\\n\按原书写形式输入中，请按照正确的方式输入，否则可能会出错！\"); printf(\"\\n\**********************************************************************\"); if(Input_Expr(string,1)) if(Read_Inorder_Expr(string,Expr_String)) { reversal_string(Expr_String); if(ReadExpr(&E,Expr_String)) {flag=1;printf(\"\\n表达式构造成功！\\n输入的带 - - 29 括弧的中缀表达式：\");WriteExpr(E);} } getch(); break; case '7':/*7 >>>合并表达式中所有常数运算*/ printf(\"\\n***************合并表达式中的所有常数运算*******************************\"); printf(\"\\n 【注】合并表达式中的所有常数运算并不能一次性将常数都合并！\"); printf(\"\\n例如：表达式'1+2*(3+3*4+9/3)'的常数合并，选择7进行合并，结果变为\\n'1+2*(3+12+3)'，\"); printf(\"根据优先级先后合并的，如果要合并到最后，需多次选择7\\n进行合并，又合并一次'1+2*(15+3)'，\"); printf(\"再次合并'1+2*18',再次合并'1+36'，\\n再次合并'37'，后无法合并！\"); printf(\"\\n************************************************************************\"); if(flag==1) { printf(\"\\n原表达式为：\"); WriteExpr(E); MergeConst(&E);//常数合并操作 printf(\"\\n合并表达式中所有的常数运算后的表达式：\"); WriteExpr(E); } else printf(\"\\n表达式未构造成功！请构造成功的表达式！\"); getch(); break; case '8'://三角函数操作 printf(\"\\n\***************************三角函数操作(选作)***************************\"); printf(\"\\n\"); printf(\"\\n\[注] 请按要求输入其中 ~代表sin !代表cos @代表tan \"); printf(\"\\n\角度用弧度表示，例如~1 即表示sin 1\"); printf(\"\\n\本操作只可求三角函数值，如需其他操作请将结果带入其它操作中\"); printf(\"\\n\输入一个字符请按回车，确保正确录入\"); printf(\"\\n\************************************************************************\"); - - 30 double opr1,result1; char opr; printf(\"\\n请按要求输入\"); scanf(\"%c\ scanf(\"%lf\ result1=Operate1(opr,opr1); printf(\"结果为%f\ getch();break; case '9': getchar(); char h; printf(\"输入需要求偏导的变量字符\\n\"); scanf(\"%c\ Diff(E,h); WriteExpr(E); break; case '0':/*0 >>>退出*/ printf(\"\\n请按任意键退出！\"); getch(); exit(0); default : printf(\"\\n输入有误！请按任意键回到主菜单重新选择！\"); getch(); break; } } } /*void Diff(BiTree &E,char v) { // int d,flag3; // printf(\"%c\ if((E->lchild)&&(E->rchild)) { if((E->rchild->data=='^')&&(E->rchild->lchild->data==v)) { E->lchild->data=(E->lchild->data)*(E->rchild->rchild->data); E->rchild->rchild->data=E->rchild->rchild->data-1; } if((E->rchild->data==v)&&(isoperator(E->lchild->data))) { E->rchild->data=1; // Diff(E->lchild,v); // Diff(E->rchild,v); - - 31 } if((E->rchild->data==v)&&(E->lchild->data>=0&&E->lchild->data<=9)) { E->data=E->lchild->data; free(E->lchild); free(E->rchild); E->lchild=E->rchild=NULL; } else { Diff(E->lchild,v); Diff(E->rchild,v); } } // else // { // printf(\"表达式不需要求偏导\\n\"); // } } case 7:getchar(); printf(\"输入需要求偏导的变量字符\\n\"); scanf(\"%c\ Diff(E,h); WriteExpr(E); break;*/ - - 32 附 expression.h /*头文件以及存储结构*/ #include typedef enum{INT,CHAR}ElemTag;/*INT为整型数据num，CHAR为字符型数据c*/ typedef struct TElemType { ElemTag tag;/*{INT,CHAR}指示是整型还是字符型*/ union { int num;/*tag=INT时，为整型*/ char c;/*tag=CHAR时，为字符型*/ }; } TElemType; /*二叉树的二叉链表存储表示 */ typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指针 */ }BiTNode,*BiTree; 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 - - 33 { SElemType1 *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType1 *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ }SqStack1; /* 顺序栈 */ /*顺序栈的基本操作*/ Status InitStack(SqStack *S) { /* 构造一个空栈S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(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(S.top==S.base) return TRUE; else return FALSE; } Status Push(SqStack *S,SElemType e) { /* 插入元素e为新的栈顶元素 */ if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */ { (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; } *((*S).top)++=e; return OK; } Status Pop(SqStack *S,SElemType *e) { /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if((*S).top==(*S).base) return ERROR; *e=*--(*S).top; - - 34 return OK; } Status GetTop(SqStack S,SElemType *e) { /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */ if(S.top>S.base) { *e=*(S.top-1); return OK; } else return ERROR; } /*顺序栈的基本操作*/ Status InitStack1(SqStack1 *S) { /* 构造一个空栈S */ (*S).base=(SElemType1 *)malloc(STACK_INIT_SIZE*sizeof(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(S.top==S.base) return TRUE; else return FALSE; } Status Push1(SqStack1 *S,SElemType1 e) { /* 插入元素e为新的栈顶元素 */ if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */ { (*S).base=(SElemType1 *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType1)); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; } *((*S).top)++=e; - - 35 return OK; } Status Pop1(SqStack1 *S,SElemType1 *e) { /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if((*S).top==(*S).base) return ERROR; *e=*--(*S).top; return OK; } Status GetTop1(SqStack1 S,SElemType1 *e) { /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */ if(S.top>S.base) { *e=*(S.top-1); return OK; } else return ERROR; } - - 36 因篇幅问题不能全部显示，请点此查看更多更全内容