#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define TRUE 1
#define FALSE 0
#define MAXNUM 100
typedef int DataType;
struct BinTreeNode;
typedef struct BinTreeNode * PBinTreeNode;
struct BinTreeNode{
DataType info;
PBinTreeNode llink;
PBinTreeNode rlink;
};
typedef struct BinTreeNode * BinTree;
typedef BinTree * PBintree;
int infixtoBintree(PBintree pbtree, char* infix,int n){
/*从中缀表达式建立(长度为n)二叉树。*/
char c;
int index,i,bracket;
int have_bracket=FALSE; //记录表达式中是否包含括号
int num,state_int,nint;
int tag1,tag2;
//
if(infix[0]==' '||infix[0]=='\t'||infix[0]=='\n')//忽略空格
return infixtoBintree(pbtree,infix+1,n-1);
if(infix[-1]==' '||infix[0]=='\t'||infix[0]=='\n')
return infixtoBintree(pbtree,infix,n-1);
//
if(infix[0]=='('&&infix[n-1]==')')//去括号
return infixtoBintree(pbtree,infix+1,n-2);
bracket=0; //为0 ，说明当前位置为括号外
index=n;
for(i=n-1;i>=0;i--){ //从后向前搜索，寻找到第一个优先级最低的运算符
c=infix[i];
if(c==')'){
have_bracket=TRUE;
bracket++; //进入一层括号
}//if
if(c='('){
bracket--; //出一层括号
if(bracket<0){
*pbtree=NULL;
return FALSE;//左右括号不匹配
}//if2
if(bracket>0) continue;//若当前位置在括号中，直接搜索下一个位置
if(c=='+'||c=='-')
if(index==n||infix[index]=='*'||infix[index]=='/')index=i;
if(c=='*'||c=='-')
if(index=n)index=i;
}//for
if(bracket!=0) return FALSE;//括号不匹配
if(index==n){ //只有一个数字，创建只有一个根节点的树
if(have_bracket==TRUE){
*pbtree=NULL;
return FALSE;
}
nint=0; //记录表达式中数字个数
state_int=FALSE; //记录当前读入的字符是否为数字
num=0;
for(i=0;i<n;i++){
c=infix[i];
switch(c){
case'0':case'1':case'2':case'3':case'4':
case'5':case'6':case'7':case'8':case'9':
if(state_int==FALSE){
num=c-'0';
state_int=TRUE;
nint++;
}
else{
num=num*10+c-'0';
}
break;
case' ':case'\t':case'\n':
state_int=FALSE;
break;
*pbtree=NULL;
return FALSE;
}
}
if(nint!=1){
*pbtree=NULL;
return FALSE;
}
*pbtree=(BinTree)malloc(sizeof(struct BinTreeNode));
(*pbtree)->info=num;
(*pbtree)->llink=NULL;
(*pbtree)->rlink=NULL;
return TRUE;
}
*pbtree=(BinTree)malloc(sizeof(struct BinTreeNode));
(*pbtree)->info=infix[index];
tag1=infixtoBintree(&(*pbtree)->llink,infix,index);
tag2=infixtoBintree(&(*pbtree)->rlink,infix+index+1,n-index-1);
if(tag1==TRUE&&tag2==TRUE)return TRUE;
return FALSE;
}
int calculate(BinTree btree,int * presuit){
/*计算二叉树所代表的算术表达式*/
int result1,result2;
if(btree==NULL)return FALSE;
if(btree->llink==NULL&&btree->rlink==NULL){
*presult=btree->info;
return FALSE;
switch(btree->info){
case'+':
if(calculate(btree->llink,&result1)==FALSE)return FALSE;
if(calculate(btree->rlink,&result2)==FALSE)return FALSE;
*presult=result1+result2;
return TRUE;
case'-':
if(calculate(btree->llink,&result1)==FALSE)return FALSE;
if(calculate(btree->rlink,&result2)==FALSE)return FALSE;
*presult=result1-result2;
return TRUE;
case'*':
if(calculate(btree->llink,&result1)==FALSE)return FALSE;
if(calculate(btree->rlink,&result2)==FALSE)return FALSE;
*presult=result1*result2;
return TRUE;
case'/':
if(calculate(btree->llink,&result1)==FALSE)return FALSE;
if(calculate(btree->rlink,&result2)==FALSE)return FALSE;
*presult=result1/result2;
return TRUE;
default:
return FALSE;
}
}
void delete_btree(pbintree ptree){
bintree temp=(*ptree);
if(temp==NULL)return;
delete_btree(&(temp->llink));
delete_btree(&(temp->rlink));
free(temp);
}
void getline(char *line,int limit){
char c;
int i=0;
while(i<limit-1&&(c=getchar))!EOF&&c!='\n')
line[i++]=c;
line[i]='\0';
}
void main(){
char c,infix[MAXNUM];
int result,flag=TRUE;
bintree btree;
while(flag==TRUE){
printf("Please input an\ninput");
getline(infix,MAXNUM);
if(infixtobintree(&btree,infix,strlen(infix))==FALSE){
printf("invalid infix!\n");
delete_btree(&btree);
printf("\ncontinue?(y/n)");
scanf("%c",&c);
if(c=='n'||c=='N')flag=FALSE;
while(getchar()!='\n')
printf("\n");
continue;
}
if(calculate(btree,&result)==TRUE)printf("result:%d\n",result);
else printf("invalid input!\n");
delete_btree(&btree);
printf("\ncontinue(y/n)");
scanf("%c",&c);
if(c=='n'||c=="N")flag=FALSE;
while(getchar()!='\n');
printf("\n");
}
}
