#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define MAXNUM 1000
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 extoBinTree(PBinTree pbtree,const char *ex,int n)
/*從中綴運算式ex(長度為n)創建二叉樹。若是一個合法的運算式，則回傳TRUE，且演算法結束時*pbtree存放二叉樹的根節點的地址；否則回傳FALSE*/
{
char c;
int index,i,bracket;
int have_bracket=FALSE; /*記錄運算式中是否包含括號*/
int num,state_int,nint;
int tag1,tag2;
if(ex[0]==' '||ex[0]=='\t'||ex[0]=='\n')
return extoBinTree(pbtree,ex+1,n-1);/*忽略掉左邊的若干空字符*/
if(ex[n-1]==' '||ex[0]=='\t'||ex[0]=='\n')
return extoBinTree(pbtree,ex,n-1);/*忽略掉右邊的若干空字符*/
if(ex[0]=='('&&ex[n-1]==')')
return extoBinTree(pbtree,ex+1,n-2);/*忽略掉左右的成對括號*/
bracket=0;
index=n;
for(i=n-1;i>=0;i--)/*從后向前搜索，尋找到第一個不在括號中的優先級最低的運算子*/
{
c=ex[i];
if(c==')')/*進入一層括號*/
{
have_bracket=TRUE;
bracket++;
}
if(c=='(') bracket--;/*出一層括號*/
if(bracket<0)/*左右括號不相匹配，運算式非法*/
{
*pbtree=NULL;
return FALSE;
}
if(bracket>0) continue;/*若當前位置在某層括號中，直接搜索下個位置*/
if(c=='+'||c=='-')
if(index==n||ex[index]=='*'||ex[index]=='/')
index=i;
if(c=='*'||c=='/')
if(index==n)
index=i;
}
if(bracket!=0) return FALSE;/*左右括號不相匹配，運算式非法*/
if(index==n)/*說明這是一個只含一個數字和若干空字符的運算式，相應地創建一棵只含一個根節點的二叉樹*/
{
if(have_bracket==TRUE)
{
*pbtree=NULL;
return FALSE;
}/*不應含有括號*/
nint=0;/*nint記錄運算式中含有的整數個數*/
state_int=FALSE;/*state_int記錄當前讀入的字符是否是數字字符*/
num=0;
for(i=0;i<n;i++)
{
c=ex[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;
default: /*出現了非法字符*/
*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=ex[index];
tag1 =extoBinTree(&(*pbtree)->llink,ex,index);/*遞回呼叫本演算法創建左子數*/
tag2 =extoBinTree(&(*pbtree)->rlink,ex+index+1,n-index-1);/*遞回呼叫本演算法創建右子數*/
if(tag1==TRUE&&tag2==TRUE) return TRUE;
return FALSE;
}
int cal(BinTree btree,int*presult)/*計算二叉樹btree所代表的運算式的值。若是一個合法的運算式，則回傳TRUE，且演算法結束時*presult中存放計算結果；否則，回傳FALSE.*/
{
int result1,result2;
if(btree==NULL) return FALSE; /*空樹，無法計算*/
if(btree->llink==NULL&&btree->rlink==NULL) /*只有一個節點，直接計算*/
{
*presult=btree->info;
return TRUE;
}
if(btree->llink==NULL||btree->rlink==NULL) /*只有左子樹或只有右子樹，無法計算*/
return FALSE;
switch(btree->info)
{
case'+':
if(cal(btree->llink,&result1)==FALSE) return FALSE;
if(cal(btree->rlink,&result2)==FALSE) return FALSE;
*presult=result1+result2;
return TRUE;
case'-':
if(cal(btree->llink,&result1)==FALSE) return FALSE;
if(cal(btree->rlink,&result2)==FALSE) return FALSE;
*presult=result1-result2;
return TRUE;
case'*':
if(cal(btree->llink,&result1)==FALSE) return FALSE;
if(cal(btree->rlink,&result2)==FALSE) return FALSE;
*presult=result1*result2;
return TRUE;
case'/':
if(cal(btree->llink,&result1)==FALSE) return FALSE;
if(cal(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)/*從標準輸入中讀入一行，作為字串line*/
{
char c;
int i=0;
while(i<limit-1&&(c=getchar())!=EOF&&c!='\n')
line[i++]=c;
line[i]='\0';
}
int main()
{
char c,ex[MAXNUM];
int result,flag=TRUE;
BinTree btree;
while(flag==TRUE)
{
printf("請輸入運算式:");
getline(ex,MAXNUM);/*讀入中綴運算式*/
if(extoBinTree(&btree,ex,strlen(ex))==FALSE)
{
printf("輸入有誤!\n");
delete_BTree(&btree);
printf("\n繼續?(y(是)/n(否):");
scanf("%c",&c);
if(c=='n'||c=='N') flag=FALSE;
while(getchar()!='\n');
printf("\n");
continue;
}
if(cal(btree,&result)==TRUE) printf("Result:%d\n",result);
else printf("Wrong input!\n");
delete_BTree(&btree);
printf("\n繼續?(y(是)/n(否)):");
scanf("%c",&c);
if(c=='n'||c=='N') flag=FALSE;
while(getchar()!='\n');
printf("\n");
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/58986.html
標籤：基礎類
上一篇：離散實驗：通過求命題公式的成真賦值，來解決實際問題（看不懂）
下一篇：求大神解答關于無線通信方面的問題