網際網路程式設計全國大賽

決賽題目

Postfix 是一種運算式的表示法，在這一種表示法中，運算子放在其運算元之後，例如， A/B 的 postfix 表示法即為 AB/。而 A/B*C 的 postfix 表示法即為 AB/C*，其計算方式為先計算 AB/，再計算 ((AB/)C*)。底下是幾個範例：

一般	postfix	計算次序
A/B*C	AB/C*	((AB/)C*)
A*B+C-D/E-G	AB*C+DE/-G-	((((AB*)C+)(DE/)-)G-)

請設計一個程式，將一個一般的運算式轉換成以 postfix 表示的運算式。運算子將只有 +、-、*、/ 四種，運算元為 A 到 Z 的大寫英文字母，其優先次序請遵循一般四則運算的優先次序。

輸入檔說明

輸入檔第一列有一個數字 n，表示後面有 n 列，每列有一個一般的運算式，不同的運算子與運算元之間以一個以上的空白分開，你必須將該運算式轉換成以postfix 表示的運算式。運算符號和運算子總數不超過 30 個。

輸出檔說明

總共輸出 n 列結果，依輸入順序印出 postfix 表示的運算式。運算元和運算子間要有一個以上的空白。

範例

2
A * B + C - D / E - G
A

A B * C + D E / - G -
A