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

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;    //矩阵的个数n
    while(cin>>n) {
        vector<pair<int, int>> matrix;    //存放每个矩阵的行数和列数
        for(int i=0;i<n;i++) {    //依次输入n个矩阵的行数和列数，并保存在容器matrix中
            int row,arrange;
            cin>>row>>arrange;
            matrix.push_back(make_pair(row, arrange));
        }
        string rule;    //存放计算的法则
        cin>>rule;    //输入法则rule
        stack<char> sign;    //符号栈
        stack<pair<int, int>> Stack_matrix;    //矩阵栈
        int count=0;    //乘法次数
        for(int i=0;i<rule.length();i++) {    //按照计算法则求矩阵的乘法次数
            if(rule[i]=='(') {    //'('为待匹配的符号，压入符号栈中
                sign.push(rule[i]);
            }else if(rule[i]>='A' && rule[i]<='Z') {    //如果为字母，将该字母对应的矩阵添加到矩阵栈中
                Stack_matrix.push(matrix[rule[i]-'A']);
            }else if(rule[i]==')') {    //如果当前符号为')'，将符号栈中的'('出栈
                sign.pop();
                pair<int, int> matrix2 = Stack_matrix.top();    //依次弹出矩阵栈的两个栈顶矩阵
                Stack_matrix.pop();
                pair<int, int> matrix1 = Stack_matrix.top();
                Stack_matrix.pop();
                count += matrix1.first*matrix1.second*matrix2.second;    //累加乘法次数
                Stack_matrix.push(make_pair(matrix1.first, matrix2.second));    //将矩阵相乘的结果重新压入栈中
            }
        }
        cout<<count<<endl;    //输出矩阵相乘的乘法总次数
    }
    return 0;
}