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

#include <stdio.h>

/* 保存矩阵的行、列数 */
typedef struct
{
	int x;	//行数
	int y;	//列数
}CoordinateInfo_t;

/*
思路：
例a为2*3的矩阵，b为3*2的矩阵，生成结果矩阵c为2*2的
a[x][y],b[y][z]
1、矩阵乘法运算公式：
c[0][0] += a[0][0]*b[0][0] + a[0][1]*b[1][2] + a[0][2]*b[2][0] 
c[0][1] += a[0][0]*b[2][0] + a[0][1]*b[2][1] + a[0][2]*b[2][2]
c[1][0] += a[1][0]*b[0][1] + a[1][1]*b[1][0] + a[1][2]*b[2][0]
c[1][1] += a[1][0]*b[0][1] + a[1][1]*b[1][1] + a[1][2]*b[2][1]
2、乘法矩阵的乘法运算次数为x*z*y.
*/
int main()
{
    int n = 0;
    scanf("%d", &n);
	CoordinateInfo_t pCoordInfo[n];
    memset(pCoordInfo, 0, n*sizeof(CoordinateInfo_t));
	CoordinateInfo_t stack[n];
    memset(stack, 0, n*sizeof(CoordinateInfo_t));
    for(int i = 0; i < n; i++)
    {
        scanf("%d %d", &pCoordInfo[i].x, &pCoordInfo[i].y);
        //printf("pCoordInfo[%d] = [%d : %d]\n", i, pCoordInfo[i].x,pCoordInfo[i].y);
    }
    char str[32] = {0};
    scanf("%s", str);
    //printf("str = [%s]\n", str);
	int len = strlen(str);
	int index = -1;	//因为跳过开始的
	int count = -1;
	int sum = 0;	//获取*的数量
	/* 以(A(BC))为例 */
	for(int i = 0; i < len; i++)
	{
		if(str[i] >= 'A' && str[i] <= 'Z')
		{
			index++;
			count++;
			stack[index].x = pCoordInfo[count].x;    //数据入栈
			stack[index].y = pCoordInfo[count].y;
		}
		/* 此时，index = 2 */
		else if(str[i] == ')')
		{
			CoordinateInfo_t temp = {0};
			temp.x = stack[index-1].x;	//B的x
			temp.y = stack[index].y;	//C的y
			sum += stack[index-1].x * stack[index].x * stack[index].y;
			//printf("sum = [%d]\n", sum);
            index -= 2;		//出栈，退到A的位置
			index += 1;		//BC计算后新的矩阵的位置
			/* 保存新矩阵的大小 */
			stack[index].x = temp.x;
			stack[index].y = temp.y;
		}
	}
	printf("%d\n", sum);
    return 0;
}