The Prefix Evaluator

The Prefix Evaluator

Let P be a prefix expression which is composed of the characters in the set {『1』、『3』、『5』、『7』、『9』、『$』、『%』} where each of the operands in P is a digit and the length of P is not greater than 30 characters. The symbols 『$』 and 『%』 are binary operators in P and defined as follows: x $ y = (x + y)/2 and x % y = (x - y)/2 where x、y I {1、3、5、7、9}. Please write a program to evaluate P.

Input Format:
A prefix expression P I {『1』、『3』、『5』、『7』、『9』、『$』、『%』}⁺ where 1 ￡ P ￡ 30.

Output Format:
The value of P. Note that the data type of the output must be 「float」.

Sample Input:
1. $39
2. %57
3. $$39%57
4. %%%1357

Sample Output:
1. 6.000000
2. -1.000000
3. 3.500000
4.-5.000000

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

解題原理：
1. 以字串讀入內容，一次處理一行
2. 將每個字元以浮點數的觀點進行處理
3. 如果字元是運算子則設為很大的數
4. 從右往左看，找到第一個運算子後進行運算，若%39，則3%9
5. 重複步驟4，直到沒有運算子即完成

程式下載

原碼下載

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