[問題] 建立二元算式樹

看板C_and_CPP作者king5014 (讀書人)時間15年前 (2010/06/05 22:38)推噓2(2推 0噓 11→)

留言13則, 2人參與討論串1/1

遇到的問題： (題意請描述清楚) 讀入一個中序運算式建立二元運算樹並印出前中後序我找到一個演算法利用指標堆疊來做如果要輸出一個運算元(數字)時則建立一個新節點，儲存此運算元其左右兩指標欄設定為NULL 並且將節點指標push置入指標堆疊sopd中一個指標堆疊sopd儲存指標然後運算子堆疊spor存+-*/ 如果要輸出一個運算子時若此運算子之(優先權<=Sopr) 則由Sopr pop出運算子且建立新節點，儲存此運算子，並且由指標堆疊sopd中pop彈出一個指標，存入新節點的右指標欄，再由sopd中彈出一個指標，存入新節點的左指標欄，然後將新節點指標再push置入sopd堆疊中。否則直接將此運算子push到Sopr 假設我輸入1+2*3 應該建立指標堆疊 sopd □□□□□□ 運算子堆疊sopr ↓ + □ 1 * □ 2 3 □←top 但是我的程式跑出來卻變成 sopd □□□□□□ 運算子堆疊sopr ↓↓↓ [ ] 1 2 3 [*]←top [+] 程式碼在下面(上色部分為演算法部分) 想破頭了不知怎麼改才對煩請高人指點開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux) VC6.0 有問題的code： (請善用置底文標色功能) #include <stdio.h> #include <stdlib.h> typedef struct Node { char data; struct Node* L; struct Node* R; }; Node* root; char stack[80]; //運算子堆疊 struct Node* nodeStack[80];//指標堆疊 int top=-1; int p=-1; char infix[80]; /*儲存中序運算式*/ void inOrder( Node* ROOT ) { if( ROOT != NULL ) { inOrder( ROOT->L ); printf( "%c\r\n", ROOT->data ); inOrder( ROOT->R ); } } void preOrder( Node* ROOT ) { if( ROOT != NULL ) { printf( "%c\r\n", ROOT->data ); preOrder( ROOT->L ); preOrder( ROOT->R ); } } void postOrder( Node* ROOT ) { if( ROOT != NULL ) { postOrder( ROOT->L ); postOrder( ROOT->R ); printf( "%c\r\n", ROOT->data ); } } void inserttree(Node left,Node right, Node father){ } int prio(char a){//優先權 switch(a){ case '+': return 1; case '-': return 1; case '*': return 2; case '/': return 2; default : return 0; } } void soprPush(char d) ////////////////////////////////////////// { top++; stack[top]=d; } /*刪除堆疊的頂端資料*/ char soprPop() ////////////////////////////////////////// { if(top == -1){ return 'z'; } else{ return(stack[top--]); //top--; } } void sopdPush(struct Node* N) { //假設此stack的pointer 是 P p++; nodeStack[p] = N; } struct Node* sopdPop() { //假設此stack的pointer 是 P if(p!=-1){ return nodeStack [p--]; } else return 0; } int main() { char *infix; infix=(char*)malloc( sizeof(char) ); // gets(infix); infix[0]='1'; infix[1]='+'; infix[2]='2'; infix[3]='*'; infix[4]='3'; struct Node* tmp; struct Node* oper; char token; int i=0, j=0; char test; while((token=infix[i++])!='\0'){ switch(token){ case '+': case '-': case '*': case '/': if(top!=-1){ test=soprPop();// 取出sopr頂端暫不做pop 只是比較 top++; } else test=0; if(prio(token)<=prio(test)){ oper = (struct Node*)malloc( sizeof(struct Node) ); oper->data =soprPop(); oper->L = sopdPop(); oper->R = sopdPop(); sopdPush(oper); } else soprPush(token); break; default: tmp = (struct Node*)malloc( sizeof(struct Node) ); tmp->data = token; tmp->L = NULL; tmp->R = NULL; sopdPush(tmp); } } printf( "Print Tree by inorder\r\n" ); inOrder(nodeStack[0]); // 傳值呼叫 printf( "Print Tree by preOrder\r\n" ); preOrder( nodeStack[0] ); // 傳值呼叫 printf( "Print Tree by postOrder\r\n" ); postOrder( nodeStack[0] ); // 傳值呼叫 system( "PAUSE" ); return 0; } 補充說明： -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.136.250.5 ※ 編輯: king5014 來自: 114.136.250.5 (06/05 22:40) ※ 編輯: king5014 來自: 114.136.250.5 (06/05 22:41)

→

loveme00835

06/05 23:20, , 1^F

06/05 23:20, 1^F

→

loveme00835

06/05 23:21, , 2^F

06/05 23:21, 2^F

→

loveme00835

06/05 23:23, , 3^F

06/05 23:23, 3^F