ZOJ 1094_Matrix Chain Multiplication

本文主要是介绍ZOJ 1094_Matrix Chain Multiplication，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大意：输入一系列矩阵（不超过26个），判断下面输入的矩阵乘法是否合法（即是否满足前者的列等于后者的行），若合法则输出其做了多次数的乘法运算（若有两矩阵A：a,b; B: b,c ,则其做的数乘法次数为a*b*c），若不合法，则输出error。

 

分析：为了操作方便定义一个矩阵结构，保存矩阵名，row和column. 从题意可知，每次的乘法都用括号隔开，那么这里就符合LIFO。前括号可以忽略，后括号作为每次乘法运算的标识。遇到矩阵即压栈。

 

#include<iostream>
#include<stack>
#include<string>
using namespace std;
struct Matrix//定义矩阵元素 
{
char name;
int row;
int column;
};
int main()
{
stack<Matrix> sk;
int i,n,j,result;
Matrix M[26],a,b,temp;
string s;//保存每一组输入 
bool flag;//error标识 
while(cin>>n)
{
for(i=0;i<n;i++)
cin>>M[i].name>>M[i].row>>M[i].column;
while(cin>>s)
{
result=0;
i=0;
flag=true;
while(s[i]!='\0')
{
if(s[i]!='(')//过滤'(' 
{
if(s[i]>='A'&&s[i]<='Z')//遇到字母即在已知的矩阵数组中匹配 
{
for(j=0;j<n;j++)
{
if(M[j].name==s[i])
{
sk.push(M[j]);//压栈 
break;
}
}
}
else
{
if(s[i]==')')//')'为乘法标识 
{
b=sk.top();
sk.pop();
a=sk.top();
sk.pop();
if(a.column==b.row)//符合矩阵乘法法则 
{
temp.name='M';
temp.row=a.row;
temp.column=b.column;
sk.push(temp);//将结果压栈 
result+=a.row*a.column*b.column;//累计乘法次数 
}
else//不符合即error并标识不输出result 
{
cout<<"error"<<endl;
flag=false;
break;
}
}
}
}
i++;
}
while(!sk.empty())//清空栈 
sk.pop();
if(flag)
cout<<result<<endl;
}
}
return 0;
}

 

这篇关于ZOJ 1094_Matrix Chain Multiplication的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---