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

#include <string>
#include <iostream>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

int numsm1[125];
int numsn1[125];
// unordered_map<char >

inline int calculate(int m1,int n1,int k1)
{
	return m1*k1*n1;    
}
    

int main()
{
    string str1;
    int n1;
    while (cin>>n1)
    {
        int ans1=0;
        vector<char> sm1;
        for(int i=0;i<n1;++i)
        {
            cin>>numsm1[i]>>numsn1[i];
        }
        cin>>str1;
        for(int i=0;i<str1.size(); )
        {
            if(str1[i]=='(')
            {
                sm1.push_back('(');
                ++i;
            }
            else if(str1[i]==')')
            {
                if(sm1[sm1.size()-2]=='(')
                {
                    char c=sm1[sm1.size()-1];
                    sm1.pop_back();
                    sm1.pop_back();
                    sm1.push_back(c);
                    ++i;
                    
                }
                else
                {
                    int m2,n2,k2;
                    int index1=sm1[sm1.size()-1]-'A';sm1.pop_back();
                    int index2=sm1[sm1.size()-1]-'A';sm1.pop_back();
                    m2=numsm1[index2];
                    n2=numsn1[index2];
                    k2=numsn1[index1];
                    ans1+=calculate(m2,n2,k2);
                    numsm1[n1]=m2;
                    numsn1[n1]=k2;
                    sm1.push_back(n1+'A');
                    ++n1;
                }

            }
            else
            {
                sm1.push_back(str1[i]);
                ++i;
            }
        }
        cout<<ans1<<endl;
    }
    
    return 0;
}