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

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n = 0;
    while(cin >> n){
        vector<pair<int, int>> matrixs(n); //行数和列数
        for(int i = 0; i < n; i++){
            cin >> matrixs[i].first;
            cin >> matrixs[i].second;
        }
        string s = "";
        cin >> s;
        
        //矩阵乘法 第一行第一列相乘相加
        //A是一个50×10的矩阵，B是10×20的矩阵  则次数为：50×10×20
        int res = 0;
        stack<pair<int, int>> st; //栈存储矩阵的行数和列数
        for(int i = 0; i < s.size(); i++){ //遍历字符串
            if(s[i] == ')'){ //如果是右括号，则栈弹出两个元素，并累加乘法次数
                auto y = st.top(); //后面的矩阵
                st.pop();
                auto x = st.top(); //前面的矩阵
                st.pop();
                
                if(x.second == y.first){
                    res += x.first * x.second * y.second;
                    st.push({x.first, y.second}); // //把形成的新矩阵的行数和列数入栈
                }
                //
                /*else if(y.second == x.first){
                    res += y.first * y.second * x.second;
                    st.push({y.first, x.second}); //把形成的新矩阵的行数和列数入栈
                }*/
            }
            else if(s[i] != '('){ ////如果是字符，则直接入栈
            //else if(isalpha(s[i])){   
                // A是第一个矩阵 它的行数和列数对应matrix[0]
                int t = s[i] - 'A';
                st.push(make_pair(matrixs[t].first, matrixs[t].second));
            }
        }
        
        //输出
        cout << res << endl;
    }
    
    return 0;
}