#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));
}
}
//java/5689