深度解析四則運算

怎麼將字串的算數表達式計算出來？

如果使用正規表示式來匹配,有點不怎麼好想,而且一般想法設計到遞歸,而在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] != &#39;)&#39; 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中文網其他相關文章！