当前位置 博文首页 > 可惜浅灰的博客：stack应用：UVA442 矩阵连乘
题目描述：
? ??假设你必须评估一种表达形如 ABCDE，其中 A,B,C,D,E是矩阵。既然矩阵乘法是关联的，那么乘法的顺序是任意的。然而，链乘的元素数量必须由你选择的赋值顺序决定。
? 例如，A，B，C分别是 50 * 10 ，10 * 20 和 20 * 5 的矩阵。现在有两种方案计算 A * B * C ,即（A * B) * C 和 A*(B * C)。第一个要进行15000次基本乘法，而第二个只进行3500次。你的任务就是写出一个程序判定以给定的方式相乘需要多少次基本乘法计算。
输入：输入包含两个部分：矩阵和表达式。 输入文件的第一行包含了一个整数 n(1?\leq≤?n?\leq≤?26), 代表矩阵的个数。接下来的n行每一行都包含了一个大写字母，说明矩阵的名称，以及两个整数，说明行与列的个数。
输出：? 对于每一个表达式，如果乘法无法进行就输出 " error "。否则就输出一行包含计算所需的乘法次数。
解题思路：
? ? 1、矩阵有不止一个属性，有矩阵名、长度、宽度，需要单独建一个类；
? ? 2、用到多个矩阵，这些矩阵的矩阵名都是不同的，要把矩阵名转化成下标，矩阵建一个数组，?方便查找矩阵的属性。
? ? 3、对输入的处理上，有'(‘之后不一定立马需要有乘法运算，但出现')'，每出现一次都要执行一遍乘法操作，后来先处理，适合用栈。逐个遍历输入字符串，遇到矩阵名就使其入栈，遇到'('不用管，遇到’)'对栈顶的连个矩阵做一次乘法操作，之后把乘好之后的矩阵入栈。重复操作即可。
? ? 4、矩阵可乘辨别：前宽度 = 后长度
代码实现：
#include <iostream>
using namespace std;
#define max_n 9
#include <stack>
class Matrix
{
public:
int len;
int wid;
Matrix(int x= 0, int y = 0) :len(x), wid(y) {}
};
Matrix mat_arr[max_n];
void InitArr(const int& n)
{
char c;
int a, l, w;
for (int i = 0; i < n; i++)
{
cin >> c;
a = c - 'A';
cin >> l >> w;
Matrix mat(l, w);
mat_arr[a] = mat;
}
}
void Solve(const string& s)
{
stack<Matrix> sta;
int len = s.length();
int sum = 0;
for (int i = 0; i < len; i++)
{
if (s[i] == '(')
{
continue;
}
else if (s[i] == ')')
{
Matrix mat_b = sta.top();
sta.pop();
Matrix mat_a = sta.top();
sta.pop();
if (mat_a.wid == mat_b.len)
{
sum += mat_a.len * mat_a.wid * mat_b.wid;
sta.push(Matrix(mat_a.len, mat_b.wid));
}
else
{
cout << "error" << endl;
return;
}
}
else
{
int a = s[i] - 'A';
sta.push(mat_arr[a]);
}
}
cout << sum << endl;
}
int main()
{
int n = 0;
cin >> n;
InitArr(n);
string input;
while (1)
{
cin >> input;
Solve(input);
}
return 0;
}