目錄

• 四則運(yùn)算表達(dá)式求值
• 思路說明
• 算法步驟
• 代碼

四則運(yùn)算表達(dá)式求值

思路說明

使用雙棧來實(shí)現(xiàn)——存放數(shù)值的棧 nums 與存放運(yùn)算符的棧 ops.

算法步驟

• 對(duì)原始表達(dá)式字符串 exp 進(jìn)行預(yù)處理, 將其轉(zhuǎn)為一個(gè)元素對(duì)應(yīng)一個(gè)數(shù)值或運(yùn)算符的列表 explist.
• 遍歷 explist , 每個(gè)元素依次壓入對(duì)應(yīng)的棧中. 每次壓入后, 判斷當(dāng)前兩棧頂是否可進(jìn)行乘除運(yùn)算.棧頂可進(jìn)行乘除運(yùn)算的充要條件是, ops 棧頂為<*> ,</> 之一, 且 nums 中的元素比 ops 中的元素恰好多一個(gè). 如果可以運(yùn)算, 則運(yùn)算, 并將運(yùn)算結(jié)果壓回 nums 中.
• explist 遍歷完之后, 所有乘除運(yùn)算都已進(jìn)行, 此時(shí) ops 中只剩加法與減法, 接下來開始另一個(gè)循環(huán), 一直運(yùn)算即可. 最后 nums 中剩余的唯一元素即為表達(dá)式的值.

代碼

def operation(a, b, op: str):
    """
    計(jì)算一次運(yùn)算的結(jié)果
    :param a: val
    :param b: val
    :param op: 運(yùn)算符
    :return: val
    """
    if op == '+':
        return a+b
    elif op == '-':
        return a-b
    elif op == '*':
        return a*b
    elif op == '/':
        return a/b
    else:
        raise Exception('運(yùn)算符不正確')
def exp_str2list(exp: str):
    """
    將表達(dá)式exp:str轉(zhuǎn)成list,每個(gè)元素對(duì)應(yīng)一個(gè)數(shù)<num>或運(yùn)算符<op>.
    已知exp是標(biāo)準(zhǔn)的四則運(yùn)算表達(dá)式字符串.
    :param exp: str,表達(dá)式
    :return: list
    """
    opset = {'+', '-', '*', '/'}  # 運(yùn)算符集合
    flag = -1
    explist = list()
    for i, char in enumerate(exp):  # 對(duì)表達(dá)式字符串中的每個(gè)字符
        if char in opset:  # 若char是運(yùn)算符
            explist.append(exp[flag+1:i])  # 上一個(gè)運(yùn)算符到當(dāng)前運(yùn)算符中間為數(shù)字,保存到explist
            flag = i  # 更新flag到當(dāng)前op位置
            explist.append(char)  # 當(dāng)前op亦加入explist
    explist.append(exp[flag+1:])
    return explist
def calculate_expression(exp: str):
    """
    表達(dá)式求值. 計(jì)算字符串exp所代表的表達(dá)式的值, 返回一個(gè)數(shù)值
        已知exp是標(biāo)準(zhǔn)的四則運(yùn)算表達(dá)式字符串, 且不含括號(hào).
    :param exp: str, 表達(dá)式
    :return: val
    """
    opset = {'+', '-', '*', '/'}
    nums = list()  # 數(shù)棧
    ops = list()  # 運(yùn)算符棧
    explist = exp_str2list(exp)
    print(explist)
    for e in explist:
        # e入棧
        if e in opset:  # 若e是運(yùn)算符
            ops.append(e)
        else:
            nums.append(eval(e))
        # 若e是優(yōu)先級(jí)高的乘除法, 且
        # nums與ops恰好匹配, 棧頂可以進(jìn)行一次計(jì)算, 運(yùn)算結(jié)果壓入回nums
        if ops and ops[-1] in {'*', '/'} and len(nums) == len(ops) + 1:
            op = ops.pop()
            y = nums.pop()
            x = nums.pop()
            nums.append(operation(x, y, op))
    # 此時(shí)explist中元素已全部遍歷, 同時(shí)乘除法均已被運(yùn)算, 雙棧只剩加減法有待運(yùn)算. 眾所周知, 加減法服從結(jié)合律, 接下來一路算到底即可.
    while ops:
        op = ops.pop()
        y = nums.pop()
        x = nums.pop()
        x_op_y = operation(x, y, op)
        nums.append(x_op_y)
    return nums[0]
if __name__ == '__main__':
    exp = '1*43+542+532*432'
    print(calculate_expression(exp))
    print(eval(exp))

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：[email protected]進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，查實(shí)之后，將立刻刪除涉嫌侵權(quán)內(nèi)容。

猜你喜歡

• Python中類、模塊和包的概念分別是什么，如何理解

  類類的概念在許多語言中出現(xiàn)，是面向?qū)ο缶幊痰幕A(chǔ)，很容易理解。抽象出不同物體的共同特征，根據(jù)相似性原則，把彼此相似的物體歸于相同的

• Python生成器是指什么，如何創(chuàng)建生成器

  我們可以通過列表生成式簡單直接地創(chuàng)建一個(gè)列表，但是受到內(nèi)存限制，列表容量肯定是有限的。而且，創(chuàng)建一個(gè)包含100萬個(gè)元素的列表，不僅占

• Python隨機(jī)森林模型是怎樣的，怎樣實(shí)現(xiàn)

  本篇文章給大家?guī)砹岁P(guān)于Python的相關(guān)知識(shí)，其中主要整理了隨機(jī)森林模型的相關(guān)問題，包括了集成模型簡介、隨機(jī)森林模型基本原理、使用sklearn實(shí)現(xiàn)隨機(jī)森林模型等等內(nèi)容，

• Python實(shí)現(xiàn)解釋器的方法是什么，具體步驟是怎樣

  這篇文章主要介紹了利用?Python?開發(fā)一個(gè)?Python?解釋器,在本文中，我們將設(shè)計(jì)一個(gè)可以執(zhí)行算術(shù)運(yùn)算的解釋器。下面我們大家一起來看看吧

• Python中類的繼承如何理解，有哪些要點(diǎn)

  類的繼承可以看成對(duì)類的屬性和方法的重用,能夠大大的減少代碼量,下面這篇文章主要給大家介紹了關(guān)于Python中類的繼承的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下