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

#include <iostream>
using namespace std;
#include <stack>
#include <string>
#include <vector>
int caculate(int x, int y, int z) {
    return x * y * z;
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> mas;
    // cout << "n: " << n << endl;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        // cout << "ab: " << a <<" "<< b << endl;
        mas.emplace_back(a, b);
    }
    string str;
    cin >> str;
    stack<char> sk;
    stack<pair<int, int>> mask;
    // j指向当前入栈矩阵在mas数组中的编号,初始为-1
    int res = 0;

    // cout << "str: " << str << endl;
    for (int i = 0, j = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            sk.push('(');
        } else if (str[i] >= 'A' && str[i] <= 'Z') {

            if (sk.top() != '(') {
                int x = mask.top().first;
                int y = mask.top().second;
                int z = mas[j].second;
                res = res + caculate(x, y, z);
                mask.pop();
                mask.push(pair<int, int>(x, z));
                j++;
            } else {
                sk.push(str[i]);
                mask.push(mas[j]);
                j++;
            }
        } else if (str[i] == ')') {
            sk.pop();
            sk.pop();
            if (!sk.empty() && sk.top() != '(') {
                int z = mask.top().second;
                mask.pop();
                int x = mask.top().first;
                int y = mask.top().second;
                res = res + caculate(x, y, z);
                mask.pop();
                mask.push(pair<int, int>(x, z));
            } else if (!sk.empty() && sk.top() == '(') {
                sk.push('X');
            }
        }
    }
    cout << res << endl;
}

主要是对输入的处理，使用栈，对每个进入的字符进行判断，如果上一入栈的也是矩阵，则计算2者的乘法次数加到总数上，弹出旧的矩阵信息并将新矩阵信息入栈，符号不动（2矩阵相乘剩下一个矩阵），若为左括号则直接入栈，若为右括号则弹出一个2个符号并在栈非空时补入一个矩阵型符号。矩阵的信息单独拿一个数组和一个栈来保存。

栈的用法，总体思路可以参考HJ50四则运算，不过这个只有一种运算，一个栈（逻辑上的）就够了，只不过字符不包含矩阵信息，所以多用了个栈来存储矩阵的信息，所以看上去比较绕。