题意：给出矩阵相乘的表达式，让你计算需要的相乘次数，如果不能相乘，则输出error。
思路：
参考的网站连接：http://blog.csdn.net/wangjian8006/article/details/8905295
刚开始想到用栈的，但不知道怎么下手。后来网上查了一下，其实可以用结构体定义一个矩阵的类型，建立关于该结构体的栈，这样操作起来就方便多了。
遇到'('，无视继续；遇到字母，压入栈顶；遇到')'，将栈顶前两个矩阵压出，并加上其相乘次数，再将所得的矩阵压入栈顶；
这里解释这么做的原因：
注意看题目给出的表达式列表的形式，每两个矩阵相乘，左右必有一个括号：
如(AB)，(A(BC))(这里B、C有一对括号，BC相乘后得到一个矩阵，该矩阵和A左右又有一对括号)，(A((BC)D))
这样，有多少对括号(或者有几个 '(' / ')' )就要计算两个矩阵相乘多少次。因此，我们可以利用栈，一次一次往里面压入矩阵，每当遇到一个')'，就计算一次相乘。
用(A((BC)D))举例：
1.'('，无视继续；
2.A,压入栈顶，此时栈里元素：A(按进入栈的顺序，下面一样)；
3、4.'('，同样无视；
5.B，压入栈顶，此时栈里元素：AB；
6.C，压入栈顶，此时栈里元素：ABC；
7.')'，将栈顶的两个元素压出栈，判断，若可以相乘，则计算BC的相乘次数并加上，将BC乘后的矩阵B'压入栈顶。 此时栈里元素：AB'；
8.D，压入栈顶，此时栈里元素：AB'D;
9.')'，将栈顶的两个元素B'D出栈，判断，若可以相乘，则计算B'D的相乘次数并加上，将B'D乘后的矩阵B''压入栈顶。 此时栈里元素：AB''
10.')'，将栈顶的两个元素AB''出栈，判断，若可以相乘，则计算AB''的相乘次数并加上，将AB''乘后的矩阵A'压入栈顶。 此时栈里元素：A'
但由于之后不会再有')'，所以矩阵相乘也就结束。最后的和即为结果。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack> using namespace std;
int n,ans;
int error; //错误标记
int matrix[][]; //存储一开始给出的n个矩阵
char str[]; //存储表达式列表 struct Matrix{
int row,col;
};
//结构体类型的栈
stack <Matrix> s;
//处理表达式列表
void solve(){
ans=;
Matrix tmp,t1,t2;
int len=strlen(str);
for(int i=;i<len;i++){
if(str[i]>='A' && str[i]<='Z'){ //遇到A~Z直接入栈
tmp.row=matrix[str[i]-'A'][];
tmp.col=matrix[str[i]-'A'][];
s.push(tmp);
}
else if(str[i]==')'){ //遇到')'，计算相乘次数
t2=s.top();
s.pop();
t1=s.top();
s.pop();
//t1*t2
if(t1.col!=t2.row){ //如不能计算，标记error，返回
error=;
return;
}
else{
ans+=t1.row*t1.col*t2.col;
t1.col=t2.col;
s.push(t1); //将相乘后的矩阵压入栈顶
}
}
}
}
int main()
{
char ch;
int r,c;
memset(matrix,,sizeof(matrix));
scanf("%d",&n);
getchar();
for(int i=;i<=n;i++){
scanf("%c%d%d",&ch,&r,&c);
matrix[ch-'A'][]=r;
matrix[ch-'A'][]=c;
getchar();
}
while(scanf("%s",str)!=EOF){
error=;
solve();
if(error){
printf("error\n");
}
else{
printf("%d\n",ans);
}
}
return ;
}