UVA 442 - Matrix Chain Multiplication

http://blog.csdn.net/crazy__chen/article/details/38418199
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 Specification

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 (  ), 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 Specification

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

题目描述：输入n个矩阵的维度和一个矩阵链乘的表达式，输出乘法的次数，如果乘法无法进行，则输出error。

根据题意，矩阵我定义为一个有rol,row两个属性的对象，我们手动输入一系列的矩阵

然后输入矩阵链乘表达式，其中表达式内可能有括号，所以括号内的要想相乘，否则应该从左向右乘（矩阵相乘是不符合交换律的）

使用栈来解决，第一个站用于存储矩阵，一个栈用于存储左括号的位置

顺序扫描矩阵链乘表达式，遇到矩阵（也就是非括号，程序里面我直接用矩阵在数组中的下标表示），将其装入矩阵栈。遇到左括号，将遇到左括号的位置，装入括号栈。遇到右括号，我们从括号栈里面记录的最后一个左括号的位置开始，将矩阵连乘，一直到右括号为止。

乘的过程中，如果出现不能相乘，结束程序；如果连乘结束，将结果矩阵装入矩阵栈（注意将矩阵栈中，刚才连乘的矩阵全部清空）

上述过程后，矩阵栈中，是一系列可以直接顺序链乘的矩阵，连乘之，同样，如果出现不能相乘，结束程序；否则等到最后的矩阵结果

public class Matrix {
 int col = 0;
 int row = 0;
 public Matrix(int col,int row) {
  this.col = col;//列
  this.row = row;//行
 }  
}

public class Test {    
    //矩阵相乘，返回新矩阵
    public static Matrix multiply(Matrix a , Matrix b )  {  
        return new Matrix( a.col,b.row);         
    }  
    
    public static boolean can_mul(Matrix a , Matrix b )  {  
        if( a.row == b.col ) return true ;  
        return false ;  
    }  
    
    public static void main(String[] args) {
        int total = 4;//矩阵数目
        Matrix[] matrixs = new Matrix[total];
        matrixs[0] = new Matrix(3,3);
        matrixs[1] = new Matrix(3,4);
        matrixs[2] = new Matrix(4,5);
        matrixs[3] = new Matrix(5,6);
        
        String[] str= {"0","(","1","2",")","3"};//乘法表达式
        Matrix[] stack = new Matrix[str.length];//矩阵栈
        int[] left = new int[str.length];//括号栈,用于存放左括号的位置
        
        int stackLen = 0;//用于记录矩阵栈的末端
        int mL = 0;//mL+1=矩阵进入栈的数目
        //一个m×n的矩阵a(m,n)左乘一个n×p的矩阵b(n,p)，会得到一个m×p的矩阵c(m,p)
        for(int i=0,j=0,k=0;i<str.length;i++){
            if(str[i] == "("){//如果是左括号，进入括号栈
                left[j] = stackLen;//记录栈中左括号应在矩阵栈的位置                
                j++;
            }else if(str[i] == ")"){//如果是右括号                            
                Matrix tmp = stack[left[j-1]];//遇到右括号前,最后一次记录左括号右边的第一个矩阵
                for(int m=left[j-1]+1;m<stackLen;m++){//将左右括号内的矩阵相乘
                    if(can_mul(tmp, stack[m])){//如果能相乘
                        tmp = multiply(tmp, stack[m]);
                    }else{//如果不能相乘,结束程序
                        System.out.println("error");
                        System.exit(-1);
                    }
                }
                stack[left[j-1]] = tmp;//将新矩阵放入栈
                
                stackLen = left[j-1]+1;//将矩阵栈从新矩阵开始继续计数                
                for(int n=stackLen;n<stack.length;n++){//将后面的矩阵清空
                    stack[n] = null;
                }
                j--;//将括号栈内，最后一个左括号去掉
                
            }else{//如果是矩阵，进入矩阵栈
                stack[stackLen] = matrixs[mL];
                System.out.println(stack[stackLen].row);
                stackLen++;            
                mL++;
            }
        }

        Matrix tmp = stack[0];        
        for(int i = 1;i<stackLen;i++){//顺序计算矩阵相乘
            if(can_mul(tmp, stack[i])){
                tmp = multiply(tmp, stack[i]);
            }else{
                System.out.println("error");
                System.exit(-1);
            }
        }
        
        System.out.println("结果为row="+tmp.row+",col="+tmp.col+"的矩阵");
    }
}

比如(((((DE)F)G)H)I)，遇到 (就cnt累计加一，字母入栈，遇到)减一，并出栈两个矩阵计算运算量，将计算后的矩阵压入栈。当cnt等于0时就输出运算量。

http://shangxun.iteye.com/blog/1937814

1. int sum,n;  
2. int mat[30][2];  
3. int arr[30],prev[30], next[30];  
4. char str[1000];  
5.   
6. void solve(){  
7.     // 如过只有一个矩阵，那么直接输出结果0  
8.     if(strlen(str)==1 && isupper(str[0])){  
9.         printf("0\n");  
10.     }  
11.     else{  
12.         char copyMat[30][2];  
13.         int i,j;  
14.         // 复制一个数组进行操作。 因为后面的操作需要对这些矩阵进行修改  
15.         for(i=0; i<n; ++i){  
16.             copyMat[i][0] = mat[i][0];  
17.             copyMat[i][1] = mat[i][1];  
18.         }  
19.         sum=0;  
20.         stack<char>st;   
21.           
22.         for(i=0; i<strlen(str); ++i){  
23.             if(str[i]=='(' || isupper(str[i]))  
24.                 st.push(str[i]);  
25.             else if(str[i]==')'){  
26.                 stack<char>temp;        
27.         // 当碰到‘）’时，把栈中的矩阵全都取出来进行计算     
28.                 while(isupper(st.top())){  
29.                     temp.push(st.top());              
30.                     st.pop();  
31.                 }  
32.                 // 把'('也弹出  
33.                 st.pop();  
34.                 char ex;  
35.                 // 取出第一个矩阵（在原表达式中是最左边的一个）  
36.                 if(!temp.empty()){  
37.                     ex=temp.top();  
38.                     temp.pop();  
39.                 }  
40.                 while(!temp.empty()){  
41.                     char multi = temp.top();  
42.                     temp.pop();  
43.                     // 如果左边矩阵的列数和右边矩阵的函数不同，则直接输出 error  
44.                     if(copyMat[ex-'A'][1] != copyMat[multi-'A'][0]){  
45.                         printf("error\n");  
46.                         return ;  
47.                     }  
48.                     // 计算相乘次数，加上  
49.                     sum += copyMat[ex-'A'][0]*copyMat[multi-'A'][0]*copyMat[multi-'A'][1];  
50.                     // 相乘后得到一个新矩阵，更新尺寸  
51.                     copyMat[ex-'A'][1] = copyMat[multi-'A'][1];  
52.                 }  
53.                 st.push(ex);  
54.             }  
55.         }    
56.         printf("%d\n",sum);  
57.     }  
58. }  
59.   
60.   
61. int main()  
62. {  
63.     freopen("input.txt", "r",stdin);  
64.     char ch;  
65.     int  i, j;  
66.     scanf("%d%*c", &n);  
67.     for(i=0; i<n; ++i){  
68.         scanf("%c %d %d%*c",&ch,&mat[i][0],&mat[i][1]);  
69.     }  
70.       
71.     while(gets(str)){  
72.         solve();  
73.     }  
74.     return 0;  
75. }