史萊姆論壇 - 中序轉後序

史萊姆論壇 (http://forum.slime.com.tw/)

- 程式語言討論區 (http://forum.slime.com.tw/f76.html)

- - 中序轉後序 (http://forum.slime.com.tw/thread266189.html)

請問,
1.為什麼pop(&item)可以用位址傳遞?不是應該用指標嗎?
2.if(item=='(')break
item 沒有內容怎麼會等於'('?
3.為什麼會push(token)?

語法:

  

/*定義堆疊最多可以存放MAX_SIZE個元素*/

#define MAX_SIZE 100



/*宣告stack是堆疊資料結構*/

typedef struct stk{

  char data[MAX_SIZE];/*存放堆疊的元素*/

  int top;            /*記錄堆疊的頂端*/

}stack;



/*宣告一個堆疊S存放運算子和左括號*/

stack S;



/*這個函數會將參數推入堆疊*/

push(char c)

{

    if (S.top < MAX_SIZE - 1) S.data[++S.top] = c;

}



/*這個函數會從堆疊彈出一個元素並存放在參數指定的位址*/ 

pop(char *c)

{

    if (S.top > -1) *c = S.data[S.top--];

}



/*這個函數會檢查參數是否為運算子，是的話，傳回1，否的話，傳回0*/ 

int is_operator(char c)

{

   if ((c == '+')||(c == '-')||(c == '*')||(c == '/')) return 1;

   else return 0; 

}



/*這個函數會檢查參數是否為運算元，是的話，傳回1，否的話，傳回0*/ 

int is_operand(char c)

{

  if (c >= 'a' && c <= 'z') return 1;

  else return 0;

}  



/*這個函數會根據參數指定的運算子傳回其優先順序*/ 

int get_precedence(char c)

{

    switch(c){

      case '(': return 0;

      case '+': return 1;

      case '-': return 1;

      case '*': return 2;

      case '/': return 2;

      default:  return -1;                                

    }          

}



/*這個函數會將中序表示法轉換為後序表示法*/ 

infix_to_postfix(char *infix, char *postfix)

{

    int i = 0, j = 0;

    char token, item;



    while((token = infix[i++]) != '\0')

    {

      if (is_operand(token))

postfix[j++] = token;

      else if (token == '(')

push(token);

      else if (token == ')')

while (S.top > -1){

 pop(&item);

 if (item == '(')    break;

 postfix[j++] = item;

}

      else if (is_operator(token)){

while (S.top > -1){

          if (get_precedence(token) > get_precedence(S.data[S.top])) break;

          else{

   pop(&item);

postfix[j++] = item;

 }

        }

push(token);

      }

    }

    

    while(S.top > -1)

    {

pop(&item);

postfix[j++] = item;

    }

    postfix[j] = '\0';

}



/*主程式*/

main()

{

    char infix[MAX_SIZE] = "a*(b+c)-d";  /*宣告中序表示法為 "a*(b+c)-d"*/ 

    char postfix[MAX_SIZE];              /*宣告用來存放後序表示法的變數*/                   

    infix_to_postfix(infix, postfix);    /*呼叫函數將中序表示法轉換成後序表示法*/ 

    printf("%s轉換為後序表示法會得到%s", infix, postfix);               /*印出後序表示法的結果*/ 

    getchar();

}

迪西沒有記錯的話

-----------------------------------------------------------------

在所有程式語言中，資料傳遞有兩種，一種是『傳值呼叫』、一種是『傳址呼叫』

傳值呼叫
僅僅只有結果(變數的內容傳遞)，當 A Function 被 B Function 呼叫時，由
B Function 以『傳值呼叫』、傳遞結果給 A Function，這樣 A Function 結
束，其輸出是不會改變 B Function 內的變數內容，若 B Function 要接收 A
Function 的運算結果，則需要指定一個變數去接收 A Function 的 return 的
結果。好處是若要維持某一個變數的內容，不要因為被呼叫某 Function 而改變
的化，可以利用『傳值呼叫』。缺點是一次只能回傳一個唯一結果。

傳址呼叫
直接以某個記憶體位址的指派，直接更動某個變數的資料(內容)。這種透過記憶位置
呼叫個變數器而更動傳遞的資料的方式，就是『傳址呼叫』。
當 A Function 被 B Function 呼叫時，由B Function 以『傳址呼叫』、傳遞結果給
A Function，當 A Function 結束，其輸出是直接改寫 B Function 內的某個變數內容。
當如有大量的資料需要在數個 Function 需要被共用、流動時，『傳址呼叫』是最好用的，
但是程式碼要是處理不好，會改變到不想改變的『變數器』內容就是了。

共用資料變數的方式，還有一種就是『全域變數』，在程式執行時，宣告一個
大量的 Array，作為『全域變數』，接下來的任何 Function 的內部變數宣告
名稱，只要不與該 Array 重複，程式在執行上，習慣上會往上一層找尋有沒有
該變數可以用，如此就可以共用資料了。不過需要清楚『全域變數』、『區域
變數』的特性及變數存活週期等等。

指標變數或相關的傳址用法 * 或是 & 符號，以及 Array 的運算操作

以 Array 跟一般變數有一點不一樣，Array 的名子可以當作指標變數
傳遞位址的運算依據

其中 & 符號是指傳遞 &A變數的該A變數的位址，而不是A變數的內容 ...

& 的兩種作用，一個是取得某個變數器的位址；另一種是依據記憶體位址去取出變數器的內容(資料)

可以詳細參考 C/C++ 語言書的傳址呼叫 ...

迪西只記得這些 ... 其他都忘了 ...

感謝你的指導

非常感謝你,你的回答對我很有幫助!

2.if(item=='(')breakㄤ;，item 沒有內容怎麼會等於'('?

並非是沒有內容 ...
而是程式在逐步取得字元符號比對的時候，當 item 變數器的內容是 ( 時，
就執行 break 中斷某個迴圈執行 ...

語法:

if (is_operand(token)) postfix[j++] = token;

   else if (token == '(') push(token);

   else if (token == ')') 

       while (S.top > -1) // if (item == '(') break; 是中斷這一個迴圈

           { 

             pop(&item);

             if (item == '(') break; 

             postfix[j++] = item;

           }

3.為什麼會push(token)?
應該說 push(token) 的使用時機為何？將 ( 放到堆疊裡，或是某的運算符號
放到堆疊裡

語法:

if (is_operand(token)) postfix[j++] = token;

   else if (token == '(') push(token);

   else if (token == ')') 

       while (S.top > -1)

           { 

             pop(&item);

             if (item == '(') break;

             postfix[j++] = item;

           }

...

...

...

else if (is_operator(token)){

...

push(token);

}

再依適當的機會把堆疊裡的東西取出，就達到中置轉後置

建議編寫不管是哪一種程式的原始碼，可以稍稍排版整理一下，如上
這樣子可以增加程式的易讀性，而且哪幾行一組，哪幾行是相關的，
哪幾行是一個 Function。也可以利用註解幫助說明或是排版。