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

# 先转换为中缀表达式，然后利用定义的矩阵乘法函数来计算这个中缀表达式
# 这样比较麻烦，可以根据这种式子对中缀表达式的计算逻辑进行简化
# 遍历计算方式method ,遇到字母就将矩阵存入栈，遇到右括号：如果矩阵数大于2.就出栈两个矩阵，计算后存入计算后的矩阵，更新计数器；否则终止计算
from re import A
import sys

def cal_count(a,b):
    if a == [0,0]:
        return b,0
    # if a[0] == b[1]:
    #     a,b = b,a
    cnt = a[0]*b[1]*a[1]
    shape = [a[0],b[1]]
    # print("cal:",a,b,cnt)
    return shape,cnt

n = int(input().strip())
mats = []
for i in range(n):
    mats.append(list(map(int,input().strip().split())))
method = input().strip()
prepro_method = []
for c in method:
    prepro_method.append(c)
    if prepro_method[-1].isalpha():
        prepro_method.append('*')
# prepro_method = prepro_method[::-1]
# print(prepro_method)
index = 0
if prepro_method[-1] == '*':
    del prepro_method[-1]
while index < len(prepro_method) - 1:  # 确保不会越界
    if prepro_method[index] == '*' and prepro_method[index + 1] == ')':
        del prepro_method[index]  # 删除当前的 '*'
    elif prepro_method[index] == ')' and (prepro_method[index + 1] != ')'):
        prepro_method.insert(index+1,'*')
        index += 2
    else:
        index += 1  # 只有在没有删除元素时才前进到下一个元素

# prepro_method = prepro_method[::-1]
# print(prepro_method)
stack_mats = []
stack_l = []
cal = []
cnt = 0
i = 0
for c in prepro_method:
    # print(c,stack_mats,stack_l)
    if c.isalpha():
        stack_mats.append(mats[i])
        i += 1
    elif c == ')':
        # c == ')'
        l = stack_l.pop(-1)
        while l != '(':
            # print(l)
            b = stack_mats.pop(-1)
            a = stack_mats.pop(-1)
            new,v = cal_count(a,b)
            cnt += v
            stack_mats.append(new)
            l = stack_l.pop(-1)
    else:
        stack_l.append(c)
# 简化的方法：
#for c in method:
#    if c=='(':
#        continue
#    elif c.isalpha():
#        stack_mats.append(mats[i])
#        i = i+1
#    else:
#        if len(stack_mats) >= 2:
#            b = stack_mats.pop()
#            a = stack_mats.pop()
#            new,cntP = cal_count(a,b)
#            cnt += cntP
#            stack_mats.append(new)
#        else :
#            break
        

print(cnt)