题解 | #矩阵乘法计算量估算#
矩阵乘法计算量估算
https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
- 矩阵相乘要求第一个矩阵的列等于第二个矩阵的行，计算次数等于第一个矩阵行*第一个矩阵列(第二个矩阵行)*第二个矩阵列
-
利用简单的栈结构匹配计算，可参考中缀表达式计算。如果遇到左括号则入符号栈；如果右括号则出符号栈并获取两个数值栈进行相乘，将结果添加到最终结果；如果遇到A-Z则通过ord(c)-65计算下标，并将对应下标的矩阵行和列入数值栈
n = int(input())
matrix = []
for _ in range(n):
matrix.append(list(map(int, input().split())))
s = [c for c in input()]
num_stack = []
oper_stack = []
count = 0
def matrix_count(a, b):
return a[0]*a[1]*b[1]
for c in s:
if c == '(':
oper_stack.append(c)
elif c == ')':
oper_stack.pop()
b, a = num_stack.pop(), num_stack.pop()
count += matrix_count(a, b)
num_stack.append([a[0], b[1]])
else:
idx = ord(c)-65
num_stack.append(matrix[idx])
print(count)
