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

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin >> n;
    // n * 2的输入
    vector<vector<int>> vec(n, vector<int>(2));
    for (int i = 0; i < n; i++) {
        cin >> vec[i][0] >> vec[i][1];
    }
    string rule;
    cin >> rule;
    // 双栈法
    stack<pair<int, int>> nums;
    stack<char> op;
    // 计算量累加
    int res = 0;
    // 两两计算栈中元素的计算量，直到栈元素为1
    auto compute = [&](stack<pair<int, int>> s) {
        while (s.size() != 1) {
            auto [a, b] = s.top();
            s.pop();
            auto [c, d] = s.top();
            s.pop();
            res += (a * d * c);
            auto tmp = std::make_pair(a, d);
            s.push(tmp);
        }
        return s.top();
    };
    // 标记字母对应的索引用于取维度值
    int idx = 0;
    for (int i = 0; i < rule.size(); i++) {
        int c = rule[i];
        if (std::isalpha(c)) {
            // 维度值入栈
            nums.push({vec[idx][0], vec[idx][1]});
            idx++;
            // 字母入操作栈
            op.push(c);
        } else {
            // 左括号入栈
            if (c == '(') {
                op.push(c);
            } else {
                // 将括号之间的矩阵运算按照正向顺序排列
                stack<pair<int, int>> tmps;
                while (op.top() != '(') {
                    tmps.push(nums.top());
                    nums.pop();
                    op.pop();
                }
                // '('出栈
                op.pop();
                // 将括号内的计算结果放入nums栈
                nums.push(compute(tmps));
                // 占位符，标记新放入的计算结果
                op.push('A');
            }
        }
    }
    cout << res << endl;
}
// 64 位输出请用 printf("%lld")