题解 | #矩阵乘法计算量估算#
矩阵乘法计算量估算
https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
import re
import random
def cal(list1, list2):
list3 = [list1[0], list2[1]]
num = list1[0]*list1[1]*list2[1]
return [list3, num]
while True:
try:
n = int(input())
# 逐个获取矩阵并存储为列表
list_in = []
for i in range(n):
list_in.append(list(map(int, input().split(' '))))
# # 接受表达式 存入字典
# text = input()
# index = 0
# dict_ = {}
# for tmp in text:
# if re.match(r'[A-Z]', tmp):
# dict_[tmp] = list_in[index]
# index+=1
# # print(dict_)
# 接受表达式 把字母替换为矩阵
text = list(input())
index = 0
for i in range(len(text)):
if re.match(r'[A-Z]', text[i]):
text[i] = list_in[index]
index+=1
# print(text)
# 找到最右左括号 计算并删除括号 返回计算结果替换原段落 循环 直至列表长度变为1
num = 0
# 计算运算次数
key = 0
# 防死循环
# print(text)
while True and key < n:
# print(key)
done = False
for i in range(len(text)-1,0,-1):
# print(f'i = {i}')
# print(f'text[i] = {text[i]}')
# 找最右的左括号
# 注意这样无法检测到首位
tmp = []
if text[i] == '(':
done = True
# 找到右括号确定范围
for j in range(i+1, len(text)):
# print(f'i = {i} j = {j}')
tmp = text[i:j+1]
# print(f"tmp = {tmp}")
if text[j] == ')':
# 开始计算
if len(tmp) <= 2:
# 非法输入 空括号
# 替换并返回
for k in range(j-i+1):
# 注意pop后索引会变
# 遍历用次数 pop索引应固定
text.pop(i)
elif len(tmp) == 3:
# 括号内只有一个矩阵 直接弹掉括号进行返回
text.pop(j)
text.pop(i)
else:
# 括号内有多个矩阵
tmp_cal = tmp[1]
# 取出首个矩阵
for tmp_m in tmp[2:-1]:
# print(f'tmp_m = {tmp_m}')
[tmp_cal,num_cal] = cal(tmp_cal, tmp_m)
num+=num_cal
# print(f'tmp_cal:{tmp_cal}')
# print(f'num: {num}')
for k in range(j-i):
# 注意pop后索引会变
# 遍历用次数 pop索引应固定
# pop掉段落长度-1 剩一个右括号位置不变 用新矩阵替换
text.pop(i)
# print(text)
text[i] = tmp_cal
# print(text)
# 返回最终矩阵
# print(text)
break
break
if not done:
# 当首位以后的位置找不到右括号
if text[0] == '(' and '(' not in text[1:]:
# 开始计算
# 替换并返回
# 括号内有多个矩阵
tmp = text
tmp_cal = tmp[1]
# 取出首个矩阵
for tmp_m in tmp[2:-1]:
# print(f'tmp_m = {tmp_m}')
[tmp_cal,num_cal] = cal(tmp_cal, tmp_m)
num+=num_cal
# print(f'tmp_cal:{tmp_cal}')
# print(f'num: {num}')
for k in range(len(text)-1):
# 注意pop后索引会变
# 遍历用次数 pop索引应固定
# pop掉段落长度-1 剩一个右括号位置不变 用新矩阵替换
text.pop(0)
# print(text)
text[0] = tmp_cal
# print(text)
# 返回最终矩阵
# print(text)
break
key += 1
print(num)
# # 测试括号功能
# text2 = '(0(12)(34(5(6)))7(8)9)'
# print(text2)
# # 按括号拆成单元 计算最右的左括号所在的対 依次向左
# # 最右括号必为最下级括号（若非最下级则该括号对应有内嵌括号，则不为最右左括号対 矛盾）计算完后取消括号 并迭代 依然成立最右括号必为最下级括号
# indexs = [tmp.start() for tmp in re.finditer(r'\(', text)]
# indexs.reverse()
# # print(indexs)
# indexs_2 = []
# for tmp in indexs:
# tmp2 = 0
# start = tmp
# while True:
# tmp2 = text.find(')', start)
# # print(f"tmp={tmp} tmp2={tmp2}")
# if tmp2 in indexs_2:
# start = tmp2+1
# else:
# indexs_2.append(tmp2)
# break
# # print(indexs)
# # print(indexs_2)
# for i in range(len(indexs)):
# print(text[indexs[i]:indexs_2[i]+1])
# # print(indexs)
# # print(indexs_2)
except:
break
