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

//C++实现55行代码

#include<iostream>
#include<string>
#include<vector>                        //vector用于存放矩阵向量
#include<stack>                         //stack用于字符串的存取处理
using namespace std;
int main()
{
    int num=0;
    string str;
    while(cin>>num)
    {
        vector<int> v;
        int temp=0;
        for(int i=0;i<num*2;++i)
        {
            cin>>temp;
            v.push_back(temp);
        }
        cin>>str;                                    //以上步骤用于获取输入，变量有num、v、str
        int res=0;                                   //存放最终的计算总数
        int len=str.length();
        stack<char> s2;                                    //栈s2存放第一次遍历的字符
        stack<char> s3;                                    //栈s3存放要处理的字符
        for(int i=0;i<len;++i)                                   //遍历字符串
        {
            if(str[i]==')')                                //如果遇到右括号')'就开始处理，否则压入s2
            {
                char temp;
                while(s2.top()!='(')
                {
                    temp=s2.top();
                    s3.push(temp);
                    s2.pop();
                }                               //将括号内的字符提取至s3
                s2.pop();                               //s2内的左括号'('出栈
                int sum=0;                               //记录一对括号内的计算次数
                char c=s3.top();                              //一个括号组内不止两个矩阵，要记录第一个矩阵的字母
                s2.push(c);                               //很重要，代表这个括号内矩阵的索引
                int first=c-'A';                              //一个括号组内不止两个矩阵，要记录第一个矩阵的大小位置
                s3.pop();                               //第一个矩阵出栈
                while(s3.size())                               //括号内其他矩阵与第一个矩阵运算
                {
                    int num1=s3.top()-'A';             //记录第二个矩阵的位置信息
                    s3.pop();                    //已经计算过的矩阵出栈
                    sum=sum+v[first*2]*v[num1*2]*v[num1*2+1];    //当前矩阵计算次数之和
                    v[first*2+1]=v[num1*2+1];            //更新第一个矩阵的大小信息
                }
                res+=sum;                                //计算总数
            }else   s2.push(str[i]);
        }
        cout<<res<<endl;
    }
    return 0;
}