【每日一題】公式計算

給定一個字元串str，str 表示一個公式，公式裡可能有整數，加減乘除，傳回公式的計算結果。

【舉例】

str = “3-6*9+43*70*8-6” , 傳回 24023

str = “3+1*4” , 傳回 7

分析：

由于乘除的計算優先級高于加減，是以：第一遍周遊優先計算乘除，第二遍周遊再計算加減。

def expression_compute(string):
    stack = []
    i = 0
    while i < len(string):
        item = string[i]
        # 遇到數字
        if '0' <= item <= '9':
            num, j = get_num(string, i)
            stack.append(num)
            i = j
        # 遇到乘除：立即計算
        elif item == "*" or item == "/":
            num, j = get_num(string, i + 1)
            stack.append(compute(stack.pop(), item, num))
            i = j
        # 遇到加減：暫時緩存
        elif item == "+" or item == "-":
            stack.append(item)
            i += 1
    
    # 計算加減
    i = 0
    res = stack[0]
    # 注意從前向後計算
    while i < len(stack) - 1:
        operator = stack[i + 1]
        num2 = stack[i + 2]
        res = compute(res, operator, num2)
        i += 2
    return res


# 從 string 的 index 位置開始擷取數字
# 傳回：num, i。計算結果，後續要處理的位置
def get_num(string, index):
    num = 0
    for i in range(index, len(string)):
        item = string[i]
        if item < '0' or item > '9': break

        num = num * 10 + int(item)

    return num, i + 1 if i == len(string) - 1 else i

# 運算
def compute(num1, operator, num2):
    if operator == "+": return num1 + num2
    if operator == "-": return num1 - num2
    if operator == "*": return num1 * num2
    if operator == "/": return int(num1 / num2)
  
  
print(expression_compute("14-95+62/50"))
           

給定一個字元串str，str 表示一個公式，公式裡可能有整數，加減乘除和左右括号，傳回公式的計算結果。

【舉例】

str = “48*((70-65)-43)+8*1” , 傳回 -1816

str = “3+1*4” , 傳回 7

str = “3+(1*4)” , 傳回 7

【說明】

1. 可以認為給定的字元串一定是正确的公式，即不需要對 str 做公式有效性檢查。
2. 如果是負數，就需要用括号括起來，比如”4*(-3)“ 。但如果負數作為公式的開頭或者括号部分的開頭，則可以沒有括号，比如：”-3*4“ 和 ”(-3*4)“ 都是合法的。
3. 不用考慮計算過程中發生的溢出的情況

運算規則：

• 優先計算括号内公式
• 再計算乘算
• 再計算加法

在計算括号内公式時：遇到 ”(“ 時，遞歸調用，再遇到 “)” 在進行計算，每次調用 que 中隻存儲目前括号内的公式。

def expression_compute(string):
    return process(string, 0)[0]

def get_num(string, index):
    num = 0
    for i in range(index, len(string)):
        item = string[i]
        if item < '0' or item > '9': break

        num = num * 10 + int(item)

    return num, i + 1 if i == len(string) - 1 else i

# 計算 string 公式
# 優先括号内的公式，再計算乘除，再計算加減
def process(string, index):
    que = []
    i = index
    while i < len(string):
        # (：遞歸調用
        if string[i] == "(":
            num, j = process(string, i + 1)
            i = j
            que.append(num)
        # 遇到數字
        elif "0" <= string[i] <= "9":
            num, j = get_num(string, i)
            que.append(num)
            i = j
        # ) 計算括号内的公式
        elif string[i] == ")":
            res = sub_expression_compute(que)
            return res, i + 1
        else:
            que.append(string[i])
            i += 1

    # 計算沒有括号，剩下的公式
    return sub_expression_compute(que), i

# 計算 array 内的公式
# 優先計算乘除，再計算加減
def sub_expression_compute(array):
    stack = []
    i = 0
    # 計算乘除
    while i < len(array):
        if array[i] == "*" or array[i] == "/":
            stack.append(compute(stack.pop(), array[i], array[i + 1]))
            i += 2
        else:
            stack.append(array[i])
            i += 1

    # 計算加減
    i = 0
    res = stack[0]
    while i < len(stack) - 1:
        operator = stack[i + 1]
        num2 = stack[i + 2]
        res = compute(res, operator, num2)
        i += 2
    return res

# 運算
def compute(num1, operator, num2):
    if operator == "+": return num1 + num2
    if operator == "-": return num1 - num2
    if operator == "*": return num1 * num2
    if operator == "/": return int(num1 / num2)
  
print(expression_compute("48*((70-65)-43)+8*1"))
print(expression_compute("3+1*4"))
print(expression_compute("3+(1*4)"))