前缀输入,中缀输出,若带字母,则为字母赋值,最后计算表达式的值。
#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<string.h> typedef enum { INT, CHAR } DataType;//CHAR=1表示存贮字符,INT=0表示存储运算数据 typedef union { char vchar; int num; } ElemType; //二叉树节点结构体 typedef struct BiTNode { DataType type;//data中存储的数据的类型 ElemType data;//数据域 struct BiTNode *lchild, *rchild; //左右孩子指针域 } BiTNode, *BiTree; //全局变量 char preExpr[100];//表达式 int isExist = 0;//表达式是否已经构造 int beCounted = 0;//表达式中的常数运算行为是否发生 //顺序栈功能的实现 #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACK_INCREMENT 10 //存储空间分配增量 #define SElemType BiTree//元素类型 typedef struct { SElemType *base;//栈底指针 SElemType *top;//栈顶指针 int stackSize;//当前已分配的存储空间 以元素为单位 } SqStack; //构造一个空栈S int InitStack(SqStack *S) { (*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base) exit(1); (*S).top = (*S).base; (*S).stackSize = STACK_INIT_SIZE; return 0; } //若栈不空 则用e返回S的栈顶元素 并返回1 否则返回0 int GetTop(SqStack S,SElemType *e) { if(S.top == S.base) return 0; *e = *(S.top - 1); return 1; } //插入元素e为新的栈顶元素 int Push (SqStack *S,SElemType e) { if((*S).top - (*S).base >= (*S).stackSize) {//栈满 追加存储空间 (*S).base = (SElemType *)realloc((*S).base,((*S).stackSize + STACK_INCREMENT)*sizeof(SElemType)); if(!(*S).base) exit(1);//存储分配失败 (*S).top = (*S).base + (*S).stackSize; (*S).stackSize += STACK_INCREMENT; } *(*S).top++ = e; return 1; } //若栈不空 则删除S的栈顶元素 用e返回其值 并返回1 否则返回0 int Pop(SqStack *S, SElemType *e) { if((*S).top == (*S).base) return 0; *e = * --(*S).top; return 1; } //若栈S为空栈,则返回1,否则返回0 int StackEmpty(SqStack S) { if(S.top==S.base) return 1; else return 0; } //函数声明 void list(); int getPreExpr(); void AsNode(BiTree *E,int i); int ReadExpr(BiTree *E); int Primary(char a,char b); void WriteExpr(BiTree E); void Assign(BiTree *E,char V,int c,int *flag); int Check_Variable(BiTree E); float Operate(int a, char ope, int b); float Value(BiTree E); //主函数 int main() { char choice; BiTree E,E2;//二叉树 float value_result; while(1) { list();//输出功能列表 printf("请输入你的选择:"); choice = getch(); switch(choice) { case '1': printf("\n【提示】\n算术表达式内可以含有变量(a~z),常量(0~9)和二元运算符(+, -, *, /)"); fflush(stdin);//清理缓冲区 if(getPreExpr()) if(ReadExpr(&E)) { isExist=1; printf("表达式构造成功!\n"); } printf("按任意键返回:"); getch(); break; case '2': if(isExist==1)//检查是否已经构造表达式 { printf("\n带括弧的中缀表达式为:"); WriteExpr(E); } else printf("\n没有成功构造表达式!"); printf("\n按任意键返回:"); getch(); break; case '3': if(isExist==1)//检查是否已经构造表达式 { char next; do { int Assign_flag=0; int c; char V; printf("\n表达式E为:"); WriteExpr(E); fflush(stdin);//清理缓冲区 //获取输入 printf("\n请输入需要赋值的变量:"); V=getchar(); //判断输入的是不是字符 if((V>='a' && V<='z') || (V>='A' && V<='Z')) { printf(""); } else { printf("请输入字母!"); next = 'y'; continue;//从头重新输入 } printf("请输入需要赋给该变量的值:",V); scanf("%d",&c); Assign(&E,V,c,&Assign_flag); //判断是否赋值成功 if(Assign_flag) { printf("赋值成功!\n赋值后的表达式为:"); WriteExpr(E); } else printf("赋值失败!可能表达式中没有此变量!"); printf("\n是否继续赋值?<y/n>"); next = getch(); }while(next=='y' || next=='Y'); } else { printf("\n没有成功构造表达式!"); printf("\n按任意键返回:"); getch(); } break; case '4': if(isExist==1)//检查是否已经构造表达式 { printf("\n算术表达式为:"); WriteExpr(E); if(Check_Variable(E))//确保没有未知量 { value_result = Value(E); printf("\n其值为:"); printf("%.2f",value_result); } else printf("\n表达式中仍存在没有赋值的变量!"); } else printf("\n没有成功构造表达式!"); printf("\n按任意键返回:"); getch(); break; case '0': printf("\n感谢使用,再见!\n按任意键退出:"); getch(); exit(0); break; } system("cls");//清屏 } return 0; } //功能列表 void list() { printf("------------------表达式类型的实现-----------------\n"); printf(" 1.输入前缀表示式并构造表达式\n"); printf(" 2.用带括弧的中级表示式输出表达式\n"); printf(" 3.对表达式中的变量赋值\n"); printf(" 4.对算术表达式求值\n"); printf("----------------------------------------------------\n"); } //获取前缀表达式 int getPreExpr() { printf("\n请输入前缀表示式:"); gets(preExpr);//从键盘输入一串字符串作为前缀表达式 if(strlen(preExpr) == 1)//输入的表达式字符串长度为1 //输入的表达式只有一个运算符 if(preExpr[0] == '+' || preExpr[0] == '-' || preExpr[0] == '*' || preExpr[0] == '/') { printf("输入错误!表达式只有一个运算符!"); return 0; } //输入的表达式只有一个数字或字符 else if((preExpr[0] >= '0' && preExpr[0] <= '9') || (preExpr[0] >= 'a' && preExpr[0] <= 'z') || (preExpr[0] >= 'A' && preExpr[0] <= 'Z')) { printf("输入成功!表达式只有一个字符!"); return 1; } else { printf("输入错误!输入无法识别"); return 0; } else return 1; } //将字符或数字存为二叉树结点 void AsNode(BiTree *E,int i) { if(preExpr[i]>='0' && preExpr[i]<='9')//为数字 { //将字符型数字转换成字符串以满足atoi函数的参数要求 char value[2]; value[0] = preExpr[i]; value[1] = '\0'; //将字符型数字转换成整形数字 (*E)->data.num = atoi(value); (*E)->type = INT; } else//为字符 { (*E)->data.vchar = preExpr[i]; (*E)->type = CHAR; } } //以前缀表示式构造表达式 int ReadExpr(BiTree *E) { SqStack S; int i,len;//len为表达式的长度 BiTree p,q; (*E) = (BiTree)malloc(sizeof(BiTNode));//申请二叉树的根结点的空间 (*E)->lchild = NULL; (*E)->rchild = NULL; len = strlen(preExpr); //len赋值为表达式的长度 if(len == 1)//表达式长度为1时,二叉树只有根结点 { AsNode(E,0);//将第一个输入字符存入二叉树的结点中 } else { AsNode(E,0);//将第一个输入字符存入二叉树的结点中 InitStack(&S);//初始化栈 q=(*E); Push(&S,q);//入栈 Push(&S,q);//入栈,根结点入栈两次是为判断先序输入的表达式是不是正确的表达式 for(i=1; i<len && !StackEmpty(S); i++) { p=(BiTree)malloc(sizeof(BiTNode)); AsNode(&p,i);//将exprstring[i]存入二叉树的结点中 p->lchild = NULL; p->rchild = NULL; //为运算符,运算符入栈,根据是否为空来选择成为左孩子还是右孩子 if(preExpr[i]=='+' || preExpr[i]=='-' || preExpr[i]=='*' || preExpr[i]=='/') { if(!q->lchild)//左孩子空 成为左孩子 { q->lchild=p; Push(&S,p); q=p; } 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); } } } //栈空且i>=len,说明输入的表达式是正确的 if(StackEmpty(S) && i >= len) { return 1; } else { printf("\n输入的表达式有误!"); return 0; } } } //如果两个字符是运算符,比较两个运算符的优先级 输出是否a比b优先 int Primary(char a,char b) { //判断是否为运算符 if((a=='*' || a=='-' || a=='+' || a=='/') && (b=='*' || b=='-' || b=='+' || b=='/')) { //a为乘法或除法运算符 优先于加减运算符 if(a=='*' || a=='/') { if(b == '*' || b == '/') return 0; else return 1; } else return 0; } else return 0; } //用带括弧的中缀表达式输出表达式 void WriteExpr(BiTree E) { //树不为空 中序遍历 if(E) { //递归左子树 if(E->lchild && E->lchild->type == CHAR)//E的左孩子不为空且为字符 { //双亲运算符比孩子运算符优先 if(Primary(E->data.vchar,E->lchild->data.vchar)) { //带括弧输出左子树 printf("("); WriteExpr(E->lchild); printf(")"); } else WriteExpr(E->lchild);//不带括弧输出左子树 } else WriteExpr(E->lchild);//直接输出左子树 //访问输出根结点的值 if(E->type == INT) printf("%d",E->data.num); else printf("%c",E->data.vchar); //递归右子树 if(E->rchild && E->rchild->type == CHAR)//E的右孩子不为空且为字符 { //双亲运算符比孩子运算符优先 if(Primary(E->data.vchar,E->rchild->data.vchar)) { //带括弧输出右子树 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)->type == CHAR && (*E)->data.vchar == V)//找到要赋值的变量 { (*E)->type = INT; //修改元素类型 (*E)->data.num = c; *flag = 1;//标志已赋值 } //递归左子树 Assign(&((*E)->lchild),V,c,flag); //递归右子树 Assign(&((*E)->rchild),V,c,flag); } } //检查表达式是否还存在没有赋值的变量 先序递归遍历 int Check_Variable(BiTree E) { //树不为空且元素为字符型 if(E && E->type == CHAR) { //存在非运算符 if(E->data.vchar != '*' && E->data.vchar != '-' && E->data.vchar != '+' && E->data.vchar != '/') return 0; //递归左子树 if(Check_Variable(E->lchild)) { Check_Variable(E->rchild);//递归右子树 } } else return 1; } //基本运算求值 ope:运算符 float Operate(int a, char ope, int b) { switch(ope) { case '+': return (a+b); break; case '-': return (a-b); break; case '*': return (a*b); break; case '/': return (a/b); break; default : return 0; } } //对算术表达式求值 float Value(BiTree E) { if(E)//树不为空 { //若为叶子结点(即数字)则返回结点的值 if(!E->lchild && !E->rchild && E->type == INT) return E->data.num; //非叶子结点则继续递归求值 return Operate(Value(E->lchild),E->data.vchar,Value(E->rchild)); } }