表达式类型的实现c程序(功能全,可运行)

1、expression.cpp#include"expression.h"#include"math.h"#include <stdio.h>#define pi 3.1415926 /*全局变量*/int save_number51;/*在按原表达式输入形式中，输入的常量保存到数组save_number中，常量最多为50个，0单元不用*/char Expr_String50;/*存放表达式的字符串*/*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/*参数flag=0表示输出的提示信息是"请输入正确的前缀表示式

2、："*/*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(string0='+'

3、|string0='-'|string0='*'|string0='/'|string0='')/*输入的表达式只有一个运算符*/ printf("n表达式只有一个字符，为运算符，错误！");return ERROR;else if(string0>='0'&&string0<'9')|(string0>='a'&&string0<='z')|(string0>='A'&

4、amp;&string0<='Z')/*输入的表达式只有一个数字或字符*/ printf("n表达式只有一个字符！");return OK;else printf("n输入的字符不是运算符也不是变量常量，错误！");return ERROR;return OK;/*判断字符stringi，如果是'0'-'9'常量之间，二叉树结点存为整型；否则，存为字符型*/void judge_value(BiTree *E,char *string,int i)if(stringi>='0&#

5、39;&&stringi<='9')/*为常量*/(*E)->data.tag=INT;(*E)->data.num=stringi-48;else if(stringi>=1&&stringi<=20)/*为常量，常量存于数组save_number中*/(*E)->data.tag=INT;(*E)->data.num=save_numberstringi;else/*为变量*/(*E)->data.tag=CHAR;(*E)->data.c=stringi;/*以正确的前缀表示式并构造表达

6、式E*/Status ReadExpr(BiTree *E,char *exprstring)SqStack S;/定义顺序栈Sint 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);/*将exprstr

7、ing0存入二叉树的结点中*/else judge_value(E,exprstring,0);/*将exprstring0存入二叉树的结点中*/InitStack(&S);/*初始化栈*/q=(*E);Push(&S,q);/*入栈*/Push(&S,q);/*入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式*/for(i=1;i<len&&!StackEmpty(S);i+)/p=(BiTree)malloc(sizeof(BiTNode);judge_value(&p,exprstring,i);/*将exprstrin

8、gi存入二叉树的结点中*/p->lchild=NULL;p->rchild=NULL;if(exprstringi='+'|exprstringi='-'|exprstringi='*'|exprstringi='/'|exprstringi='')/*为运算符，运算符入栈，左孩子不空，向左孩子走，否则，如果右孩子不空，向右孩子走*/if(!q->lchild)q->lchild=p;Push(&S,p);q=p;elseq->rchild=p;Push(&S,p);q

9、=p;else/*不是运算符，运算符出栈*/if(!q->lchild)q->lchild=p;Pop(&S,&q);elseq->rchild=p;Pop(&S,&q);if(StackEmpty(S)&&i>=len)return OK;/*栈空且i>=len，说明输入的表达式是正确的*/else/*输入的表达式是错误的*/printf("n输入的表达式有误！");return ERROR;/*如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR*/Sta

10、tus 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 retu

11、rn 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不是运算符*/*用带括弧的中缀表达式输出表达式*/void WriteExpr(BiTree E)if(E)/*树不为空*/*先递归左

12、子树*/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);/*否则，不带括弧输出左子树*

13、/else WriteExpr(E->lchild);/*否则，输出左子树*/*访问输出根结点的值*/if(E->data.tag=INT)printf("%d",E->data.num);else printf("%c",E->data.c);/*后递归右子树*/if(E->rchild&&E->rchild->data.tag=CHAR)/*E的右孩子不为空，且右孩子为字符*/if(Pri_Compare(E->data.c,E->rchild->data.c)/*E->

14、;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)

15、->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);/*递归左子树*/*指数运算函数，底数为x，指数为exp*/long power(int x,int exp)long result;int i;for(i=1,result=1;i<=exp;

16、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=op

17、r1*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,opr2; opr2=

18、opr1*2*pi/360;switch(opr) case 's':/*正玄sin*/result1=sin(opr2);return result1;break; case 'c':/*余弦*/result1=cos(opr2);return result1;break; case 't':/*正切*/result1=tan(opr2);return result1;break;default:break;/*检查表达式是否还存在没有赋值的变量，以便求算数表达式的值*/Status Check(BiTree E)if(E&&E

19、->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)/*

20、递归左子树*/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);/*运算求值，后根遍历的次序对表达式求值，其中参数递归调用了

21、Value()函数求左子树的值和右子树的值*/*构造一个新的复合表达式*/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复合成功！其表达式变为

22、：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;

23、/*栈定义*/InitStack1(&S);/*初始栈*/Push1(&S,'#');/*先将字符'#'入栈，用来表示作为栈的最底一个元素*/len=strlen(string);/*len为字符串string的长度*/c=stringlen-1;/*从字符串的最后一个字符开始向前扫描*/i=len-1;while(!StackEmpty1(S)&&i>=0)/*栈不为空且i大于等于0*/if(c='(')/*字符为'('*/Pop1(&S,&c);/*出栈，赋值给c*/whi

24、le(c!=')')/*假如c不为')',出栈*/*pre_expr+=c;if(!StackEmpty1(S)&&GetTop1(S,&c1)&&c1!='#') Pop1(&S,&c);else printf("n输入的表达式有误!");return ERROR;else if(c=')')/*字符为')'，入栈*/Push1(&S,c);else if(c>='0'&&c<='

25、;9')/*字符为'0'-'9'之间，循环扫描string前一个字符，后确定常量的大小*/number=c-48;/*number为第一个常量字符的ASCII码-48*/for(c1=stringi-1,j=1;(c1>='0'&&c1<='9')&&i>=0;j+,i-)/*循环扫描string前一个字符，求出常量后赋给number*/number=(c1-48)*power(10,j)+number;/*number为扫描到的常量*/c1=stringi-2;save_

26、numberchar_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(stringi-1>='

27、;0'&&stringi-1<='9')|(stringi-1>='A'&&stringi-1<='Z')|(stringi-1>='a'&&stringi-1<='z')printf("n输入的表达式有误！");return ERROR;else*pre_expr+=c;else if(c='*'|c='/')/*字符为运算符'*'或'/'*/w

28、hile(GetTop1(S,&c1)&&(c1='')/*将c与栈顶的字符c1比较优先级*/Pop1(&S,&c1);*pre_expr+=c1;/*如果c1比c优先，出栈*/Push1(&S,c);/*入栈字符c*/else if(c='+'|c='-')/*字符为运算符'+'或'-'*/while(GetTop1(S,&c1)&&(c1=''|c1='*'|c1='/')/*将c与栈顶的字符

29、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=stringi;/*i不小于0，c=stringi循环下一个字符*/else /*否则，将

30、清空栈*/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 *exprstri

31、ng)int len,i,j;char temp;len=strlen(exprstring);/*len为exprstring的长度*/for(i=0,j=len-1;i<j;i+,j-)/*字符串前后两个字符对换*/temp=exprstringi;exprstringi=exprstringj;exprstringj=temp;/*常数合并操作函数，合并表达式E中所有常数运算*/void MergeConst(BiTree *E)long result;if(*E)->lchild&&(*E)->rchild)/*左右孩子不为空*/if(*E)->

32、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)-&g

33、t;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 '/

34、': return TRUE; case '': return TRUE; default: return FALSE; /*主菜单*/char menu()char choice;printf("nt*");printf("nt*9.表达式类型的实现*");printf("nt 1 >>>输入正确的前缀表达式");printf("nt 2 >>>带括弧的中缀表示式输出");printf("nt 3 >>>对变量进行赋值&quo

35、t;);printf("nt 4 >>>对算数表达式求值");printf("nt 5 >>>构造一个新的复合表达式");printf("nt 6 >>>以表达式的原书写形式输入(选作)");printf("nt 7 >>>合并表达式中所有常数运算(选作)"); printf("nt 8 >>>三角函数操作 (选作)");printf("nt 0 >>>退出");pri

36、ntf("nt*");printf("nt请输入你的选择(数字)>>>>>");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要赋值char string30;/字符串while(1)system("cls");

37、/清屏switch(menu()case '1':/*1 >>>输入正确的前缀表达式*/printf("nt*输入提示信息*");printf("nt输入正确的前缀表达式的要求：");printf("ntt【变量】 a-z或A-Z");printf("ntt【常量】 0-9，不能超过9");printf("ntt【运算符】 +,-,*,/,(乘幂)"); printf("ntt例0;5;+a*53");printf("nt请输入正确

38、的前缀表达式，后按回车键存入缓冲区，否则可能会出错！");printf("nt*");if(Input_Expr(Expr_String,0)/在flag=0时，初始输入if(ReadExpr(&E,Expr_String)/前缀读入并构造Eflag=1; printf("n表达式构造成功！n输入的带括弧的中缀表达式："); WriteExpr(E);/*带括弧的中缀表示式输出 ，递归实现*/getch();break;case '2':/*2 >>>带括弧的中缀表示式输出*/printf("

39、nt*输出说明信息*");printf("nt输出带括弧的中缀表达式：");printf("nt【1】如果表达式已经构造成功的，输出表达式；");printf("nt【2】如果表达式还未构造成功的，请返回主菜单选择构造表达式；");printf("nt【注】其中要注意的是，可能有一些表达式构造时没有办法判断为有误，");printf("nt 如果输出不是你想得到的，说明你之前输入的表达式有误，请重新构造！");printf("nt*");if(flag=1)prin

40、tf("n带括弧的中缀表达式为："); WriteExpr(E);else printf("n表达式未构造成功！请重新构造成功的表达式！");getch();break;case '3':/*3 >>>对变量进行赋值*/printf("nt*赋值操作说明信息*");printf("nt赋值操作：实现对表达式中的某一个变量V的赋值，即使V=C，C为一整数");printf("nt 【1】根据输出的表达式，输入要赋值的变量V，只能输入一个字符，否则出错");prin

41、tf("nt 【2】输入要将变量V赋值为的整数C，只能是整数，否则出错");printf("nt 【注】如果表达式未构造，请回到主菜单选择构造表达式");printf("nt*");if(flag=1)int Assign_flag=0;printf("n表达式E为：");WriteExpr(E);flushall();/*清理缓冲区*/printf("n请输入要赋值的字符：");V=getchar();printf("请输入要将赋值为：");scanf("%d&q

42、uot;,&c);Assign(&E,V,c,&Assign_flag);/赋值并改变标志if(Assign_flag)printf("n赋值成功！n赋值后的表达式为：");WriteExpr(E);else printf("n表达式里没有%c这个变量！",V);else printf("n表达式未构造成功！请构造成功的表达式！");getch();break;case '4':/*4 >>>对算数表达式求值*/printf("nt*算数表达式求值说明信息*"

43、;);printf("nt 【注】如果表达式还有变量未赋值，即表达式不是算数表达式");printf("nt 不能求出表达式的值，请回到主菜单选择赋值操作，后再求值");printf("nt*");if(flag=1)printf("n算数表达式：");WriteExpr(E);if(Check(E) /检查是否全赋值result=Value(E);printf("n求算数表达式的值:t");WriteExpr(E);printf("=%ld",result);else pr

44、intf("n表达式未构造成功！请构造成功的表达式！");getch();break;case '5':/*5 >>>构造一个新的复合表达式*/printf("nt*构造新的复合表达式说明信息*");printf("nt 【1】构造一个新的表达式E1，采用表达式的原书写形式输入");printf("nt 【2】构造表达式E1成功后，输入要复合表达式E和E1的操作运算符(+,-,*,/,)");printf("nt 【注】如表达式E未构造，不能复合表达式；如构造表达式E1错

45、误，复合失败");printf("nt*");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(&

46、quot;n表达式E1构造成功！");WriteExpr(E1);printf("n请输入要构造新的复合表达式的操作运算符>>>");P=getchar();while(P!='*'&&P!='/'&&P!='+'&&P!='-'&&P!='')flushall();/*清理缓冲区*/printf("n输入的操作运算符有误！请重新输入>>>");P=getchar()

47、;CompoundExpr(P,&E,E1);else printf("n复合新的表达式失败！请按任意键返回主菜单！");else printf("n表达式未构造成功！请构造成功的表达式！");getch();break;case '6':/*6 >>>以表达式的原书写形式输入*/printf("nt*以表达式的原书写形式输入说明信息*");printf("nt输入正确的原书写形式表达式");printf("nt 【变量】 a-z或A-Z");print

48、f("nt 【常量】 大于等于0的正整数");printf("nt 【运算符】 +,-,*,/,(乘幂)");printf("nt 【括弧】 左括弧 ( ,右括弧 ) ");printf("nt 【注】 表示式中常量最多只能是30个，超过30个，出错！");printf("nt按原书写形式输入中，请按照正确的方式输入，否则可能会出错！");printf("nt*");if(Input_Expr(string,1)if(Read_Inorder_Expr(string,Expr

49、_String)reversal_string(Expr_String);if(ReadExpr(&E,Expr_String)flag=1;printf("n表达式构造成功！n输入的带括弧的中缀表达式：");WriteExpr(E);getch();break;case '7':/*7 >>>合并表达式中所有常数运算*/printf("n*合并表达式中的所有常数运算*");printf("n 【注】合并表达式中的所有常数运算并不能一次性将常数都合并！");printf("n例如：表

50、达式'1+2*(3+3*4+9/3)'的常数合并，选择7进行合并，结果变为n'1+2*(3+12+3)'，");printf("根据优先级先后合并的，如果要合并到最后，需多次选择7n进行合并，又合并一次'1+2*(15+3)'，");printf("再次合并'1+2*18',再次合并'1+36'，n再次合并'37'，后无法合并！");printf("n*");if(flag=1) printf("n原表达式为："

51、;);WriteExpr(E);MergeConst(&E);/常数合并操作printf("n合并表达式中所有的常数运算后的表达式：");WriteExpr(E);else printf("n表达式未构造成功！请构造成功的表达式！");getch();break;case '8':/三角函数操作printf("nt*三角函数操作(选作)*");printf("n");printf("nt注 请按要求输入其中 s代表sin c代表cos t代表tan "); printf(

52、"nt输入数据为角度，例如s1 即表示sin 1"); printf("nt本操作只可求三角函数值，如需其他操作请将结果带入其它操作中"); printf("nt输入一个字符请按回车，确保正确录入"); printf("nt*"); double opr1,result1;char opr; printf("n请按要求输入");scanf("%c",&opr);getch();scanf("%lf",&opr1);getch(); resu

53、lt1=Operate1(opr,opr1); printf("结果为%f",result1); getch();break; case '0':/*0 >>>退出*/printf("n请按任意键退出！");getch();exit(0);default :printf("n输入有误！请按任意键回到主菜单重新选择！");getch();break;Expression.h #include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW 0typedef int Status;/*二叉树结点类型*/typedef enumINT,CHA