题解 | 矩阵乘法计算量估算

注意进出栈的顺序

from collections import deque

n = int(input())

def get_num(c):
    return ord(c) - ord("A")

def m_mul(ah, aw, bh, bw):
    tmp = ah * aw * bw
    return ah, bw, tmp

metrixs = []
for _ in range(n):
    metrixs.append(list(map(int, input().split())))
calc_queue = input()
calc_stack = deque()
total_result = 0
for c in calc_queue:
    if c == "(":
        calc_stack.append(c)
    elif c == ")":
        curr_list = []
        while next_c := calc_stack.pop():
            if next_c == "(":
                break
            else:
                curr_list.append(next_c)
        curr_h, curr_w = curr_list.pop()
        while len(curr_list) > 0:
            _h, _w = curr_list.pop()
            curr_h, curr_w, tmp = m_mul(curr_h, curr_w, _h, _w)
            total_result += tmp
        calc_stack.append([curr_h, curr_w])
    else:
        curr_h, curr_w = metrixs[get_num(c)]
        if len(calc_stack) > 0:
            last_c = calc_stack.pop()
            if last_c != "(":
                _h, _w = last_c
                curr_h, curr_w, tmp = m_mul(_h, _w, curr_h, curr_w)
                total_result += tmp
                calc_stack.append([curr_h, curr_w])
            else:
                calc_stack.append(last_c)
                calc_stack.append([curr_h, curr_w])
        else:
            calc_stack.append([curr_h, curr_w])
print(total_result)