题目大意:
给出一个矩阵乘法的表达式，计算需要多少次乘法运算。
思路:学过线性代数就很容易得出乘法次数就是A(row)*B(row)*B(col)，也就是A的行数乘以A的行数和列数，思路本质上和表达式求值的题目是一样的，用一个栈保存矩阵信息，遇到右括号时从栈中弹出两矩阵参与运算。并将计算结果入栈。
具体实现:
(PS:这里的矩阵只存储了它的行数和列数，由于想不不到合适的名字，只好用它代替)
#include<iostream> #include<map> #include<cstring> #include<stack> using namespace std; struct Matrix{int row; int col;}; stack<Matrix> s; map<char,Matrix> Matrix_info; char Matrixexp[10000]; //ma mb分别表示两个矩阵 sum是计算次数 bool multiCount(const Matrix& Ma,const Matrix& Mb,int& count){ //如果不能计算 if(Ma.col!=Mb.row){ return false; }else{ count+=Ma.row*Mb.col*Mb.row; Matrix newMatrix={Ma.row,Mb.col}; //将运算后的矩阵放入栈中 s.push(newMatrix); return true; } } void solution() { int count=0; bool isLegal=true; for(int i=0;i<strlen(Matrixexp);i++){ if(Matrixexp[i]>='A'&&Matrixexp[i]<='Z'){ s.push(Matrix_info[Matrixexp[i]]); }else if(Matrixexp[i]==')'&&s.size()>=2){ Matrix ma,mb; mb=s.top(); s.pop(); ma=s.top(); s.pop(); isLegal=multiCount(ma,mb,count); if(!isLegal) break; } } if(isLegal) cout<<count<<endl; else cout<<"error"<<endl; } void input(){ int n; cin>>n; while(n--){ char Matrix_name; Matrix Matrix_size; cin>>Matrix_name>>Matrix_size.row>>Matrix_size.col; Matrix_info[Matrix_name]=Matrix_size; } } int main() { input(); cin.get(); while(gets(Matrixexp)){ solution(); } return 0; }