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

#include <iostream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

// 矩阵结构
struct Matrix {
    int rows;
    int cols;
};

// 读取矩阵信息
vector<Matrix> readMatrices(int n) {
    vector<Matrix> matrices(n);
    for (int i = 0; i < n; i++) {
        cin >> matrices[i].rows >> matrices[i].cols;
    }
    return matrices;
}

// 处理右括号的逻辑
void processParenthesis(stack<int>& indices, vector<Matrix>& matrices, int& totalCost) {
    int rightIndex = indices.top();
    indices.pop();
    int leftIndex = indices.top();
    indices.pop();

    // 计算当前乘法的运算量
    int cost = matrices[leftIndex].rows * matrices[leftIndex].cols * matrices[rightIndex].cols;
    totalCost += cost;

    // 更新左矩阵的列数为右矩阵的列数
    matrices[leftIndex].cols = matrices[rightIndex].cols;

    // 将更新后的左矩阵索引重新压入栈
    indices.push(leftIndex);
}

// 解析表达式并计算运算量
int parseExpression(const string& expression, vector<Matrix>& matrices) {
    stack<int> indices; // 存储矩阵索引
    int totalCost = 0;  // 总运算量

    for (size_t i = 0; i < expression.size(); ++i) {
        if (expression[i] == '(') {
            // 遇到左括号，直接跳过
            continue;
        } else if (expression[i] == ')') {
            // 遇到右括号，调用封装的函数处理
            processParenthesis(indices, matrices, totalCost);
        } else if (isalpha(expression[i])) {
            // 遇到矩阵，记录其索引
            int index = expression[i] - 'A';
            indices.push(index);
        }
    }

    return totalCost;
}

int main() {
    int n;
    cin >> n;
    vector<Matrix> matrices = readMatrices(n);
    string expression;
    cin >> expression;

    int totalCost = parseExpression(expression, matrices);

    cout << totalCost << endl;

    return 0;
}