题解 | #矩阵乘法计算量估算#
矩阵乘法计算量估算
http://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
//C++实现55行代码
#include<iostream>
#include<string>
#include<vector> //vector用于存放矩阵向量
#include<stack> //stack用于字符串的存取处理
using namespace std;
int main()
{
int num=0;
string str;
while(cin>>num)
{
vector<int> v;
int temp=0;
for(int i=0;i<num*2;++i)
{
cin>>temp;
v.push_back(temp);
}
cin>>str; //以上步骤用于获取输入，变量有num、v、str
int res=0; //存放最终的计算总数
int len=str.length();
stack<char> s2; //栈s2存放第一次遍历的字符
stack<char> s3; //栈s3存放要处理的字符
for(int i=0;i<len;++i) //遍历字符串
{
if(str[i]==')') //如果遇到右括号')'就开始处理，否则压入s2
{
char temp;
while(s2.top()!='(')
{
temp=s2.top();
s3.push(temp);
s2.pop();
} //将括号内的字符提取至s3
s2.pop(); //s2内的左括号'('出栈
int sum=0; //记录一对括号内的计算次数
char c=s3.top(); //一个括号组内不止两个矩阵，要记录第一个矩阵的字母
s2.push(c); //很重要，代表这个括号内矩阵的索引
int first=c-'A'; //一个括号组内不止两个矩阵，要记录第一个矩阵的大小位置
s3.pop(); //第一个矩阵出栈
while(s3.size()) //括号内其他矩阵与第一个矩阵运算
{
int num1=s3.top()-'A'; //记录第二个矩阵的位置信息
s3.pop(); //已经计算过的矩阵出栈
sum=sum+v[first*2]*v[num1*2]*v[num1*2+1]; //当前矩阵计算次数之和
v[first*2+1]=v[num1*2+1]; //更新第一个矩阵的大小信息
}
res+=sum; //计算总数
}else s2.push(str[i]);
}
cout<<res<<endl;
}
return 0;
}
