题意：

        A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵

        计算A*B*C有两种顺序：（（AB）C）或者（A（BC）），前者需要计算15000次乘法，后者只需要3500次。

        编写程序计算不同的计算顺序需要进行的乘法次数。


方法一：
栈

思路：
        栈存储矩阵的行和列。
        遍历字符串：
                                如果是字符，则直接入栈；
                               如果是右括号，则栈弹出两个元素，并累加乘法次数，再形成新的矩阵并入栈。
      在这过程并累加乘法次数，最后输出乘法次数。 



#include <bits/stdc++.h>

using namespace std;
int a[20][2];
string s;

int main(){
    int n;
    while(cin >> n){
        for(int i=0;i<n;i++)
            cin >> a[i][0] >> a[i][1];//输入矩阵的行列
        cin >>s;
        stack<pair<int,int>> st;//栈存储矩阵的行列
        int len=s.size();
        int res=0;
        for(int i=0;i<len;i++){//遍历字符串
            if(s[i]==')'){//如果是右括号，则栈弹出两个元素，并累加乘法次数
                auto y=st.top();
                st.pop();
                auto x=st.top();
                st.pop();
                if(x.second==y.first){
                    res+=x.second*x.first*y.second;
                    st.push({x.first,y.second});//形成新的矩阵并入栈
                }else if(x.first==y.second){
                    res+=x.first*x.second*y.first;
                    st.push({x.second,y.first});
                }
                
            }else if(s[i]!='('){//如果是字符，则直接入栈
                int t=s[i]-'A';
                st.push({a[t][0],a[t][1]});
            }
        }
        cout << res << endl;//输出答案
    }
    
    return 0;
}


时间复杂度：
空间复杂度：

方法二
递归

思路：
        通过递归找到左右边界点。
        规则：
                遍历给定字符串的 l , r 区间，如果找到左括号，则循环找到匹配的右括号，并递归下去。
                最后，计算两个矩阵的值赋给全局变量res,并且生成新的矩阵。

 

#include <bits/stdc++.h>

using namespace std;
int a[20][2];
string s;
int res=0,n;

//递归
pair<int,int> f(int l,int r){

    stack<pair<int,int>> st;
    for(int i=l;i<=r;i++){
        if(s[i]=='('){
            int j=i+1;
            int level=1;
            while(j<=r){//循环找到匹配的右括号
                if(s[j]=='('){
                    level++;
                }else if(s[j]==')'){
                    level--;
                    if(level==0){
                        auto t=f(i+1,j-1);//递归
                        st.push(t);//后序入栈
                        break;
                    }
                }
                j++;
            }
            i=j;
        }else if(isalpha(s[i])){
            int x=s[i]-'A';
            st.push({a[x][0],a[x][1]});
        }
    }
    auto t2=st.top();
    st.pop();
    auto t1=st.top();
    st.pop();
    res+=t1.first*t1.second*t2.second;//构造新的矩阵
    return {t1.first,t2.second};
}

int main(){
    while(cin >> n){
        res=0;
        for(int i=0;i<n;i++)
            cin >> a[i][0] >> a[i][1];//输入矩阵的行列
        cin >>s;
        f(1,s.size()-2);//递归
        cout << res << endl;//输出答案
    }
    
    return 0;
}
时间复杂度：
空间复杂度：