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

#include <cctype>
#include <iostream>
#include <stack> 
using namespace std;
/*栈便于解决字符串中判断顺序的问题
由栈来存放字符串，可以获得计算的顺序。如（A（BC））如果来的是左括号就忽略，是字母，就把对应矩阵的行列长度压到栈中，是右括号，就弹出最上面的两个矩阵的行列来计算,计算结果压回到栈中。
要同时存储行列两个数据，先用二维数组来分别接收每一组行列，往栈中压的时候选择pair<int,int>类型即可每次压两个一组的数据
关于如何计算乘法运算次数：A（m*n）B(n*k) 相乘，A一行要乘n次，然后A的这一行要和B的k列每列都算一遍，同样的过程A要算M行，所以就是m*n*k */
int main() {
    int n;
    cin>>n;
    int a[n][2];//每行用来存一个矩阵的行列
    for(int i=0;i<n;i++){
    cin>>a[i][0]>>a[i][1];}
    string s;
    cin>>s;
    int res=0;
    stack<pair<int,int>>st;
    for(int i=0;i<s.size();i++){
        if(isalpha(s[i])){//遍历字符串，如果来的是字母，就把对应的矩阵行列压到栈中
            int t=s[i]-'A';
            st.push({a[t][0],a[t][1]});
        }
        else if(s[i]==')'){//如果来的是）就开始计算当前相邻的两个矩阵的计算次数
            pair<int,int>x=st.top();
            st.pop();
            pair<int,int>y=st.top();
            st.pop();
            if(y.second==x.first){res+=y.first*y.second*x.second;}
            st.push({y.first,x.second});
        }
    }
    cout<<res<<endl;
    
}

遇到判断字符串内部的计算顺序类的问题，都可以考虑一下栈