史萊姆論壇

史萊姆論壇 (http://forum.slime.com.tw/)
-   程式語言討論區 (http://forum.slime.com.tw/f76.html)
-   -   C++堆疊的問題 (http://forum.slime.com.tw/thread192450.html)

onlyaway 2006-11-29 12:38 PM
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<<"則後序四則運算式為:";
 }

getter 2006-11-30 01:25 AM
這個類似的問題我以前有做過，不過當時是使用 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。

純參考。

getter 2006-11-30 01:50 AM
你的程式ㄚ 我用 DEV-C++ 以 CPP 做編譯發現一些錯誤

原 - 1, 錯誤訊息一大推
語法:
預設:postfix[j++]=token;  /*token為運算元時直接放入後序式*/
改 - 1:
語法:
postfix[j++]=token;  /* 預設: token為運算元時直接放入後序式*/
原 - 2, 錯誤訊息`main' must return `int'
語法:
void main()
改 - 2:
語法:
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 時，代表著可能是有多的無用 ()之類，
在某個優先層級作比較可能要從最內部比較出來吧。
可能的話還需要考慮結合律做為過濾條件。

加油吧！！

getter 2006-11-30 01:33 PM
又想到一種方法，那就是

中置式 轉 後置式(前置式) 在轉回 中置式

如此可以直接去掉不必要的括弧 ...

原中置式運算式 (((a+((b*c)/(d-e))))*(f+g))
轉換成後置式運算式 abc*de-/+fg+*
在轉成原中置式運算式 (a+b*c/(d-e))*(f+g)

至於 程式碼 ... 我沒有，抱歉啦

onlyaway 2006-12-02 07:29 PM
我有照大大的方法改完 你說的新方法 後轉中 我有想過 我跟我這組的同學都是想用這種方法 但是我們班好像沒有人寫出來 都卡在這邊
語法:

#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;
 }


所有時間均為台北時間。現在的時間是 11:48 AM。

Powered by vBulletin® 版本 3.6.8
版權所有 ©2000 - 2025, Jelsoft Enterprises Ltd.

『服務條款』

* 有問題不知道該怎麼解決嗎？請聯絡本站的系統管理員 *


SEO by vBSEO 3.6.1