疑問 - 中序轉後序

[bobo0836]

請問,
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();
}

[getter]

迪西沒有記錯的話

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

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

傳值呼叫
僅僅只有結果(變數的內容傳遞)，當 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++ 語言書的傳址呼叫 ...

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

[bobo0836]

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

[getter]

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。 也可以利用註解幫助說明或是排版。