题解 | #矩阵乘法计算量估算#

#include <stdio.h>
#include <string.h>

int n;
void compute(char s[], int arr_size[][2],int len, int size_r[]);
int multi_num;

int main() {
    int n;
    int arr_size[20][2];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d", &arr_size[i][0],&arr_size[i][1]);
    }

    int size_r[2];
    char s[200] = {0};
    scanf("%s",s);
    int len = strlen(s);

    n = 0;
    multi_num = 0;
    compute(s,arr_size,len,size_r);//计算法则，矩阵大小数组，法则字符长度，中间变量存储
    printf("%d\n",multi_num);

    return 0;
}

void compute(char s[], int arr_size[][2],int len, int size_r[])
{
    int size[26][2];//每次计算括号内的矩阵大小：行、列
    int i = 0;

    while(n<len){
        if(s[n]=='('){
            n++;
            compute(s,arr_size,len,size_r);
            size[i][0] = size_r[0];
            size[i][1] = size_r[1];
            i++;
        }
        else if(s[n] == ')'){ //一次递归完成
            n++;
            break;
        }
        else{
            size[i][0] = arr_size[s[n] - 'A'][0]; //保证每次计算的矩阵均从size中的第一行开始
            size[i][1] = arr_size[s[n] - 'A'][1];
            n++;
            i++;
        }
    }
    for(int j=0; j<i-1; j++)
    {
        multi_num = multi_num + size[j][0]*size[j][1]*size[j+1][1];//10*20*5矩阵乘法计算次数
        size[j+1][0] = size[j][0];
    }
    size_r[0] = size[0][0]; //递归完成后的当前结果存储至临时变量
    size_r[1] = size[i-1][1];
}