//用數組實現樹
1 #include<iostream> 2 #include<ctype.h> 3 #include<cstring> 4 #define N 10000 5 #define optd 1 6 #define optr 2 7 using namespace std; 8 int treeL[N], treeR[N]; 9 class node 10 { 11 public: 12 int flag;//區分當前節點是操作符還是操作數 13 double k; 14 char ch; 15 }; 16 17 node opt[N]; 18 int nodeN; 19 char formula[1000]; 20 21 int buildTree(int ld, int rd) 22 { 23 int i; 24 for(i=ld; i<rd; ++i) 25 if(!isdigit(formula[i])) 26 break; 27 if(i>=rd)//最后全部為數字的時候 28 { 29 ++nodeN; 30 opt[nodeN].flag=optd; 31 sscanf(formula+ld, "%lf", &opt[nodeN].k); 32 treeL[nodeN]=treeR[nodeN]=0;//末端節點沒有左右孩子 33 return nodeN;//返回當前所建節點編號 34 } 35 int pAS=-1, pMD=-1;//分別表示加減號， 乘除號所在的位置 36 int paren=0;//記錄左括弧相對于右括弧出現的數目 37 for(i=ld; i<rd; ++i) 38 { 39 switch(formula[i]) 40 { 41 case '(': ++paren; break; 42 case ')': --paren; break; 43 44 //最后計算的運算符一定是在括弧的外邊，不會包含在括弧里邊 45 case '+': 46 case '-': 47 if(paren==0) pAS=i; 48 break; 49 case '*': 50 case '/': 51 if(paren==0) pMD=i; 52 break; 53 } 54 } 55 if(pAS<0) pAS=pMD; 56 if(pAS<0) //說明沒有找到括弧外邊的運算符，則脫掉一對括弧重新尋找 57 return buildTree(ld+1, rd-1); 58 int u=++nodeN; 59 opt[u].flag=optr;//表示存儲操作符 60 opt[u].ch=formula[pAS]; 61 treeL[u]=buildTree(ld, pAS); 62 treeR[u]=buildTree(pAS+1, rd); 63 return u; 64 } 65 66 void printTree(int cur)//中序輸出表達式樹 67 { 68 if(cur)//非末端節點 69 { 70 printTree(treeL[cur]); 71 if(opt[cur].flag==optd) 72 cout<<opt[cur].k<<" "; 73 else 74 cout<<opt[cur].ch<<" "; 75 printTree(treeR[cur]); 76 } 77 } 78 79 int main() 80 { 81 while(cin>>formula) 82 { 83 buildTree(0, strlen(formula)); 84 printTree(1); 85 } 86 return 0; 87 }
//用鏈表實現樹
1 #include<iostream> 2 #include<ctype.h> 3 #include<cstring> 4 #define N 10000 5 #define optd 1 6 #define optr 2 7 using namespace std; 8 9 class node 10 { 11 public: 12 node *lchild, *rchild; 13 int flag;//區分當前節點是操作符還是操作數 14 double k; 15 char ch; 16 }; 17 18 char formula[1000]; 19 20 void buildTree(node* &T, int ld, int rd) 21 { 22 int i; 23 for(i=ld; i<rd; ++i) 24 if(!isdigit(formula[i])) 25 break; 26 if(i>=rd)//最后全部為數字的時候 27 { 28 T=new node(); 29 T->flag=optd; 30 sscanf(formula+ld, "%lf", &T->k); 31 return ; 32 } 33 int pAS=-1, pMD=-1;//分別表示加減號， 乘除號所在的位置 34 int paren=0;//記錄左括弧相對于右括弧出現的數目 35 for(i=ld; i<rd; ++i) 36 { 37 switch(formula[i]) 38 { 39 case '(': ++paren; break; 40 case ')': --paren; break; 41 42 //最后計算的運算符一定是在括弧的外邊，不會包含在括弧里邊 43 case '+': 44 case '-': 45 if(paren==0) pAS=i; 46 break; 47 case '*': 48 case '/': 49 if(paren==0) pMD=i; 50 break; 51 } 52 } 53 if(pAS<0) pAS=pMD; 54 if(pAS<0) //說明沒有找到括弧外邊的運算符，則脫掉一對括弧重新尋找 55 return buildTree(T, ld+1, rd-1); 56 T=new node(); 57 T->flag=optr;//表示存儲操作符 58 T->ch=formula[pAS]; 59 buildTree(T->lchild, ld, pAS); 60 buildTree(T->rchild, pAS+1, rd); 61 } 62 63 void printTree(node *T)//中序輸出表達式樹 64 { 65 if(T)//非末端節點 66 { 67 printTree(T->lchild); 68 if(T->flag==optd) 69 cout<<T->k<<" "; 70 else 71 cout<<T->ch<<" "; 72 printTree(T->rchild); 73 } 74 } 75 76 int main() 77 { 78 while(cin>>formula) 79 { 80 node *T=NULL; 81 buildTree(T, 0, strlen(formula)); 82 printTree(T); 83 } 84 return 0; 85 }
?
?
)
)
