题解 | #矩阵乘法计算量估算# 可实现括号内多个

if formula[i]=='(':
    bracket_pos.append(len(stack))

elif formula[i]==')':
    # the pos of last '('
    front = bracket_pos.pop()

# lst = [[d1,d2],[d2,d3],...]
def simple_dim_times(lst1):  #[tail--head]--cal order
    time = 0
    while len(lst1)>1:
        a=lst1.pop()
        b=lst1.pop()
        # to keep the order: matrix a * b
        print('a,b,str1',a,b,lst1)
        dimension = [a[0], b[1]]
        #print(dimension)
        time += a[0] * a[1] * b[1]
        #print('time', time)
        lst1 = lst1 + [dimension]
        #print(lst1)
    return lst1,time


n = int(input())
D = [list(map(int,input().split())) for _ in range(n)]
f = input()
# A-->D[0],B-->D[1]
# formula with dimension
formula = []
for i in f:
    if i.isalpha():
        k=(ord(i)-65)
        formula.append(D[k])
    else:
        formula.append(i)
#print('formula',formula)

stack = []
bracket_pos = []
times = 0
for i in range(len(formula)):
    if formula[i]=='(':
        # record the pos in stack of the first alpha(in this bracket)
        bracket_pos.append(len(stack))
        #print('bracket_pos',bracket_pos)
    elif formula[i]==')':
        # the pos of last '('
        front = bracket_pos.pop()
        temp = []
        while len(stack)>front:
            # stop when length=front
            temp.append(stack.pop())
        # the order is the cal order:[tail--head]
        #print('temp',temp)

        temp,cnt1 = simple_dim_times(temp)
        stack += temp
        times += cnt1
        #print('now stack', stack)
        #print('now times', times)
    else:
        stack.append(formula[i])
        #print('+',stack)
#print('out')
while len(stack)>1:  # still need simple cal
    stack = stack[::-1]  # turn into cal order
    temp,cnt2 = simple_dim_times(stack)
    stack += temp
    times += cnt2
print(times)