/*頭文件*/
	#include
	#include
	#include
	#include
#include
#define?TRUE?1
#define?FALSE?0
#define?OK?1
#define?ERROR?0

#define?STACK_INIT_SIZE?100
#define?STACKINCREMENT?10
///數據類型定義
typedef?int?Status;
typedef?struct?BiTNode//樹的存儲結構
{
int?tdata;//放int數據，當有數字時，data[0]=‘&‘，用‘&‘標志結點放的是數字
char?data[10];//放字母字符串或是運算符號字符
struct?BiTNode?*lchild*rchild;
}BiTNode*BiTree;
///棧的數據類型定義
typedef?char?SElemType;
typedef?struct
{
SElemType?*base;
SElemType?*top;
int?stacksize;
}SqStack;?
/////////////棧函數定義
Status?IntiStack（SqStack?&S）?//初始化棧函數
{S.base=（char?*）malloc（STACK_INIT_SIZE*sizeof（char））;
if?（!S.base）?return?ERROR;
S.top=S.base;S.stacksize=STACK_INIT_SIZE;return?OK;}

Status?DestroyStack（SqStack?&S）?//銷毀函數
{free（S.base）;S.top=S.base=NULL;return?OK;}

int?StackLength（SqStack?S）?//求棧存儲的長度函數
{int?i=S.top-S.base;return?i;}

Status?Push（SqStack?&S?char?e）?//把e插入到棧頂函數
{
if?（S.top-S.base>=S.stacksize）
{
S.base=（SElemType?*）realloc（S.base
（S.stacksize+STACKINCREMENT）*sizeof（SElemType））;//當棧滿的時候重新分配空間
if?（!S.base）?return?ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
*S.top++=e;?return?OK;}
*S.top++=e;?return?OK;
}

char?Pop（SqStack?&S）//刪除棧頂并用e返回?函數
{if（S.top==S.base）?return?ERROR;
char?e=*--S.top;return?e;}
char?gettop（SqStack?&Schar?&e）//取棧頂元素的函數
{?if?（S.top<0）{
	return?ERROR;?
}??????//棧空，返回空值
?????????else?{?
???????????????????e=*（S.top-1）;
??????????????????	return?e;?
???????????????}
????????}??//?gettop
Status?StackEmpty?（SqStack?&S）
?????{?if?（S.top==S.base）
??????????????return?OK;???????//棧空，返回OK
?????????else?{?
???????????????????return?ERROR;
?????????????????}
????????}??//?empty

char?in[100]in2[100];//假設表達式最多有100個字符，“#”表示輸入完畢
SqStack?S;?//借用該棧來實現阿拉伯數字的輸入
int?a=0;?//定義該全局變量來一個一個地初始化樹
int?i=0j=0;//定義全局變量
char?OP[5]={‘+‘‘-‘‘*‘‘/‘‘^‘};//運算符
///////////////函數定義
Status?IntiBiTree（BiTree?&T）
{
T=NULL;
return?OK;
}
Status?DestroyBiTree（BiTree?&T）
{?if（T->lchild）
????DestroyBiTree（T->lchild）;
??if（T->rchild）
	??DestroyBiTree（T->rchild）;
free（T）;
T=NULL;
return?OK;
}
void?input（）?{?//輸入表達式的函數
char?d=‘a‘;
for（int?b=0;d!=‘#‘;b++）
{?
scanf（“%c“&d）;
in[b]=d;//附給in[100]數組
}
getchar（）;//接收回車鍵字符
}
int?pow10（int?b）///10的b?次方
{int?c=1;
for（int?q=1;q<=b;q++）c=c*10;
return?c;
}?
Status?CreateBiTree（BiTree?&T）//創建表達式類型的樹
{?int?y;
while（in[a]!=‘#‘）//以#結束
{
if（in[a]==‘-‘||in[a]==‘+‘||in[a]==‘*‘||in[a]==‘/‘||in[a]==‘^‘）//當字符為運算符時
{
if?（!（T=（BiTNode?*）malloc（sizeof?（BiTNode））））?return?ERROR;
T->data[0]=in[a];//字符數組的第一個元素為運算符
T->data[1]=‘@‘;//以‘@‘作為結尾的標志
T->tdata=0;//初始化變量
a++;
CreateBiTree（T->lchild）;//運算符需要建立它的左右孩子
CreateBiTree（T->rchild）;
return?OK;?
}
else
{
if（in[a]==‘0‘||in[a]==‘1‘||in[a]==‘2‘||in[a]==‘3‘||in[a]==‘4‘||
in[a]==‘5‘||in[a]==‘6‘||in[a]==‘7‘||in[a]==‘8‘||in[a]==‘9‘）//當字符是阿拉伯數字時
{
Push（S?in[a]）;//建一個棧來放阿拉伯數字
if（in[a+1]!=‘0‘&&in[a+1]!=‘1‘&&in[a+1]!=‘2‘&&i

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件??????23017??2008-07-04?14:40??數據結構課程設計\2.cpp

?????文件??????50176??2008-07-31?17:11??數據結構課程設計\2.ncb

?????文件????????719??2008-07-31?16:45??數據結構課程設計\2.plg

?????文件??????41984??2008-07-31?16:45??數據結構課程設計\Debug\vc60.idb

?????文件??????53248??2008-07-31?16:44??數據結構課程設計\Debug\vc60.pdb

?????文件?????459776??2008-07-31?16:45??數據結構課程設計\Debug\2.pdb

?????文件?????237666??2008-07-31?16:45??數據結構課程設計\Debug\2.exe

?????文件??????48091??2008-07-31?16:44??數據結構課程設計\Debug\2.obj

?????文件??????55808??2008-07-04?15:23??數據結構課程設計\數據結構課程設計的封面.doc

?????文件?????223744??2008-07-05?23:44??數據結構課程設計\數據結構課程設計實驗報告.doc

?????文件???????3341??2008-07-31?16:44??數據結構課程設計\2.dsp

?????文件??????48640??2008-07-31?17:11??數據結構課程設計\2.opt

?????文件????????510??2008-07-31?17:11??數據結構課程設計\2.dsw

?????目錄??????????0??2008-07-04?15:19??數據結構課程設計\Debug

?????目錄??????????0??2008-07-04?15:19??數據結構課程設計

-----------?---------??----------?-----??----

??????????????1246720????????????????????15