作者：Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处
矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如：
A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵
计算A*B*C有两种顺序：（（AB）C）或者（A（BC）），前者需要计算15000次乘法，后者只需要3500次。
编写程序计算不同的计算顺序需要进行的乘法次数。
本题含有多组样例输入！
输入描述：输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则
计算的法则为一个字符串，仅由左右括号和大写字母（'A'~'Z'）组成，保证括号是匹配的且输入合法！
输出需要进行的乘法次数
示例：输入：
350 1010 2020 5(A(BC))输出：
3500 解题思路：本题我用二维数组做的，采用了指针方式，用vector也很方便。Estimate函数用来计算两个矩阵的计算量，并返回相乘后的矩阵；calc函数用来将vector中后面的两个矩阵拿出来计算，再将新生成的矩阵塞进去，以此实现矩阵的连续操作；solve函数是主要求解函数，遍历字符串，将出现的矩阵字母以此塞进vector中，每出现一次')'，就进行一个calc计算，这样实现了括号的优先级，若最后遍历完字符串，vector尺寸大于1，类似A(BC)=AD这样的，那就继续执行calc。完毕。
其实题目描述的不是特别严谨，假设括号并不是最小囊括两个，比如((ABC)D)，按照我所写的算法逻辑，就会先算BC=E，再算ED=F，再算AF，但实际上应该是ABC=G，再算GD。总的来说，根据不同的题目要求，代码应该有所变通和完善，当前的测试样例不涵盖此类情况，如果未来有不通的案例，可以评论私我~
测试代码： #include <iostream>#include <string>#include <vector>using namespace std;int* Estimate(int *t1,int *t2,int &sum){ int t1_row=t1[0]; int t1_col=t1[1]; int t2_row=t2[0]; int t2_col=t2[1]; sum=t1_row*t1_col*t2_col; int *t3=new int[2]; t3[0]=t1_row; t3[1]=t2_col; return t3;}int calc(vector<int*> &m){ int *t1; int *t2; int *t3; int sum=0; t2=m.back(); m.pop_back(); t1=m.back(); m.pop_back(); t3=Estimate(t1,t2,sum); m.push_back(t3); return sum;}int solve(int *a[2],string str){ vector<int*> m; int sum=0; int k=0; for(int i=0;i<str.size();++i) { // 若有')'，则对前面的两个矩阵进行了一次计算量估算 if(str[i]==')') { sum+=calc(m); } else if(str[i]>='A'&&str[i]<='Z') { m.push_back(a[k]); k++; } // 如果是'('，跳过 } while(m.size()>1) { sum+=calc(m); } return sum;}int main(){ int number; while(cin>>number) { int**mat=new int*[number]; for(int i=0;i<number;++i) { mat[i]=new int[2]; cin>>mat[i][0]; cin>>mat[i][1]; } string str; cin>>str; cout<<solve(mat,str)<<endl; delete[] mat; } return 0;}