Matrix Chain Multiplication

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1567    Accepted Submission(s): 1022

Problem Description
Matrix multiplication problem is a typical example of dynamical programming.

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 (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
 

Source
University of Ulm Local Contest 1996 




思路：
这道题是一个典型的可以用堆栈数据结构来解决的问题（一般有左右括号优先级的都会用到栈或者优先队列）。这道题的题意就是说，给了你ABCDEF等大写字母，每个大写字母代表一个矩阵，有着行和列的属性，然后还会出现左右括号来调节它们运算的优先级。让你求的就是确定括号优先级之后要进行的矩阵乘法的次数。就比如，4×3矩阵和3×2矩阵相乘，那么运算次数就是4×3×2，如果是4×3矩阵、3×2矩阵、2×1矩阵相乘，那么运算次数就是4×第一个3×第一个2×1。也就是说，运算次数就是a[0]×a[1]×a[3]×...×a[i+2]。思路就是对入栈的元素进行判断，如果入栈元素不是')'则顺利入栈，如果是')'或者入栈的是最后一个元素了，那么就往前找，将‘)’之前的元素一直出栈进行运算次数是多少，直到遇到了'('终止这次运算。然后再把这次出栈运算完之后得到的矩阵再次入栈。依次循环。这道题的思路还算简单，但是在细节处理上比较麻烦：比如数据的入栈出栈时候的处理啊，处理的不光要得到矩阵乘法次数还要得到一个新的矩阵，还有对进行运算的矩阵进行分类讨论看它是不是单矩阵、能不能运算、有多少矩阵参与运算，这都是需要考虑的细节。

代码： 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;

int row[10000];
int col[10000];
char name;
char str[10000];

int count(int *a, int n)  
{  
    int flag = 0;  
    if(n == 2)  //只有一个矩阵
        return 0;  
    for(int i = 1 ; i < n-1; i += 2)  
    {  
        if(a[i] != a[i+1])  
        {  
            flag = 1;  
            break;  
        }  
    }  
    if(flag == 1)  //两个矩阵横纵都不等 
        return -1;  
    int mul = a[0];  
    for(int i = 1; i < n; i += 2 )  //正常 
    {  
        mul *= a[i];  
    }  
    return mul;  
}  



int main()
{
	 freopen("1082in.txt","r",stdin); 
	 int t;
	 cin>>t;
	 for(int i=0;i<t;i++)
	 {
	 	cin>>name;
	 	cin>>row[name-'A']>>col[name-'A'];
	 }
	 getchar();
	 while(gets(str))
	 {
	 	int n = strlen(str);  
        if(n == 1)  
        {  
            cout << "0" << endl;  
            continue;  
        }  
	 	stack<char>matix;
	 	int sum=0;
		int flag=0; 
		for(int i = 0; i < n; i++)  
        {  
            if(str[i] != ')' )  
            {  
                if(isalpha(str[i]))  
                {  
                    matix.push((char)row[str[i] - 'A']);  
                    matix.push((char)col[str[i] - 'A']);     
                }  
                if(str[i] == '(')  
                    matix.push('(');  
            }  
            if(str[i] == ')' || i == n-1)  
            {  
                int cnt = 0;  
                int b[10000];  
                while(!matix.empty())  
                {  
                    if(matix.top() == '(')  
                    {  
                        matix.pop();  
                        break;  
                    }  
                    b[cnt++] = (int)matix.top();  
                    matix.pop();  
                }  
                reverse(b, b+ cnt);  
                if(!matix.empty())  
                {  
                    matix.push(b[0]);  
                    matix.push(b[cnt-1]);  
                }  
                int mul  = 1;  
                mul = count(b, cnt);  
                if(mul == -1)  //不能进行矩阵运算，退出 
                {  
                    flag = 1;  
                    break;  
                }  
                else  //将运算的次数进行求和 
                    sum += mul;  
            }  
            if(flag == 1)  
                break;  
        }  
	 	if(flag == 1)  
            cout << "error" << endl ;  
        else  
            cout << sum << endl;  
	
	 	
	 }
	
	return 0;

}