• 欢迎光临~

# HJ70 矩阵乘法计算量估算

## 题目描述

A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵

```输入：
4
24 3
3 46
46 39
39 36
(A(B(CD)))

72144```

## 解题思路：

```#include <iostream>
#include <stack>
#include <vector>
#include <string>
using namespace std;

struct Matrix {
int x, y;
};

int main() {
int n;
string reg;
while (cin >> n) {
Matrix matrix[16];
for (int i = 0; i < n; i++) {
cin >> matrix[i].x >> matrix[i].y;
}
cin >> reg;
int len = reg.length();
int num = 0, index = 0;
stack<Matrix> stValue;
stack<char> stOper;

for (int i = 0; i < len; i++) {
if (reg[i] == '(') {
stOper.push('(');
}
else if (reg[i] == ')') {
stOper.pop();
stOper.pop();
if (stValue.size() >= 2 && stOper.top() == 'A') {
stOper.push('A');
Matrix tmp1 = stValue.top();
stValue.pop();
stOper.pop();
Matrix tmp2 = stValue.top();
stValue.pop();
stOper.pop();
num += tmp1.x*tmp1.y*tmp2.x;
tmp2.y = tmp1.y;
stValue.push(tmp2);
//stOper.push('A');
}
stOper.push('A');
}
else {
if (!stValue.empty() && stOper.top() == 'A') {
Matrix tmp = stValue.top();
stValue.pop();
num += tmp.x*tmp.y*matrix[index].y;
tmp.y = matrix[index].y;
stValue.push(tmp);
index++;
stOper.pop();
}
else {
stValue.push(matrix[index++]);
}
stOper.push('A');
}
}
cout << num << endl;
}
return 0;
}```