442 Matrix Chain Multiplication
Suppose you have to evaluate an expression like A*B*C*D*E where A,B,C,D and E are matrices.
Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary.
However, the number of elementary multiplications needed strongly depends on the evaluation order
you choose.
For example, let A be a 50*10 matrix, B a 10*20 matrix and C a 20*5 matrix. There are two
different strategies to compute A*B*C, namely (A*B)*C and A*(B*C).
The first one takes 15000 elementary multiplications, but the second one only 3500.
Your job is to write a program that determines the number of elementary multiplications needed
for a given evaluation strategy.
Input
Input consists of two parts: a list of matrices and a list of expressions.
The first line of the input file contains one integer n (1 ≤ n ≤ 26), representing the number of
matrices in the first part. The next n lines each contain one capital letter, specifying the name of the
matrix, and two integers, specifying the number of rows and columns of the matrix.
The second part of the input file strictly adheres to the following syntax (given in EBNF):
SecondPart = Line { Line } <EOF>
Line = Expression <CR>
Expression = Matrix | "(" Expression Expression ")"
Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"
Output
For each expression found in the second part of the input file, print one line containing the word ‘error’
if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one
line containing the number of elementary multiplications needed to evaluate the expression in the way
specified by the parentheses.
Sample Input
9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
Universidad de Valladolid OJ: 442 – Matrix Chain Multiplication 2/2
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))
Sample Output
0
0
0
error
10000
error
3500
15000
40500
47500
15125
栈模拟
我们先用一个结构体储存每个矩阵的长和宽。然后我们开始对读入的每一个字符串进行扫描，当我们遇到（的时候直接忽略，遇到）的时候讲栈顶的两个元素弹出进行计算，每次计算的时候我们需要判断这两个矩阵是否满足相乘的条件，矩阵相乘的条件为第一个矩阵的宽等于第二个矩阵的长，然后ans根据题目中要求的进行累加。当既不是（也不是）的时候我们将这个矩阵入栈。
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 30
using namespace std;
int read()
{
,f=; char ch=getchar();
;ch=getchar();}
+ch-',ch=getchar();
return x*f;
}
bool flag;
char ch;
string ss;
struct Node
{
int x,y;
Node(,):x(x),y(y){}
}node[N];
stack<Node>s;
int main()
{
int n=read(),a,ans;
;i<=n;i++)
{
scanf("%c",&ch);
a=ch-;
node[a].x=read(),node[a].y=read();
}
while(cin>>ss)
{
int l=ss.length();
flag=;
;i<l;i++)
{
if(ss[i]==')')
{
Node m2=s.top(); s.pop();
Node m1=s.top(); s.pop();
if(m1.y!=m2.x) {flag=true;break;}
else
{
ans+=m1.x*m1.y*m2.y;
s.push(Node(m1.x,m2.y));
}
}
else
if(ss[i]!='(')
{
a=ss[i]-;
s.push(Node(node[a].x,node[a].y));
}
}
if(flag) printf("error\n");
else printf("%d\n",ans);
}
;
}