|
|
|||||||
| 論壇說明 |
|
歡迎您來到『史萊姆論壇』 ^___^ 您目前正以訪客的身份瀏覽本論壇，訪客所擁有的權限將受到限制，您可以瀏覽本論壇大部份的版區與文章，但您將無法參與任何討論或是使用私人訊息與其他會員交流。若您希望擁有完整的使用權限，請註冊成為我們的一份子，註冊的程序十分簡單、快速，而且最重要的是－－註冊是完全免費的！ 請點擊這裡：『註冊成為我們的一份子！』 |
 |
|
|
主題工具 | 顯示模式 |
2006-11-29, 12:38 PM
|
#1 |
|
|
疑問 - C++堆疊的問題
題目
Input: 鍵入「有多餘無用括符之中序式運算式」: (((a+((b*c)/(d-e))))*(f+g))之一行字串 Output: 顯示「無多於無用括符之中序式運算式」: (a+b*c/(d-e))*(f+g)之一行字串 我寫到這邊 但是還是怪怪的 麻煩大大幫我看一下 語法:
#include<iostream.h>
#define N 80
char stack[N];
int top=-1;
char infix[N]; /*儲存中序運算式*/
char postfix[N]; /*儲存後序運算式*/
/*加入資料於堆疊內*/
void push(int d)
{
if(top == N-1) {
cout<<"堆疊滿了\n";
}
stack[++top]=d;
}
/*刪除堆疊的頂端資料*/
char pop()
{
if(top == -1){
cout<<"堆疊空了\n";
}
return(stack[top--]);
}
/*取得運算符的優先權*/
int p(char d)
{
if(d=='*'||d=='/') /*乘除運算符優先權最高*/
return(2);
else if(d=='+'||d=='-') /*加減運算符優先權次之*/
return(1);
else /*否則必為'('，優先權最低*/
return(0);
}
/*中序運算式轉為後序運算式*/
void infix_to_postfix()
{
char token;
int i=0, j=0;
while((token=infix[i++])!='\0'){ /*讀取下一字元，並判斷是否為結束字元*/
switch(token){
case '(':push(token);
break;
case ')':while(stack[top]!='(')
postfix[j++]=pop();
pop(); /*將'('從堆疊內取出後丟棄不要*/
break;
case '+':
case '-':
case '*':
case '/':/*不為空堆疊時，比較優先權*/
while((top!= -1)&&(p(stack[top])>=p(token)))
postfix[j++]=pop();
push(token);
break;
預設:postfix[j++]=token; /*token為運算元時直接放入後序式*/
} /* end of switch */
} /* end of while */
while(top != -1)
postfix[j++]=pop();
} /* end of infix_to_postfix */
/*主程式*/
void main()
{
cout<<"輸入中序四則運算式:";
infix_to_postfix(); /*呼叫函數將中序式轉為後序式*/
cout<<"則後序四則運算式為:";
}
|
|
送花文章: 0,
|
|
2006-11-30, 01:25 AM
|
#2 (permalink) |
|
管理員
 
|
這個類似的問題我以前有做過，不過當時是使用 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。 純參考。 此帖於 2006-11-30 02:01 AM 被 getter 編輯. |
|
__________________ 在「專業主討論區」中的問題解決後，要記得按一下  按鈕喔，這是一種禮貌動作。  一樣是在「專業主討論區」中發問，不管問題解決與否，都要回應別人的回答文喔。 不然搞 [斷頭文]，只看不回應，下次被別人列入黑名單就不要怪人喔。 天線寶寶說再見啦~ ... 天線寶寶說再見啦~ 迪西：「再見~ 再見~」 『 Otaku Culture Party 』 關心您 ... 
|
|
|
送花文章: 37855,
|
|
2006-11-30, 01:50 AM
|
#3 (permalink) |
|
管理員
|
你的程式ㄚ 我用 DEV-C++ 以 CPP 做編譯發現一些錯誤
原 - 1, 錯誤訊息一大推 語法:
預設:postfix[j++]=token; /*token為運算元時直接放入後序式*/ 語法:
postfix[j++]=token; /* 預設: token為運算元時直接放入後序式*/ 語法:
void main() 語法:
main() 1.比方說 C 語言的 scanf() ，或是 C++ 的 cin。 2.使用 int main(int argc, char *argv[])使用 CMD 模式來輸入資料。 還是測試中，先把公式值些給到 infix[N] 中，我試著把 char infix[N] = (((a+((b*c)/(d-e))))*(f+g)); 先給好...，畫面顯示只有一行【 輸入中序四則運算式:則後序四則運算式為: 】 看樣子這 ... 還有很多地方可能要仔看細過， 如果說是要檢查 多餘括號的話 可以在讀入 終至運算式做 連續性的統計，( 連續出現幾次 -1 ，比較 ) 連續出現幾次 -1 來做比較 A == B 時，代表著可能是有多的無用 ()之類， 在某個優先層級作比較可能要從最內部比較出來吧。 可能的話還需要考慮結合律做為過濾條件。 加油吧！！ 此帖於 2006-11-30 02:10 AM 被 getter 編輯. |
|
|
送花文章: 37855,
|
|
向 getter 送花的會員:
|
|
2006-12-02, 07:29 PM
|
#5 (permalink) |
|
|
我有照大大的方法改完 你說的新方法 後轉中 我有想過 我跟我這組的同學都是想用這種方法 但是我們班好像沒有人寫出來 都卡在這邊
語法:
#include<iostream.h>
#define N 80
char stack[N];
int top=-1;
char infix[N]; /*儲存中序運算式*/
char postfix[N]; /*儲存後序運算式*/
/*加入資料於堆疊內*/
void push(int d)
{
if(top == N-1) {
cout<<"堆疊滿了\n";
}
stack[++top]=d;
}
/*刪除堆疊的頂端資料*/
char pop()
{
if(top == -1){
cout<<"堆疊空了\n";
}
return(stack[top--]);
}
/*取得運算符的優先權*/
int p(char d)
{
if(d=='*'||d=='/') /*乘除運算符優先權最高*/
return(2);
else if(d=='+'||d=='-') /*加減運算符優先權次之*/
return(1);
else /*否則必為'('，優先權最低*/
return(0);
}
/*中序運算式轉為後序運算式*/
void infix_to_postfix()
{
char token;
int i=0, j=0;
while((token=infix[i++])!='\0'){ /*讀取下一字元，並判斷是否為結束字元*/
switch(token){
case '(':push(token);
break;
case ')':while(stack[top]!='(')
postfix[j++]=pop();
pop(); /*將'('從堆疊內取出後丟棄不要*/
break;
case '+':
case '-':
case '*':
case '/':/*不為空堆疊時，比較優先權*/
while((top!= -1)&&(p(stack[top])>=p(token)))
postfix[j++]=pop();
push(token);
break;
default:postfix[j++]=token; /*token為運算元時直接放入後序式*/
} /* end of switch */
} /* end of while */
while(top != -1)
postfix[j++]=pop();
} /* end of infix_to_postfix */
/*主程式*/
void main()
{
cout<<"輸入中序四則運算式:";
cin>>infix;
infix_to_postfix(); /*呼叫函數將中序式轉為後序式*/
cout<<"則後序四則運算式為:"<<postfix;
}
|
|
送花文章: 0,
|
平板模式
