本文共 1503 字，大约阅读时间需要 5 分钟。

5134

59.82%

2559

92.93%

题目链接：

题目类型： 数据结构， 链表

样例输入：

9A 50 10B 10 20C 20 5D 30 35E 35 15F 15 5G 5 10H 10 20I 20 25ABC(AA)(AB)(AC)(A(BC))((AB)C)(((((DE)F)G)H)I)(D(E(F(G(HI)))))((D(EF))((GH)I))

000error10000error350015000405004750015125

题目大意：

给出一系列的矩阵，给他们取名A ，B……   以及它们的行数和列数。给完后，给出一系列的表达式，然后要求求出按这些表达式进行计算，会有多少次乘法步骤。

解体思路：

这题和括号匹配那题很像。关键的步骤是计算矩阵乘法次数的这个过程。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int sum,n;int mat[30][2];int arr[30],prev[30], next[30];char str[1000];void solve(){    // 如过只有一个矩阵，那么直接输出结果0    if(strlen(str)==1 && isupper(str[0])){        printf("0\n");    }    else{        char copyMat[30][2];        int i,j;        // 复制一个数组进行操作。 因为后面的操作需要对这些矩阵进行修改        for(i=0; i
        
         st; for(i=0; i
         
          temp; // 当碰到‘）’时，把栈中的矩阵全都取出来进行计算 while(isupper(st.top())){ temp.push(st.top()); st.pop(); } // 把'('也弹出 st.pop(); char ex; // 取出第一个矩阵（在原表达式中是最左边的一个） if(!temp.empty()){ ex=temp.top(); temp.pop(); } while(!temp.empty()){ char multi = temp.top(); temp.pop(); // 如果左边矩阵的列数和右边矩阵的函数不同，则直接输出 error if(copyMat[ex-'A'][1] != copyMat[multi-'A'][0]){ printf("error\n"); return ; } // 计算相乘次数，加上 sum += copyMat[ex-'A'][0]*copyMat[multi-'A'][0]*copyMat[multi-'A'][1]; // 相乘后得到一个新矩阵，更新尺寸 copyMat[ex-'A'][1] = copyMat[multi-'A'][1]; } st.push(ex); } } printf("%d\n",sum); }}int main(){ freopen("input.txt", "r",stdin); char ch; int i, j; scanf("%d%*c", &n); for(i=0; i
         
        
       
      
     
    
   

转载地址：http://xuzni.baihongyu.com/