這個類似的問題我以前有做過，不過當時是使用 C 語言寫的
有分成 Array 跟 Link-Nixt 兩種之料結構所創制的 STACK
來進行轉換 ...，當時我是參考 C++ 的程式碼來寫的。然後
看了你的程式發現，基本的樣子是差不多的。
題目: 中置運算式 轉 後置運算式
Array 的 STACK 的程式碼 - 1
語法:
/*
array 堆疊 - 中置運算式轉後至運算是程式
*/
#include <add_tc.h> /* 載入引導檔 add_tc.h */
#define size 10 /* 設定堆疊巨集 Size 為 10 */
#define N 50 /* 設定巨集 N 為 10 */
chr Stk_A[size]={0}; /* 堆疊用變數的宣告 */
chr top=0,e=0,tp; /* 堆疊用變數的宣告 */
chr in[N],ss[N],a,b; /* 輸入字陣、輸出字陣、字元讀取器 */
int ia,ja; /* 累加變數器 */
/* top 為空資料頂湍，-1 之後為有資料的頂端，tp 為頂端的資料 */
/* e 堆疊錯誤編碼 1、3 為正常，2、4為錯誤，其他數字為未知*/
int pop(int d); /* 堆疊資料取出 */
int push(int str,int d); /* 堆疊資料塞入 */
int clr_stk(); /* 淨空堆疊 */
int msn00(); /* 堆疊錯誤碼_00 */
int msn01(); /* 堆疊錯誤碼_01 */
int msn02(chr *a); /* 算式檢查錯誤碼_02 */
int msn03(chr *a); /* 算是檢查錯誤碼_03 */
int chk_AB(chr *txt,int d); /* 運算式括號檢查 */
int p2(int c); /* 回傳運算子優先順序的方法 */
int pos2fix(); /* 運算式轉換：中置式 2 後置式 */
main()
{
clrscr();
printf("\n中置運算式轉後至運算是程式\n\n請輸入中置運算式 : ");
scanf("%s",in);
AA:
if(chk_AB(in,0))
{
pos2fix();
prints(2,"\n");
printf("輸出的運算式 : %-50s",ss);
}
else
{
if(e==2|e==4)
{
printf("\n > > 括號太多超過堆疊負荷\n");
}
else { printf("\n > > 剛才輸入的運算式 %s 的括號有錯誤\n",in); }
clr_stk();
printf("\n%s",in);
printf("\n請重新輸入中置運算式 : ");
scanf("%s",in);
goto AA;
}
prn(2,"\n");
printf("程式結束");
prn(2,"\n");
pause();
}
pos2fix() /* 運算式轉換：中置式 2 後置式 */
{
int inlen;
inlen=strlen(in);
for(ia=ja=0;ia<=inlen;ia++)
{
a=in[ia]; /* 取樣字元 */
b=in[ia+1]; /* 取樣字元 */
switch(a)
{
case '(': /* 檢查是否為 ( 運算子的作業處理 */
push(a,0);
break;
case ')': /* 檢查是否為 ) 運算子的作業處理 */
while(tp!='('){ ss[ja++]=pop(0); }
pop(0);
break;
/* 檢查是否為 +、-、*、- 運算子的作業處理 */
case '+': case '-': case '*': case '/':
if((p2(a)==1|p2(a)==2)&(p2(b)==1|p2(b)==2) ){ continue; } /* 排除連續運算子 */
while(p2(tp)>=p2(a)){ ss[ja++]=pop(0); }
push(a,0);
break;
case '\0': /* 檢查是否為 \0 的作業處理 */
while(top>0){ ss[ja++]=pop(0); }
return;
default: /* 運算元的處理 */
ss[ja++]=a;
break;
}
}
}
p2(int c) /* 回傳運算子優先順序的方法 */
{
switch(c)
{
default: case '(':
return 0;
case '+': case '-':
return 1;
case '*': case '/':
return 2;
}
}
chk_AB(chr *txt,int d) /* 運算式括號檢查 */
{
int i,slen;
chr ct;
if(d!=1){ d=0; }
slen=strlen(txt);
for(i=0;i<slen;i++)
{
ct=txt[i];
if(ct=='(') { push('(',0); }
else if(ct==')' )
{
if(!pop(0))
{
if(d){ msn02(txt); }
return 0;
}
}
}
if(top==0)
{
if(e==2|e==4){ return 0; }
if(d){ msn03(txt); }
return 1;
}
else
{
if(d){ msn02(txt); }
return 0;
}
}
push(int str,int d) /* 堆疊資料塞入 */
{
if(d!=1){ d=0; }
if(top>=size)
{
if(d){ msn00(); }
e=2;
return 0;
}
else
{
Stk_A[top]=str;
tp=Stk_A[top];
top++;
e=1;
return 1;
}
}
pop(int d) /* 堆疊資料取出 */
{
chr str;
if(d!=1){ d=0; }
if(top<=0)
{
if(d){ msn01(); }
e=4;
return 0;
}
else
{
top--;
str=Stk_A[top];
tp=Stk_A[top-1];
Stk_A[top]=0;
e=3;
return str;
}
}
clr_stk() /* 淨空堆疊 */
{
top=0;
e=0;
tp=0;
}
msn00() /* 堆疊錯誤碼_00 */
{
clrscr();
prn(2,"\n");
printf("msn_00: 堆疊已滿，資料堆入失敗。");
prn(2,"\n");
pause();
}
msn01() /* 堆疊錯誤碼_01 */
{
clrscr();
prn(2,"\n");
printf("msn_01: 堆疊已空，資料取出失敗。");
prn(2,"\n");
pause();
}
msn02(chr *a) /* 算式檢查錯誤碼_02 */
{
clrscr();
prn(2,"\n");
printf("");
printf("運算式 %s 的括號有錯誤。",a);
prn(2,"\n");
pause();
}
msn03(chr *a) /* 算是檢查錯誤碼_03 */
{
clrscr();
prn(2,"\n");
printf("運算式 %s 的號檢查正確。",a);
prn(2,"\n");
pause();
}
Array 的 STACK 的程式碼 - 2
語法:
/*
array 堆疊：中置運算式轉後至運算是程式，過程顯示版
*/
#include <add_tc.h> /* 載入引導檔 add_tc.h */
#define size 10 /* 設定堆疊巨集 Size 為 10 */
#define N 50 /* 設定巨集 N 為 10 */
chr Stk_A[size]={0}; /* 堆疊用變數的宣告 */
chr top=0,e=0,tp; /* 堆疊用變數的宣告 */
chr in[N],ss[N],a,b; /* 輸入字陣、輸出字陣、字元讀取器 */
int ia,ja; /* 累加變數器 */
/* top 為空資料頂湍，-1 之後為有資料的頂端，tp 為頂端的資料 */
/* e 堆疊錯誤編碼 1、3 為正常，2、4為錯誤，其他數字為未知*/
int pop(int d); /* 堆疊資料取出 */
int push(int str,int d); /* 堆疊資料塞入 */
int Disp_s(); /* 顯示整個堆疊 */
int clr_stk(); /* 淨空堆疊 */
int msn00(); /* 堆疊錯誤碼_00 */
int msn01(); /* 堆疊錯誤碼_01 */
int msn02(chr *a); /* 算式檢查錯誤碼_02 */
int msn03(chr *a); /* 算是檢查錯誤碼_03 */
int chk_AB(chr *txt,int d); /* 運算式括號檢查 */
int p2(int c); /* 回傳運算子優先順序的方法 */
int pos2fix(); /* 運算式轉換：中置式 2 後置式 */
main()
{
clrscr();
printf("\n中置運算式轉後至運算是程式\n\n請輸入中置運算式 : ");
scanf("%s",in);
AA:
if(chk_AB(in,0))
{
pos2fix();
/*
prints(2,"\n");
printf("輸出的運算式 : %-50s",ss);
*/
}
else
{
if(e==2|e==4)
{
printf("\n > > 括號太多超過堆疊負荷\n");
}
else { printf("\n > > 剛才輸入的運算式 %s 的括號有錯誤\n",in); }
clr_stk();
printf("\n%s",in);
printf("\n請重新輸入中置運算式 : ");
scanf("%s",in);
goto AA;
}
prn(2,"\n");
printf("程式結束");
prn(2,"\n");
pause();
}
pos2fix() /* 運算式轉換：中置式 2 後置式 */
{
int inlen;
inlen=strlen(in);
for(ia=ja=0;ia<=inlen;ia++)
{
a=in[ia]; /* 取樣字元 */
b=in[ia+1]; /* 取樣字元 */
switch(a)
{
case '(': /* 檢查是否為 ( 運算子的作業處理 */
push(a,0);
Disp_s();
break;
case ')': /* 檢查是否為 ) 運算子的作業處理 */
while(tp!='(')
{
ss[ja++]=pop(0);
Disp_s();
}
pop(0);
Disp_s();
break;
/* 檢查是否為 +、-、*、- 運算子的作業處理 */
case '+': case '-': case '*': case '/':
if((p2(a)==1|p2(a)==2)&(p2(b)==1|p2(b)==2) ){ continue; } /* 排除連續運算子 */
while(p2(tp)>=p2(a))
{
ss[ja++]=pop(0);
Disp_s();
}
push(a,0);
Disp_s();
break;
case '\0': /* 檢查是否為 \0 的作業處理 */
while(top>0)
{
ss[ja++]=pop(0);
Disp_s();
}
return;
default: /* 運算元的處理 */
ss[ja++]=a;
Disp_s();
break;
}
Disp_s();
}
}
p2(int c) /* 回傳運算子優先順序的方法 */
{
switch(c)
{
default: case '(':
return 0;
case '+': case '-':
return 1;
case '*': case '/':
return 2;
}
}
chk_AB(chr *txt,int d) /* 運算式括號檢查 */
{
int i,slen;
chr ct;
if(d!=1){ d=0; }
slen=strlen(txt);
for(i=0;i<slen;i++)
{
ct=txt[i];
if(ct=='(') { push('(',0); }
else if(ct==')' )
{
if(!pop(0))
{
if(d){ msn02(txt); }
return 0;
}
}
}
if(top==0)
{
if(e==2|e==4){ return 0; }
if(d){ msn03(txt); }
return 1;
}
else
{
if(d){ msn02(txt); }
return 0;
}
}
Disp_s() /* 顯示整個堆疊 */
{
int ix,jx;
clrscr();
jx=size-1;
printf("堆疊狀態顯示器 Stk_A ：\n");
for(ix=0;ix<=jx;ix++)
{
printf("%02d:[ %c = %3d ] \t",size-ix,Stk_A[jx-ix],Stk_A[jx-ix]);
if(ix==1){ printf("堆疊大小 :[ %2d ]",size); }
if(ix==2){ printf("top旗標 :[%d]",top); }
if(ix==2){ printf("\t\ttp 頂標 :[ %c = %3d ] ",tp,tp); }
if(ix==3)
{
printf("堆暫狀態 :[");
if(e==2){ printf("錯誤]"); } else printf("%s]",e==1?"正常":"未知");
}
if(ix==3)
{
printf("\t取出狀態 :[");
if(e==4){ printf("錯誤]"); } else printf("%s]",e==3?"正常":"未知");
}
if(ix==4){ printf(" a 字元取樣 :[ %c = %3d ] ",a,a); }
if(ix==4){ printf("運算優先序:[ %1d ]",p2(a)); }
if(ix==5){ printf("堆疊頂端資料:[ %c = %3d ] ",Stk_A[top-1],Stk_A[top-1]); }
if(ix==5){ printf("運算優先序:[ %1d ]",p2(Stk_A[top-1])); }
if(ix==6){ printf("ia累加器 :[ %2d ]",ia); }
if(ix==7){ printf("ja累加器 :[ %2d ]",ja); }
printf("\n");
}
printf("\n輸入的運算式:[ %-50s ]\n",in);
prints(15," ");
for(ix=0;ix<ia;ix++){ printf("%-s"," "); }
printf("%-2s","^");
printf("\n輸出的運算式:[ %-50s ]\n",ss);
prints(15," ");
for(ix=0;ix<ja-1;ix++){ printf("%-s"," "); }
printf("%-2s","^");
/*
prints(2,"\n");
pause();
*/
}
push(int str,int d) /* 堆疊資料塞入 */
{
if(d!=1){ d=0; }
if(top>=size)
{
if(d){ msn00(); }
e=2;
return 0;
}
else
{
Stk_A[top]=str;
tp=Stk_A[top];
top++;
e=1;
return 1;
}
}
pop(int d) /* 堆疊資料取出 */
{
chr str;
if(d!=1){ d=0; }
if(top<=0)
{
if(d){ msn01(); }
e=4;
return 0;
}
else
{
top--;
str=Stk_A[top];
tp=Stk_A[top-1];
Stk_A[top]=0;
e=3;
return str;
}
}
clr_stk() /* 淨空堆疊 */
{
top=0;
e=0;
tp=0;
}
msn00() /* 堆疊錯誤碼_00 */
{
clrscr();
prn(2,"\n");
printf("msn_00: 堆疊已滿，資料堆入失敗。");
prn(2,"\n");
pause();
}
msn01() /* 堆疊錯誤碼_01 */
{
clrscr();
prn(2,"\n");
printf("msn_01: 堆疊已空，資料取出失敗。");
prn(2,"\n");
pause();
}
msn02(chr *a) /* 算式檢查錯誤碼_02 */
{
clrscr();
prn(2,"\n");
printf("");
printf("運算式 %s 的括號有錯誤。",a);
prn(2,"\n");
pause();
}
msn03(chr *a) /* 算是檢查錯誤碼_03 */
{
clrscr();
prn(2,"\n");
printf("運算式 %s 的號檢查正確。",a);
prn(2,"\n");
pause();
}
這兩支程式的差別是，一個只是單純的轉換，另一個是會顯示操作過程的
轉換
下載 STACK.rar
內有原始碼 & 執行檔 + 基本 STACK 模擬 (Array & Link next)
http://www.badongo.com/file/1792707
附註 : 當時因為作業抄襲太嚴重阿，我使用了一些改造指令
如: prn(2,"\n"); 表示 斷行 2 次
其實是 prn(列印數量,"列印文字");
pause(); 只是暫停
clrscr(); 清除畫面
chr = char
之類...
這些程式ㄚ，具有
1.稍為嚴謹的 () 號除錯功能，不成對或錯置時揪出。
2. 1*(x-y) = 1(x-y)。
3.當不小心連續輸入運算子時，會以最後的運算子為主。
如： 1*/3 = 1/3、 3-*/+5 = 3+5。
純參考。