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

#思路：按照括号从内到外计算，计算时把两个矩阵的行列数去重之后累乘就可以了
#关键在于怎么从内到外，可以以栈的思路来解决这个问题

def f(a,b):#由两个列表计算乘法次数
    return a[0]*a[1]*b[1]


dic={}#字典存储矩阵名称和大小
n=int(input())#矩阵个数
res=0#累加和
for i in range(n):
    dic[chr(ord("A")+i)]=[int(i) for i in input().split()]
# print(dic)
s=input()
stack=[]#存列表，矩阵的行列数
for i in s:
    if i.isalpha():#是字母就存对应的矩阵大小
        stack.append(dic[i])
    elif i==")":
        res+=f(stack[-2],stack[-1])#累加乘法次数
        stack.append([stack[-2][0],stack[-1][1]])#添加计算之后的矩阵大小
        stack.pop(-2)#删除用过的矩阵1
        stack.pop(-2)#还有一个记得删
print(res)