题解 | #矩阵乘法计算量估算#C++解法，调试了好久。终于把思路理清楚了

//解题思路，逐个字符解析计算法则的字符串
//1.遇到'('直接跳过，看下一个元素
//2.遇到字母，入栈。若下一个字符也是字母，出栈一个元素与下一个矩阵直接计算出结果，
//  然后将计算后的矩阵入栈，直到下一个不是字母。
//3.遇到字母,入栈。若下一个字符不是字母，直接看下一个字符
//4.遇到')'，如果是第一个，则跳过，如果不是第一个，则计算栈最上面两个矩阵的乘法次数，并累加
#include<iostream>
#include<stack>
#include<vector>
#include<string>
using namespace std;
int fun(int n)
{
    vector<pair<int,int>> v;//存矩阵
    pair<int,int> p;
    while(n--)
    {
        cin>>p.first>>p.second;
        v.push_back(p);
    }
    string str;//存计算法则
    cin>>str;
    int num=0;//用来存乘法次数
    stack<pair<int,int>> s;//栈，存计算后的矩阵
    pair<int,int> p_tmp;//临时元素，存临时矩阵
    int count=0;//用来标记')‘个数
    for(int i=0;i<str.size();)
    {
        if(str[i]=='(') //遇到'('直接跳过，看下一个元素
        {
            i++;
            continue;
        }
        if(str[i]>='A'&&str[i]<='Z')
        {
            {
                s.push(v[str[i]-'A']);//遇到字母，入栈。
            }
            //若下一个字符也是字母，出栈一个元素与下一个矩阵直接计算出结果，
            //然后将计算后的矩阵入栈，直到下一个不是字母。
            while((i+1)<str.size()&&str[i+1]>='A'&&str[i+1]<='Z')
            {
                p_tmp.first=s.top().first;
                p_tmp.second=v[str[i+1]-'A'].second;
                num+=s.top().first*s.top().second*v[str[i+1]-'A'].second;
                s.pop();
                s.push(p_tmp);
                i++;
            }
            //若下一个字符不是字母，直接看下一个字符
             i++;
            continue;
        }
         if(str[i]==')')
            {
             //遇到')'，如果是第一个，则跳过，如果不是第一个，则计算栈最上面两个矩阵的乘法次数，并累加
                if(count==0&&(i+1)<str.size())
                 {
                     count++;
                     i++;
                    continue;
                 }
                if(s.size()>1)//栈中有多个元素，需要计算最上面两个矩阵
                {
                    p_tmp.first=s.top().first;
                    p_tmp.second=s.top().second;
                    s.pop();
                    num+=s.top().first*s.top().second*p_tmp.second;
                    p_tmp.first=s.top().first;
                    s.pop();
                    s.push(p_tmp);
                    i++;
                    continue;
                }
               if(s.size()==1)//栈中只有一个元素则不用计算了
                {
                    cout<<num<<endl;
                    return 0;
                }
            }
    }
    cout<<num<<endl;//最后输出乘法次数
    return 0;
}
int main()
{
    int n;
    while(cin>>n)
    {
        fun(n);
    }
}