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

#include <cctype>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> m(n, vector<int>(2, 0));
    for (int i = 0; i != n; ++i) {
        cin >> m[i][0] >> m[i][1];
    }
    string op;
    cin >> op;
    stack<vector<int>> t;
    stack<char> p;
    long result = 0;
    for (int i = 0; i != op.size(); ++i) {
        if (op[i] == '(')
            p.push(op[i]);
        else if (isalpha(op[i])) {
            vector<int> k = { m[static_cast<int>(op[i] - 'A')][0], m[static_cast<int>(op[i] - 'A')][1] };
            t.push(k);
            if (isalpha(op[i + 1]) || op[i + 1] == '(')
                p.push('*');
        } else if (op[i] == ')') {
            while (!p.empty() && p.top() != '(') {
                vector<int> k = t.top();
                t.pop();
                vector<int> k2 = t.top();
                t.pop();
                result += k2[0] * k2[1] * k[1];
                p.pop();
                vector<int> new_v = { k2[0], k[1] };
                t.push(new_v);
            }
            if (!p.empty()) {
                p.pop();
                if (i < op.size() - 1 && (isalpha(op[i + 1]) || op[i + 1] == '('))
                    p.push('*');
            }
        }

    }
    cout << result;
}

依然使用双栈法，先进先出，遇到括号就开始往外弹出