The Postfix Converter

The Postfix Converter

Let W be an infix expression which is composed of the characters in the set {『a』、『b』、『c』、『d』、『e』、『#』、『@』、『(』、『)』} where the length of W is not greater than 30 characters. The alphabets 『a』、『b』、『c』、『d』、and 『e』 are the operands in W. The symbols 『#』 and 『@』 are binary operators in W where the priority of # is less than that of 『@』、i.e.、「a # b @ c」 is equivalent to 「a # (b @ c)」 and 「a @ b # c」 is equivalent to 「(a @ b) # c」. The operator 『#』 is with left associativity、i.e.、「a # b # c」 is equivalent to 「(a # b) # c」、while the operator 『@』 is with right associativity、i.e.、「a @ b @ c」 is equivalent to 「a @ (b @ c)」. Please write a program to convert W into a postfix expression.

Input Format:
An infix expression W I {『a』、『b』、『c』、『d』、『e』、『#』、『@』、『(』、『)』}⁺ with 1 ￡ W ￡ 30.

Output Format:
The postfix form of W.

Sample Input:
1. a # b @ c @ d # e
2. a @ (b # c) @ d
3. a # b @ ((c # d) @ (e # a))

Sample Output:
1. abcd@@#e#
2. abc#d@@
3. abcd#ea#@@#

困難度：**
時間複雜度：O(n)
程式語言：C++
預估時間：5 小時

解題原理：
1. 以字串讀入內容，一次處理一行
2. 先去除空白
3. 將每個字元以字串容器的觀點進行處理
4. 設定每種不同字元的優先權
5. 每次從字串容器集合取出優先權最高的字元
6. 如果是最高優先權的括號則進行分進合擊遞迴演算法，先處理括號內的字元，進入步驟7，否則進入步驟8
7. 如果欲處理的內容仍包含括號，進入步驟3處理括號內的字元，否則進入步驟8
8. 此時處理的字元為1個運算子和2個運算元，進行後序轉換，若a@b，則ab@
9. 重複步驟3-8，直到沒有運算子即完成

程式下載

原碼下載

參考來源：中山大學 九十三學年度電腦程式設計競賽 試題 Problem C