top-down 與 bottom-up 的設計方式

108

一般而言，程式的設計有 top-down 方式及 bottom-up 的方式。 top-down 的方式是先將程式的大綱擬定好，再一步一步的將 程式細節填上。而 bottom-up 的方式則是 將程式需要的工具 先設計好，再將 程式湊齊， 如同造房子， 先將所要建的各部份造好了， 再併裝成一棟房子。

我們以下例來做說明。

例 1： 試設計一程式來檢驗 input 檔 的 第一行 是否 含有 標準格式的括號式，一個標準的括號式 其定義如下：

()為一標準的括號式 (empty string 也算是)。
如果 E1 及 E2 皆為標準括號式則 (E1) 及 E1E2 皆為標準括號式。
括號之間不可夾其它字元 連空白亦不可以。
第一行的第一個字元也必須是左括號。
方法 1： 對於這問題，我們可以利用一變數 count 來計算目前所讀到左 括號個數 減去 右括號的個數， 在讀至一行的結束或一個空白 之前 count 不能為負，又讀完了 input 之後， count 必須為 0。 因此，程式大約為 step 1: count=0  
step 2: 如果 not end of line,
c=getchar();
不然跳至 step4  
step 3: 如果 c 為左括號，則 count++;
如果 c 為右括號，則 count--， 又如果 count 為負，則列印錯誤訊息; return;
如果 c 為其它符號，則列印錯誤訊息; return;
跳至 step2  
step4: 如果 count=0，則列印正確訊息;  

再將上述 類程式碼 (pseudo code) 轉變成下列程式碼：

      
       main()
       {  int count=0;
          char c;
          while( (c=getchar())!='\n')
          {  if ( c=='(' )  count++;
             else if( c == ')')
             {    count--;
                  if (count < 0)
                  { printf("error input!\n");
                    return;
                  }
             }
             else { printf("error input!\n"); return;}
          }
          if (count == 0) printf("correct format\n");
          else printf("error input!\n");
       }

方法 2： 我們以 堆疊 的資料結構 來處理該問題， 一個 堆疊 的資料結構 基本上有 isEmpty， isFull， push 及 pop 的功能， 一個 堆疊 可以將之想像成 一堆盤子， 一個 push 的動作就是將 一個盤子 放到 堆疊 最上面，一個 pop 的動作 即從那堆盤子拿走 最上面的 一個盤子。
以類似 bottom-up 的方式 先將一個 stack 及其 operations 先設計好，此 stack 不是要 存放盤子 而是要 存放字元。

於檔案 stack.h 中存放函數的宣告如下：

       int isStackEmpty();
       int isStackFull();
       void push(char c);
       char pop();
       void initalizeStack();

檔案 stack.c 為 stack 的資料結構，其內容如下：
       #define MAXSIZE 100
       static char s[MAXSIZE];
       static int tos;
      
       void initalizeStack(){ tos=0;}

       int isStackEmpty(){ return tos==0;}
   
       int isStackFull(){ return tos==MAXSIZE;}

       void push(char c){ s[tos++]=c;}
        
       char pop(){ return s[--tos];}

如此一來，利用 stack 來處理上述問題， 就可以 用下列 的方式 來解決：
step1： 如果目前是 end of line， goto step4  
step2： c=getchar();  
step3： 如果 c 為左括號， 則 push('(');， goto step1
如果 c 為右括號，又堆疊不為空，則 pop();， goto step1， 不然 input 不為正確格式
如果 c 是其它符號，則 input 不為正確符號
goto step1  
step4： 如果堆疊是空的，則 input 為正確格式  


所以主程式 main.c 的內容如下：

    #include <stdio.h>
    #include "stack.h"
    main()
    { char c;
      while( (c=getchar()) != '\n')
      { if ( c == ')') push(c);
        else if ( c == ')')
             { if (isStackEmpty())
               { printf("Error input!\n"); return;}
               else  pop();
             }
        else
        {  printf("Error input!\n"); return;}
      }
      if(isStackEmpty()) printf("Correct input!\n");
      else printf("Error input!\n");
    }

註：

於檔案 stack.c 中全域變數 s 與 tos 定義為 static 變數， 如此一來變數 s 與 tos 僅能在 檔案 stack.c 中被引用， 而其它檔案，如 main.c 中，則無法引用變 s 及 tos。 如此 一來 堆疊的資料結構 才能保持一致性，不致於被濫用 以致於 程式難懂且難維修。
我們僅能以 stack.h 中所提供的 函數 來使用 stack 資料結構。
如果 stack.c 中的資料結構改變如 例 2，對於引用 stack 的函數並沒有改變，即 stack.h， main.c 都無需改變， 即整個設計分成兩種層次，修改 下一層 的架構，並不影響 上一層 的設計。 這也是 C++ class 設計的基本精神之一，即 data encapsulated 資料的封包 或 資料的抽象化。
例 2： 以 linked-list 的 資料結構 來建立 stack， 則檔案 stack.c 可改為
      #include <stdio.h>
      #include <stdlib.h>

      struct node{ char c; struct node *pn;};

      static struct node *s;

      void initializeStack() {s = NULL;}

      int isStackEmpty() {return s == NULL;}

      void push(char c)
      {    struct node *p;

           p=(struct node *) malloc (sizeof(struct node));
           if (p == NULL)
           { printf("No avilable space for malloc\n"); exit(1);}
           else
           { p->c  = c;
             p->pn = s;
             s = p;
           }
       }

       char pop()
       {   char c;
           struct node *p;

           if( isStackEmpty())
           { printf("Try to pop an empty stack.\n"); exit(2);}
           else
           { c = s->c; p = s; s = s->pn; free(p); return c;}
       }   

註： 以 free() 指令將 記憶體空間 釋放出來， 以供下次使用。 free(void *) 的 參數 為一 記憶體 指標。