Zi 字媒體

[C/C++ 演算法]-資料結構與演算法(文魁)：中序表示法轉後序表示法之演算法(1)   線上執行結果：http://www.tutorialspoint.com/compile_c_online.php code2html：http://tohtml.com/     /* =============== Program Description =============== */ /* 程式名稱 : 7_3_3.cpp */ /* 程式目的 : 中序表示法轉後序表示法之演算法 */ /* 輸 入 : 中序表示法的字串陣列資料 */ /* 輸 出 : 前序表示法的字串陣列資料 */ /* =================================================== */ #define n 12 // 宣告標頭檔 #include "stdio.h" // 宣告全域變數 char Stack[n]; int top=-1; // 宣告函式原型 // 利用傳址的方式把Array A傳進parsing2函式中 void parsing2(char *A); int isOperand(char ch); /* 判斷��否為運算元 */ int isEmpty(void); /* 判斷堆疊��否為空 */ int isFull(void); /* 判斷堆疊��否滿了 */ char pop(void); /* 由堆疊取出資料 */ void push(char ch); /* 將資料放入堆疊 */ int priority(char op); /* 判斷運算符號優先順序 */ void main(void) { char A[n]="1+2*(3-4)/2"; // 轉換前的資料 printf(" Data before parsing : %s\n",A); printf("\n"); parsing2(A); // 轉換後的資料 printf(" Data after parsing : %s\n",A); printf("\n"); getchar(); } void parsing2(char *A) { int i,j=0,m=0; char ch,ch1; char B[n]; for(i=n-2;i>=0;i--) { ch = A[i]; if(isOperand(ch)) B[j++]=ch; else { if(ch==')') { m++; push(ch); }else if(ch=='(') { m++; while(!isEmpty()) { ch = pop(); if(ch==')') break; else B[j++] = ch; } }else{ if(!isEmpty()) { do { ch1 = pop(); if(priority(ch1)>priority(ch)) { B[j++] = ch1; if(isEmpty()) { push(ch); break; } } else{ push(ch1); push(ch); break; } }while(!isEmpty()); }else{ push(ch); } } } } while(!isEmpty()) B[j++] = pop(); for(i=0;i<n-1-m;i++) A[n-2-m-i]=B[i]; A[n-1-m]='\0'; } int isOperand(char ch) { int ret; switch(ch) { case '+': case '-': case '*': case '/': case '(': case ')': ret = 0; break; default: ret = 1; break; } return ret; } int isEmpty(void) { if(top==-1) return 1; else return 0; } int isFull(void) { if(top==n-1) return 1; else return 0; } char pop(void) { char ch = Stack[top]; Stack[top] = 0; top--; return ch; } void push(char ch) { Stack[++top]=ch; } int priority(char op) { int p; switch(op) { case '+': case '-': p = 1; break; case '*': case '/': p = 2; break;         default: p = 0; break; } return p; }