解题思路

这道题目要求我们根据给定的矩阵乘法表达式（可能包含括号）计算所需的乘法次数，如果矩阵维度不匹配则输出 error。

关键步骤

1. 存储矩阵信息

   • 使用 map 或 unordered_map 存储每个矩阵的行数和列数，方便后续查找。

2. 解析表达式并计算乘法次数

   • 使用 栈（Stack） 来解析带括号的表达式：
     • 遇到 ( 时，压栈。
     • 遇到 ) 时，弹出栈顶的两个矩阵（或中间结果）进行计算：
       • 检查矩阵维度是否匹配（前一个矩阵的列数是否等于后一个矩阵的行数）。
       • 如果不匹配，直接返回 error。
       • 如果匹配，计算乘法次数并更新当前矩阵的行列数。
     • 遇到矩阵名称时，直接压栈。

3. 最终结果

   • 如果计算过程中没有错误，输出总乘法次数；否则输出 error。

C++ 代码实现

#include <iostream>
#include <stack>
#include <map>
#include <string>
using namespace std;

struct Matrix {
    int row, col;
};

int main() {
    int n;
    cin >> n;
    map<char, Matrix> mat;

    // 读取矩阵信息
    for (int i = 0; i < n; i++) {
        char name;
        int r, c;
        cin >> name >> r >> c;
        Matrix tmp;
        tmp.row = r;
        tmp.col = c;
        mat[name] = tmp;
    }

    string expr;
    while (cin >> expr) {
        stack<Matrix> st;
        bool error = false;
        int total = 0;

        for (int i = 0; i < expr.size(); i++) {
            char c = expr[i];
            if (c == '(') {
                continue;  // 左括号不处理
            } else if (c == ')') {
                // 弹出栈顶两个矩阵进行计算
                if (st.size() < 2) {
                    error = true;
                    break;
                }
                Matrix b = st.top(); st.pop();
                Matrix a = st.top(); st.pop();

                // 检查维度是否匹配
                if (a.col != b.row) {
                    error = true;
                    break;
                }

                // 计算乘法次数
                total += a.row * a.col * b.col;

                // 新的矩阵行列
                Matrix new_mat;
                new_mat.row = a.row;
                new_mat.col = b.col;
                st.push(new_mat);
            } else {
                // 矩阵名称，直接压栈
                if (mat.find(c) == mat.end()) {
                    error = true;
                    break;
                }
                st.push(mat[c]);
            }
        }

        if (error || st.size() != 1) {
            cout << "error" << endl;
        } else {
            cout << total << endl;
        }
    }

    return 0;
}