HJ70_矩阵乘法计算量估算_入门栈使用的典型题

反思：

这题咋一看不难，但是越做坑越多，按照一开始不完善的思路无法完全通过测试。

参看高赞答案，代码行数特少。但是没考虑一个括号中有三个矩阵的情况。

思路：

1、判断哪两个矩阵开始相乘的条件：遇到“）”时，该字符前两个矩阵开始相乘。把相乘后矩阵行列数组压入栈栈中。该题默认不存在（A(BCD)）一个括号中有三个矩阵的情况。如果一个括号中有三个及以上矩阵可以参考原来的错误答案。

2、采用order（i)-65的方法获取压入栈的矩阵，这种方法使代码更简洁。

参考高赞答案后通过测试的代码：

 1 #a=[['5'], ['23', '61'], ['61', '59'], ['59', '34'],['34', '56'], ['56', '35'],['(A(((BC)D)E))']]
 2 b=[['47', '45'], ['45', '31'], ['31', '20'],['20', '35'], 
 3    ['35', '59'],['59', '42'],['42', '28']]#这种情况矩阵相乘要放进“（”判断循环中,边判断边处理
 4 #ord（“A")=65
 5 temp=[]
 6 for i in b:
 7     temp.append(list(map(int,i)))
 8 print(temp)
 9 f=['(A((B(C(DE)))(FG)))']
10 arr=[]
11 sum1=0
12 for i in f[0]:
13     if i.isalpha():
14         arr.append(temp[ord(i)-65])#获得压入栈中矩阵。
15     #print(arr)
16     elif i==")" and len(arr)>=2:
17         matrix1=arr.pop()
18         matrix2=arr.pop()
19         a,b,c=matrix2[0],matrix1[1],matrix2[1]
20         arr.append([a,b])#把两矩阵相乘得到的新矩阵的行列压入栈中。
21         sum1=a*b*c+sum1
22 print(sum1)
23     

只通过18个测试案例的代码

 1 a=[['5'], ['23', '61'], ['61', '59'], ['59', '34'],['34', '56'], ['56', '35'],['(A(((BC)D)E))']]
 2 n=[]*len(a)
 3 for line in a[:-1]:
 4     n.append(list(map(int,line)))
 5 a=n+a[-1]
 6 n.pop(0)
 7 t1,t2,t=[],[],[]  
 8 for k,i in enumerate(a[-1]):
 9     if i=="(":
10         t1.append(k)
11     elif i==")":
12         t2.append(k)
13     else:
14         t.append(k)
15 print(t1,t2,t)
16 d=dict(zip(t,n))
17 #print(d)
18 def nu(t1:int,t2:int,t)->int:
19     num=0
20     tt,now=[],[]
21     for j in t:
22         if j in range(t1,t2):
23             num+=1
24             now.append(j)
25         else:
26             tt.append(j)
27     return tt,now
28 def su(now,fresult):
29     l=[]
30     sum1=0
31     for i in now:
32         l.append(d[i])
33     if fresult:    
34         if list(fresult.keys())[0]<now[0]:
35             print(l)
36             l.insert(0,list(fresult.values())[0])
37             print(l)
38         else:
39             l.append(list(fresult.values())[0])
40     repeat=len(l)-1
41     for i in range(repeat):
42         c,b=l[-1][0],l[-1][1]
43         a=l[-2][0]
44         print(a,b,c,sum1)
45         sum1=sum1+a*b*c
46         l.pop()
47         l.pop()
48         l.append([a,b])
49         fresult={now[0]:[a,b]}
50         print(a,b,c,fresult)
51     return sum1,fresult
52 sum2=0
53 fresult={}
54 while t:
55     t,now=nu(t1.pop(),t2.pop(0),t)    
56     
57     sum1,fresult=su(now,fresult)
58     sum2=sum2+sum1
59     print(now,fresult,t) 
60 print(sum2)