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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct{
    int row;
    int col;
}RCT;

int _lastRctType = 0;
int rctLen = 0;
int _sum = 0;

int comput1(RCT* arr, int* computArr,int len)
{
    int retsum = 0;
    RCT a0 =arr[computArr[len-1] -'A'];
    for(int i = len-1; i > 0; i--)
    {
        retsum += a0.row * a0.col * arr[computArr[i-1] -'A'].col;
        a0.col = arr[computArr[i-1] -'A'].col;
    }
    arr[rctLen] = a0;
    _lastRctType = rctLen + 'A';
    rctLen++;
    
    return retsum;
}

int getValue(RCT* arr, char* str)
{
    int stack[16];
    int top = 0;
    int strLen = strlen(str);
    int computeArr[16] = {0};
    int computeArrLen = 0;

    for(int i = 0; i <strLen; i++)
    {
        if(')' == str[i] || (i == strLen-1)){
            //comput
            while(stack[top-1] != '(' && top >= 1)
            {
                computeArr[computeArrLen++] = stack[top-1];
                top--;
            }
            top--;//去 '('
            _sum += comput1(arr,computeArr,computeArrLen);
            stack[top++] = _lastRctType;
            computeArrLen = 0;
        }
        else {
            stack[top++] = str[i];
        }
    }

    return _sum;
}

int main() {
    RCT rec[100] = {0};
    int n;
    int row,col;
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d %d",&row,&col);
        rec[i] = (RCT){row,col};
        rctLen++;
    }
    char str[128] = {0};
    scanf("%s",str);

    printf("%d",getValue(rec, str));
    return 0;
}