如果使用正規表示式來匹配,有點不怎麼好想,而且一般想法設計到遞歸,而在Python中是非常不建議使用遞歸的,
因為它不僅有遞歸深度的限制(一般是1000個棧幀),而且不支援尾遞歸優化。
最簡單的方法就是先將表達式轉換為前綴表達式,然後透過前綴表達式來計算出結果。
前綴表達式(運算子中前面)也被稱為波蘭式,對應的後綴表達式(運算子中後面)也被成為逆波蘭式,而我們生活中,還有
常見的大多數程式語言中使用的都是中綴表達式。
中綴表達式轉換為前綴表達式規則:
(1) 初始化兩個堆疊：運算子堆疊S1和儲存中間結果的堆疊S2;
( 2) 從右到左掃描中綴表達式
(3) 遇到運算元時,將其壓入S2
(4) 遇到運算子時,比較其與S1棧頂運算子的優先權：
(4-1) 如果S1為空,或棧頂運算子為右括號“)”，則直接將此運算子入棧
(4-2) 否則,若優先權比棧頂運算子的較高或相等,也將運算子壓入S1
(4-3) 否則,將S1棧頂的運算子彈出並壓入到S2中,
再次轉到(4-1)與S1中新的棧頂運算子相比較
(5) 遇到括號時：
(5-1) 若是右括號「)」,則直接壓入S1
(5-2) 若是左括號「(」,則依序彈出S1棧頂的運算子,並壓入S2,直到遇到右括號為止,
此時將這一對括號丟棄
(6) 重複步驟(2)至(5),直到表達式的最左邊
(7) 將S1中剩餘的運算子依序彈出並壓入S2
(8) 依序彈出S2中的元素並輸出,結果即為中綴表達式對應的前綴表達式。 #範例:
將轉換到的前綴表達式堆疊進行運算就簡單了(1)初始化一個新列表
(2)從右往左遍歷前綴表達式列表,遇到數字,存到新列表中
(3)遇到運算符,就彈出新列表中的前兩個數字,進行運算,再將結果保存到新列表中
(4)直到新列表中遍歷完前綴表達式列表,此時新列表中就只有一個元素,就是最終的結果
def mid_to_prev(expressions: str):
priority = { # 运算符的优先级
"/": 1,
"//": 1,
"*": 1,
"%": 1,
"+": 0,
"-": 0,
"**": 2 }
expression_list = expressions.split() #
number_stack = [] # 数字栈
symbol_stack = [] # 运算符栈
for x in expression_list[::-1]:
if x.isdigit():
number_stack.insert(0, x) # 如果是整数直接存进去
else:
if x == '(': # 如果是 ( 弹出运算符栈中的运算符直到遇到 (
pop_symbol = symbol_stack[0]
while pop_symbol != ')':
pop_symbol = symbol_stack.pop(0)
number_stack.insert(0, pop_symbol)
pop_symbol = symbol_stack[0]
else:
symbol_stack.pop(0)
elif len(symbol_stack) == 0 or symbol_stack[0] == ')' or x == ')' or priority[x] >= priority[symbol_stack[0]]:
symbol_stack.insert(0, x) # 当符号栈为空 或者 遇到 ) 或者栈顶的符号是 ) 或者优先级大于等于符号栈顶的运算符优先级 直接存进去
elif priority[x] < priority[symbol_stack[0]]: # 优先级小于符号栈顶元素的时候
while symbol_stack[0] != ')' and priority[x] < priority[symbol_stack[0]]:
number_stack.insert(0, symbol_stack.pop(0))
else:
symbol_stack.insert(0, x)
else:
while len(symbol_stack) != 0:
number_stack.insert(0, symbol_stack.pop(0))
return number_stack得到總的結果:
def calc(number1,number2,calc): # 两个数运算
if calc == '/':
return number1 / number2
elif calc == '*':
return number1 * number2
elif calc == '//':
return number1 // number2
elif calc == '**':
return number1 ** number2
elif calc == '%':
return number1 % number2
elif calc == '+':
return number1 + number2
elif calc == '-':
return number1 - number2實例:
前面的前綴表達式結果:
##經驗證結果是正確的。以上是深度解析四則運算的詳細內容。更多資訊請關注PHP中文網其他相關文章！
