Transforming Infix to Postfix/Prefix Ste by Step

以 MS Visual Studio C++ 逐步實作 infix => postfix/prefix 轉換

徐熊健、李宏恩

2014/11/21, 2017/10/29

1. Using String ^ for input/output directly 輸入字串、直接輸出。

2. Specifying each char/token of the input string by index (to the string) 利用 MessageBox 檢視輸入字串中的各個字元。

我們設定 operand/operator 皆為一個字元，用

String ^ infix = textBox1->Text;

即可用 infix->Length 取得其長度，且 infix[i] 為講義/課本所謂的 token[i], 0<=i<=n-1.

3. Identifying the current token (operator or operand) 區分所檢查的字元是否為運算子（是：置入堆疊；否：併入輸出字串。）

4. Declare the necessary stack (an array of String ^) 宣告必要的 stack （型態是 String ^ 的陣列）

String ^ 在 VS 中是特別的物件，請用

static array<String ^> ^ Stack = gcnew array<String ^>(100); 宣告之！ (這 static 是 C++ 的用字，可定義 global variables 詳見: http://ot-note.logdown.com/posts/178610/global-and-static-variables)

注意：static top = -1; (可 initialize 之~~ (y) )

5. Following the infix==>postfix algorithm 依上課提示：將（1）運算子按照運算優先順序置入堆疊，且該自堆疊中彈出字元以併入後序字串時，不得怠慢；（2）運算元併入後序字串；

俟所有字元處理完成後，再自堆疊中依序取出字元、併入後序字串；爾後印出後序字串。

判斷 字串 s 是否為 operand:

bool IsOperand(String ^ s)

{ if ((s!="+") && (s!="-") && (s!="*") && (s!="/")

&& (s!="(") && (s!=")") && (s!="&") && (s!="|")

&& (s!="^") && (s!="#"))

return true;

return false;

}

6. Simplifying the codes 將「俟所有字元區分完成後，再自堆疊中依序取出字元、併入輸出字串」這個步驟用更簡潔的方式寫出。

7. Testing longer infix 測試較長的中序式。

8. Dealing with "(" and ")" 加入（、）的判定與處理。

9. richTextBox1->Text += ... 留下之前輸出的結果。

10. More test cases 多測些中序式。

11. Infix==>postfix/prefix 不僅做中序轉後序，同時做中序轉前序。