题目内容
矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如：
A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵
计算ABC有两种顺序：（（AB）C）或者（A（BC）），前者需要计算15000次乘法，后者只需要3500次。
编写程序计算不同的计算顺序需要进行的乘法次数
输入描述:
输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则
输出描述:
输出需要进行的乘法次数
示例1
输入
3
50 10
10 20
20 5
(A(BC))
输出
3500
思路
显然用栈做。但是细节要把控好。
考虑这样的数据，代码也应该能handle：
4
50 10
10 20
20 5
5 6
(A(BCD))
输出
9000
思路：
每个字母肯定不会重复，每个字母对应到一个(r,c)元组上，弄成结构体比较方便。
将字母括号串从左到右扫描，遇到')'则弹栈，一直弹到遇到'('，那么弹出的这些字母（对应到一个个矩阵，也对应到一个包含(r,c)维度信息的结构体），它们的列数c相乘，再乘以最后弹出元素（也即紧邻'('右边的字母）的行数r。
注意，这里还没有结束，遇到了'('应该把弹出这些元素计算结果进行保存，并且，更新一下维护的字母括号序列的元素，我的做法是把原有的“(XXXXZ)”这个东西用Z来替代，因为Z的列数c后续还是会被使用。
放码过来
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <climits>
#include <stack>
using namespace std;
void EX21_clean() {
int n;
struct Dim { int r, c; };
while (cin >> n) {
vector<Dim> vd;
Dim dim;
for (int i = 0; i < n; i++) {
cin >> dim.r >> dim.c;
vd.push_back(dim);
}
string s; cin >> s;
stack<Dim> stk;
int ans = 0;
stack<char> cal;
int delta;
int idx;
char ch1, ch2;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ')') {
if (cal.size() != 1) {
ch1 = cal.top(); cal.pop();
if (ch1 == '(') {
continue;
}
idx = ch1 - 'A';
dim = vd[idx];
delta = dim.c;
while (!cal.empty()) {
ch2 = cal.top(); cal.pop();
idx = ch2 - 'A';
if (ch2 == '(') {
cal.push(ch1); //注意此处
break;
}
dim = vd[idx];
delta *= dim.c;
}
delta *= dim.r;
ans += delta;
}
}
else {
cal.push(s[i]);
}
}
cout << ans << endl;
}
}
int main() {
//EX1();
//EX2();
//EX3();
//EX4();
//EX5();
//EX6();
//EX7();
//EX11();
//EX12();
//EX13();
//EX14();
//EX15();
//EX16();
//EX17();
EX21_clean();
return 0;
}