Problem Description yizhen has no girlfriend due to his stupid brain that he even can’t solve a simple arithmetic roblem. Can you help him If you solve it and tell him the result, then he can find his lovers! So beautiful! Input The input

一、題目描述

請用 python3編寫一個計算器的控制臺程序，支持加減乘除、乘方、括號、小數點，運算符優先級為括號>乘方>乘除>加減，同級別運算按照從左向右的順序計算。

二、輸入描述

數字包括"0123456789"，小數點為"."，運算符包括：加("+")、減("-")、乘("*")、除("/")、乘方("^"，注：不是**！)、括號("()")

需要從命令行參數讀入輸入，例如提交文件為 main.py，可以用 python3?main.py "1+2-3+4" 的方式進行調用

輸入需要支持空格，即?python3?main.py "1 ? ? + ? ? 2 ? ? ?- ? ? 3 ? ?+ ? ?4" 也需要程序能夠正確給出結果

所有測試用例中參與運算的非零運算數的絕對值范圍保證在 10^9-10^(-10) 之內, 應該輸出運算結果時非零運算結果絕對值也保證在該范圍內

三、輸出描述

數字需要支持小數點，輸出結果取10位有效數字，有效數字位數不足時不能補0

對于不在輸入描述內的輸入，輸出INPUT ERROR

對于格式不合法(例如括號不匹配等)的輸入，輸出 FORMAT ERROR

對于不符合運算符接收的參數范圍(例如除0等)的輸入，輸出VALUE ERROR

對于2、3、4的情況，輸出即可，不能拋出異常

同時滿足2、3、4中多個條件時，以序號小的為準

四、樣例

輸入: 1 + 2 - 3 + 4

輸出: 4

輸入: 1 + 2 - 3 + 1 / 3

輸出: 0.3333333333

輸入: 1 + + 2

輸出: FORMAT ERROR

輸入: 1 / 0

輸出: VALUE ERROR

輸入: a + 1

輸出: INPUT ERROR

【注：此題為TsinghuaX:34100325X 《軟件工程》 MOOC 課程 Spring, 2016 Chapter 1 Problem，此文發布時，這門課剛剛在 “學堂在線” 上開課兩天】

代碼是先看了 http://blog.csdn.net/whos2002110/article/details/19119449 這個網址的。然后 自己記憶寫了一份。 本來目的是要學一些 解釋器的。雖然也看到一些實現，但是感覺對我有點難度，于是從簡單開始學習。 import java.util.ArrayList;import java.

用 Python3 實現，初看一下，首先想到的其實是一種“討巧”(作弊 >_

大致代碼區區幾行：

1 from sys import argv

2

3 if __name__ == "__main__":

4 exp = argv[1]

5 print(eval(exp))

即便是考慮到題干中的輸出要求做異常處理(try...except)輸出相應的錯誤信息，也就十行左右。

但稍深入就會發現，有些情形還是無法按要求處理的，比如樣例 “1 + + 2”，用 eval() 會輸出結果 “3” (+2 前的 “+” 被當作正號)，而題目要求輸出 “FORMAT ERROR”。

沒辦法，只能老老實實做苦力活兒了。

表達式求值其實是《數據結構》課程里一個基本且重要的問題之一，一般作為 “棧” 的應用來提出。

問題的關鍵就是需要按照人們通常理解的運算符的優先級來進行計算，而在計算過程中的臨時結果則用 棧 來存儲。

為此，我們可以首先構造一個 “表” 來存儲當不同的運算符 “相遇” 時，它們誰更 “屌” 一些(優先級更高一些)。這樣就可以告訴計算機，面對不同的情形，它接下來應該如何來處理。

其次，我們需要構造兩個棧，一個運算符棧，一個運算數棧。

運算符棧是為了搞定當某個運算符優先級較低時，暫時先讓它呆在棧的底部位置，待它可以 “重見天日” 的那一天(優先級相對較高時)，再把它拿出來使用。正確計算完成后，此棧應為空。

運算數棧則是為了按合理的計算順序存儲運算中間結果。正確計算完成后，此棧應只剩下一個數，即為最后的結果。

完整的代碼如下：

1 # -*- coding: utf-8 -*-

2

3 #################################

4 # @Author: Maples7

5 # @LaunchTime: 2016/2/24 12:32:38

6 # @FileName: main

7 # @Email: maples7@163.com

8 # @Function:

9 #

10 # A Python Calculator for Operator +-*/()^

11 #

12 #################################

13

14 from sys import argv

15 from decimal import *

16

17 def delBlank(str):

18 """

19 Delete all blanks in the str

20 """

21 ans = ""

22 for e in str:

23 if e != " ":

24 ans += e

25 return ans

26

27 def precede(a, b):

28 """

29 Compare the prior of operator a and b

30 """

31 # the prior of operator

32 prior = (

33 # '+' '-' '*' '/' '(' ')' '^' '#'

34 ('>', '>', '', ''), # '+'

35 ('>', '>', '', ''), # '-'

36 ('>', '>', '>', '>', '', ''), # '*'

37 ('>', '>', '>', '>', '', ''), # '/'

38 ('

39 ('>', '>', '>', '>', ' ', '>', '>', '>'), # ')'

40 ('>', '>', '>', '>', '', '>', '>'), # '^'

41 ('

42 )

43

44 # operator to index of prior[8][8]

45 char2num = {

46 '+': 0,

47 '-': 1,

48 '*': 2,

49 '/': 3,

50 '(': 4,

51 ')': 5,

52 '^': 6,

53 '#': 7

54 }

55

56 return prior[char2num[a]][char2num[b]]

57

58 def operate(a, b, operator):

59 """

60 Operate [a operator b]

61 """

62 if operator == '+':

63 ans = a + b

64 elif operator == '-':

65 ans = a - b

66 elif operator == '*':

67 ans = a * b

68 elif operator == '/':

69 if b == 0:

70 ans = "VALUE ERROR"

71 else:

72 ans = a / b

73 elif operator == '^':

74 if a == 0 and b == 0:

75 ans = "VALUE ERROR"

76 else:

77 ans = a ** b

78

79 return ans

80

81 def calc(exp):

82 """

83 Calculate the ans of exp

84 """

85 exp += '#'

86 operSet = "+-*/^()#"

87 stackOfOperator, stackOfNum = ['#'], []

88 pos, ans, index, length = 0, 0, 0, len(exp)

89 while index < length:

90 e = exp[index]

91 if e in operSet:

92 # calc according to the prior

93 topOperator = stackOfOperator.pop()

94 compare = precede(topOperator, e)

95 if compare == '>':

96 try:

97 b = stackOfNum.pop()

98 a = stackOfNum.pop()

99 except:

100 return "FORMAT ERROR"

101 ans = operate(a, b, topOperator)

102 if ans == "VALUE ERROR":

103 return ans

104 else:

105 stackOfNum.append(ans)

106 elif compare == '

107 stackOfOperator.append(topOperator)

108 stackOfOperator.append(e)

109 index += 1

110 elif compare == '=':

111 index += 1

112 elif compare == ' ':

113 return "FORMAT ERROR"

114 else:

115 # get the next num

116 pos = index

117 while not exp[index] in operSet:

118 index += 1

119 temp = exp[pos:index]

120

121 # delete all 0 of float in the end

122 last = index - 1

123 if '.' in temp:

124 while exp[last] == '0':

125 last -= 1

126 temp = exp[pos:last + 1]

127

128 try:

129 temp = Decimal(temp)

130 except:

131 return "INPUT ERROR"

132 stackOfNum.append(temp)

133

134 if len(stackOfNum) == 1 and stackOfOperator == []:

135 return stackOfNum.pop()

136 else:

137 return "INPUT ERROR"

138

139 if __name__ == "__main__":

140 # get the exp

141 exp = argv[1]

142

143 # set the precision

144 getcontext().prec = 10

145

146 # delete blanks

147 exp = delBlank(exp)

148

149 # calc and print the ans

150 ans = calc(exp)

151 print(ans)

其中需要稍微注意的細節有：

1. 表達式處理前，前后都插入一個 '#' 作為一個特殊的運算符，這樣做是為了方便統一處理，即不用再去特別判斷表達式是否已經結束(從而引發一系列邊界問題導致代碼冗長復雜，這種處理也可稱之為 “哨兵” 技巧)。如果最后兩個運算符相遇則說明表達式處理完畢，這個運算符的優先級也是最低的(在 prior 表中也有體現)。

2. 輸出要求比較復雜，拋去錯誤信息輸出不說(只能具體情況具體分析)，不能輸出多余的0，折騰了一會兒最后發現用高精度的?Decimal 可以完美滿足題目要求。

3. 由于不能輸出多余的0，所以在帶有小數部分的數字 “錄入” 時(代碼115-132行)，就要把一些多余的0提前去掉(代碼121-126行)，比如 2.0 這樣的情況。