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

#include <stdio.h>
#include <ctype.h>

typedef struct
{
    int row;        //行数
    int col;        //列数
}Matric_t;


int main()
{
    Matric_t matric[15] = {0};
    Matric_t stack[15] = {0};
    char rule[50];
    int num;
    int index = -1;
    int stack_index = -1;
    int mul_count = 0;
    
    if(scanf("%d", &num) == EOF)
    {
        return 0;
    }
    
    for(int i = 0; i < num; i++)
    {
        scanf("%d%d", &(matric[i].row), &(matric[i].col));
    }
    
    scanf("%s", rule);
    
    for(int i = 0; i < strlen(rule); i++)
    {
        if(isupper(rule[i]))                // 为大写字母则 将数据入栈
        {
            ++index;
            ++stack_index;
            stack[stack_index].row = matric[index].row;
            stack[stack_index].col = matric[index].col;
        }
        else if(rule[i] == ')')
        {
            /* 新生成的矩阵行列数 */
            Matric_t temp;
            temp.row = stack[stack_index-1].row;
            temp.col = stack[stack_index].col;
            
            /* 题意 不会出现 （ABC）情况, 故相邻相乘即可 */
            /* 计算当前乘法次数 */
            mul_count += stack[stack_index-1].row * stack[stack_index-1].col * stack[stack_index].col;
//              printf("stack_index - 1 -> row = %d, col = %d, -> row = %d, col = %d, count = %d \n",stack[stack_index-1].row, 
//             stack[stack_index-1].col, stack[stack_index].row, stack[stack_index].col, mul_count);
            stack_index -= 2;    //已计算的矩阵出栈
            ++stack_index;       //将相乘新生成的矩阵入栈
            stack[stack_index].row = temp.row;
            stack[stack_index].col = temp.col;
            
           
        }
    }
    
    printf("%d", mul_count);
    
    return 0;
}