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

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

typedef struct __Stack_ts {
    int row;
    int col;
    struct __Stack_ts* next;
} Stack_ts;

Stack_ts* Stack_new(int row, int col)
{
    Stack_ts* result = NULL;

    result = (Stack_ts*)malloc(sizeof(Stack_ts));
    result->row = row;
    result->col = col;
    result->next = NULL;

    return result;
}

Stack_ts* Stack_push(Stack_ts* head, int row, int col)
{
    Stack_ts* result = NULL;
    Stack_ts* node = NULL;

    node = Stack_new(row, col);
    node->next = head;
    head = node;

    result = head;
    return result;
}

Stack_ts* Stack_pop(Stack_ts* head, int* row, int* col)
{
    Stack_ts* result = NULL;
    Stack_ts* node = NULL;

    if (head != NULL) {
        node = head;
        *row = node->row;
        *col = node->col;
        head = head->next;
        free(node);
    } else {}    

    result = head;
    return result;
}


int main() {
    int a[15][2] = {};
    int a1[2],a2[2];
    int n,i,length;
    char s[15+28+1] = {};
    int sum = 0;
    Stack_ts* num = NULL;

    scanf("%d", &n);
    for (i=0; i<n; ++i) {
        scanf("%d %d", &a[i][0], &a[i][1]);
    }
    scanf("%s", s);
    length = strlen(s);
    for (i=0; i<length; ++i) {
        if (s[i] == ')') {
            num = Stack_pop(num, &a2[0], &a2[1]);
            num = Stack_pop(num, &a1[0], &a1[1]);
            sum += a1[0]*a2[1]*a1[1];
            num = Stack_push(num, a1[0], a2[1]);
        } else if (s[i]>='A' && s[i]<='Z') {
            num = Stack_push(num, a[s[i]-'A'][0], a[s[i]-'A'][1]);
        } else {}
    }
    printf("%d", sum);

    return 0;
}