矩阵乘法计算量估算

#n接收矩阵个数
n = int(input())
#juzhen接收矩阵行列数据，里面的每一个元素是一个有2个元素的列表，表示每一个矩阵的行列数
juzhen = []
#循环接收输入的每一个矩阵的行列数据
for i in range(n):
    l = list(map(int,input().split()))
    juzhen.append(l)
#s接收计算的法则
s = input()
#res存储计算量的结果
res = 0
#tmp用于模拟栈
tmp = []
#从头开始往后遍历计算法则字符串
#遇到字母就将对应的矩阵入栈
#遇到）就将最后两个入栈的矩阵出栈用于计算
#计算完成后将得到的新矩阵入栈
for i in range(len(s)):
    #如果遇到字母
    if s[i].isalpha():
        #计算是哪个字母
        j = ord(s[i])-65
        #将对应字母所表示的矩阵行列数据放进栈中
        tmp.append(juzhen[j])
    #如果遇到），说明该进行计算了
    elif s[i] == ')':
        #将栈的最后放进去的两个数据，也就是栈尾的两个数据用于计算
        #两个矩阵的计算量存放在res中
        res += tmp[-2][0]*tmp[-2][1]*tmp[-1][1]
        #两个矩阵计算完成后得到一个新的矩阵
        #将新的矩阵替换之前的两个矩阵
        #也就是说，用于计算的两个矩阵数据要出栈
        #新的矩阵要入栈
        tmp[-2] = [tmp[-2][0],tmp[-1][1]]
        tmp.pop(-1)
print(res)

while True:
    try:
        s=int(input())
        a=[]
        for i in range(s):
            a.append(list(map(int, input().split())))
        b=input()
        c=[]
        j=0
        count=0
        for i in b:
            if i.isalpha():
                c.append(a[j])
                j+=1
            elif i==')' and len(c)>=2:
                a2=c.pop()
                a1=c.pop()
                count += a1[0]*a1[1]*a2[1]
                c.append([a1[0],a2[1]])
        print(count)
    except:
        break

import re
letterlist=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']

while 1:
    try:
        a=int(input())
        dimmat=[]
        for each in range(a):
            dimmat.append(list(map(int, input().split())))
        rule=input()


        reg=re.compile('\\(\w{2}\\)')
        prosum=0
        while len(rule)>2:
            curr=reg.findall(rule)
            for item in curr:
                currstr=item
                currL1=item[1]
                ind=letterlist.index(currL1)
                val1=dimmat[ind][0]
                val2=dimmat[ind][1]
                val3=dimmat[ind+1][1]
                prosum=prosum+val1*val2*val3
                newmatdim=[val1,val3]
                dimmat[ind]=newmatdim
                del dimmat[ind+1]
                del letterlist[ind+1]
                rule=rule.replace(currstr,currL1)
        print(prosum)
    except:
        break
        

from functools import reduce

def cal(a,b):
    """
    计算两个行列式，并更新计算数
    并将更新后的行列式更新到记录，供返回后使用
    """
    global count
    global record
    global max_idx
    ar1 = record[a]
    ar2 = record[b]
    count += (ar1[0]*ar1[1]*ar2[1])
    max_idx += 1
    #需要单个字符的标记
    idx = chr(ord("A")+max_idx)
    record[idx] = (ar1[0],ar2[1])
    return idx
    return idx

def cal_count(s):
    #返回行列式的索引
    if "(" not in s:
        idx = reduce(cal, s)
        return idx
    else:
        left = s.index("(")
        right = s.rindex(")")
        tem = cal_count(s[left+1:right])
        return cal_count(s[:left]+tem+s[right+1:])

if __name__ == '__main__':
    while True:
        try:
            count = 0
            n = int(input().strip())
            record = {}
            max_idx = 0
            for i in range(n):
                max_idx += 1
                record[chr(ord('A')+i)] = tuple(map(int, input().strip().split(" ")))
            cal_count(input().strip())
            print(count)
        except:
            break

def get_sum(s, m, r):
    if s[0] == '(' and s[3] == ')':  # 推出条件 (AZ)
        return r + m[0][0] * m[0][1] * m[1][1]  # [[1,2],[2,3]] 1*2*3
    for index, item in enumerate(s):
        if s[index] == '(' and s[index + 3] == ')':  # 题目隐含条件，一对最近的括号中有且仅有两个字母 eg: (A(BC))
            mi = index // 2  # 找到'('对应矩阵的matrix index
            s1 = s[:index] + 'Z' + s[index + 4:]  # (A(BC)) => (AZ)
            m1 = m[:mi] + [[m[mi][0], m[mi + 1][1]]]  # [[1,2],[2,3],[3,4]] => [[1,2],[2,4]]
            r1 = r + m[mi][0] * m[mi][1] * m[mi + 1][1]  # r + 2*3*4
            return get_sum(s1, m1, r1)


while True:
    try:
        n = int(input())
        m = [[int(_) for _ in input().split()] for _ in range(n)]  # 生成记录矩阵 [[1,2],[2,3]]
        s = input()  # 计算法则 (A(BC))
        print(get_sum(s, m, 0))
    except:
        break

import re

while True:
    try:
        n = int(input())
        jz = [[int(i) for i in input().split()] for j in range(n)]
        sx = input()
        m = {}
        stack = []
        new = []
        count = 0

        s = re.findall(r'\w', sx)
        for k, value in enumerate(s):
            m[value] = jz[k]

        for l in sx:
            if l == ')':
                if len(stack) < 3:
                    continue
                new.append(stack.pop())
                new.append(stack.pop())
                stack.pop()
                count += m[new[0]][1] * m[new[1]][0] * m[new[1]][1]
                n = new[1] + new[0]
                rc = [m[new[1]][0], m[new[0]][1]]
                m[n] = rc
                stack.append(n)
                new.clear()
                continue
            stack.append(l)

        print(count)



    except:
        break

# 测试用例右括号会多一个，如(A(B(C(D(E(F(GH))))))))
# python 栈 解法分享
while True:
    try:
        # (A(BC))
        N = int(input())
        lstMat = []
        for _ in range(N): # 输入N个矩阵
            lstMat.append(list(map(int, input().split())))
        law = list(input()) # 计算规则 ['(', 'A', '(', 'B', 'C', ')', ')']
        for i in law:
            if i.isalpha(): # 把law中的ABC字符替换为实际的ABC列表
                law[law.index(i)] = lstMat.pop(0)
        lst = [] # 栈
        cal = [] # 用于计算的临时列表
        times = 0 # 总的计算次数

        for i in law:
            if i == ')': # 遇到右括号时，进行计算
                if not '(' in lst: # 如果栈中无左括号(这一步if主要是因为测试用例中多了一个**右括号，要不就不用加了)
                    continue
                # 此时 lst = ['(', 'A', '(', 'B', 'C']
                # 出栈操作，直到遇见左括号 (
                while True:
                    x = lst.pop() # 出栈
                    if x == '(':
                        break
                    else:
                        cal.insert(0, x) # 给计算列表添加元素，考虑到计算顺序和出栈顺序（计算顺序的逆序），需要insert(0)
#                 print(cal) 中间的几个打印是在调试时找问题用的~
                # 遇到左括号结束循环，此时 lst = ['(', 'A'], cal = [A, B]
                # 计算弹出内容需要计算的次数
                times += cal[0][0] * cal[0][1] * cal[1][1] # 矩阵1的行数 * 矩阵1的列数 * 矩阵2的列数
#                 print(times)
                # 相乘得到新的矩阵
                Matrix = [cal[0][0], cal[1][1]]
#                 print(Matrix)
                # 把新矩阵入栈
                lst.append(Matrix)
                # 清空计算列表
                cal = []
            else:
                lst.append(i) # 入栈
        print(times)
    except:
        break

#看来看去python的答案都一样的，自己写一波
#遇到')'弹栈
def cal_val(A,B):
	if A[1]==B[0]:
		return A[0]*B[1]*A[1]
	else:
		return -1

def cal(A,B):
	if A[1]==B[0]:
		return [A[0],B[1]]
	else:
		return -1

while True:
	try:
		num=int(input())
		array=[]
		for i in range(num):
			matrix=list(map(int,input().split()))
			array.append(matrix)
		array=array[::-1]
		express=str(input().strip())
		stack=[]
		cal_value=0
		for i in range(len(express)):
			if express[i].isalpha():
				stack.append(array.pop())
			elif express[i]==')':
				if len(stack)>1:
					A=stack.pop()
					B=stack.pop()
					print('A,B:',A,B)
					cal_value+=cal_val(B,A)
					stack.append(cal(B,A))
		stack=stack[::-1]
                while len(stack)>1:
			A=stack.pop()
			B=stack.pop()
			cal_value+=cal_val(A,B)
			stack.append(cal(A,B))
		print(cal_value)
	except:
		break

l = list(map(lambda x:chr(x),range(ord('A'),ord('Z')+1)))
while True:
    try:
        N = eval(input())
        ls = []
        for i in range(N):
            ls.append(list(map(eval,input().split())))
        s = input()
        num = 0
        while len(s) != 2:
            lst = []
            index_ls = -1
            index_s = -1
            for k in s:
                if k == '(':
                    index_s += 1
                    lst.clear()
                elif k in l:
                    index_s += 1
                    index_ls += 1
                    lst.append(k)
                elif k == ')':
                    break
            a = ls[index_ls-1][0]
            b = ls[index_ls][1]
            num += ls[index_ls-1][0]*ls[index_ls-1][1]*ls[index_ls][1]
            ls.insert(index_ls-1,[a,b])
            ls.remove(ls[index_ls])
            ls.remove(ls[index_ls])
            s = s[:index_s-2]+lst[-1]+s[index_s+2:]
        print(num)
    except:
        break

while True:
    try:
        n=int(input())
        dic,charA={},65
        for _ in range(n):
            dic[chr(charA)]=list(map(int,input().split()))#将输入的矩阵大小以ABCD...为键存入字典
            charA+=1
        rule=input()
        if rule.count('(')!=rule.count(')'):(738)###有个测试集多了一个右括号
            rule=rule[:-1]
        stack,count=[],0
        for i in rule:
            if i!=')':
                stack.append(i)
            else:(739)#若匹配到右括号
                a=stack.pop()
                b=stack.pop()
                dic['d']=[dic[b][0],dic[a][1]]#将新计算的矩阵形状放入字典中
                stack.pop()(740)#弹出左括号
                if stack:#若栈中没有矩阵，即计算到最后一步，则不添加新的矩阵，否则添加
                    stack.append('d')
                count+=dic[b][0]*dic[b][1]*dic[a][1](741)#两个矩阵(m,n),(n,q)的计算量为m*n*q
        print(count)
    except:
        break

# coding:utf-8

import sys

def parse(s):
    r = []
    a = []
    for i, ch in enumerate(s):
        if ch.isalpha():
            a.append([i, ch])
        if ch == ')':
            while len(a) > 0:
                ch = a.pop()
                r.append(ch)
    return r

try:
    while True:
        line = sys.stdin.readline().strip()
        if line == '':
            break
        n=int(line)
        a=[]
        for i in range(n):
            line = sys.stdin.readline().strip()
            line=line.split()
            line=[int(ch) for ch in line]
            a.append(line)
        line = sys.stdin.readline().strip()
        r=parse(line)
        n=0
        item1=r.pop(0)
        item2=r.pop(0)
        if item1[0]>item2[0]:
            item1,item2=item2,item1
        m1=a[ord(item1[1])-ord('A')]
        m2=a[ord(item2[1])-ord('A')]
        n+=m1[0]*m1[1]*m2[1]
        tmp=[item1[0],[m1[0],m2[1]]]
        while len(r)>0:
            item=r.pop(0)
            if item[0]>tmp[0]:
                m1=tmp[1]
                m2=a[ord(item[1])-ord('A')]
            else:
                m1=a[ord(item[1])-ord('A')]
                m2=tmp[1]
            n+=m1[0]*m1[1]*m2[1]
            tmp=[item1[0],[m1[0],m2[1]]]
        print(n)
except Exception as e:
    print(e)

while True:
    try:
        n=int(input().strip())
        num_list=[]
        for i in range(n):
            num_list.append(list(map(int,input().strip().split(' '))))
        #print(num_list)
        faze=str(input().strip())
        #print(faze)
        def data(faze,num_list):
            result=0
            for i in range(len(faze)):
                if faze[i]=='(' and faze[i+3]==')':
                    result=num_list[i//2][0]*num_list[i//2][1]*num_list[i//2+1][1]
                    num_list=num_list[:i//2]+[[num_list[i//2][0],num_list[i//2+1][1]]]+num_list[i//2+1:]
                    #print(num_list[:i//2])
                    faze=faze[:i]+'v'+faze[i+4:]
                    return result,num_list,faze
        num=0
        for i in range(n-1):
            result,num_list,faze=data(faze,num_list)
            num+=result
        print(num)
    except:
        break

参考大神的思路