题意：给出矩阵相乘的表达式，让你计算需要的相乘次数，如果不能相乘，则输出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[30][2]; //存储一开始给出的n个矩阵 char str[1010]; //存储表达式列表 struct Matrix{ int row,col; }; //结构体类型的栈 stack <Matrix> s; //处理表达式列表 void solve(){ ans=0; Matrix tmp,t1,t2; int len=strlen(str); for(int i=0;i<len;i++){ if(str[i]>='A' && str[i]<='Z'){ //遇到A~Z直接入栈 tmp.row=matrix[str[i]-'A'][0]; tmp.col=matrix[str[i]-'A'][1]; 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=1; 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,0,sizeof(matrix)); scanf("%d",&n); getchar(); for(int i=1;i<=n;i++){ scanf("%c%d%d",&ch,&r,&c); matrix[ch-'A'][0]=r; matrix[ch-'A'][1]=c; getchar(); } while(scanf("%s",str)!=EOF){ error=0; solve(); if(error){ printf("error "); } else{ printf("%d ",ans); } } return 0; }