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

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    //10*20*5+50*10*5=1000+2500=3500
    int num;
    while(cin>>num)
    {
        int data[num][2];
        for(int i=0; i<num; i++)
        {
            cin>>data[i][0]>>data[i][1];
        }
        string str;
        cin>>str;
        int pos = 0;
        int length = str.length();
        int flag = 0;
        int index = 0;
        int num = 0;
        stack<int> st1;
        stack<int> st2;
        while(pos<length)
        {

            while(str[pos] == '(')
            {
                flag ++;
                pos ++;
            }

            if(pos<length && str[pos]!='(' && str[pos]!=')')
            {
                if(flag == 0)
                {
                    st1.push(index);
                    index++;
                    pos++;
                    //flag = 0;
                }
                else
                {
                    for(int i=0; i<flag; i++)
                    {
                        st1.push(index);
                    }
                    index++;
                    pos++;
                    flag = 0;
                }

            }
            if(pos<length && str[pos]==')')
            {
                int tmp1 = data[st1.top()][1];
                //int tmp2 = data[st1.top()][0];
                st1.pop();
                num = data[st1.top()][0]*data[st1.top()][1]*tmp1;
                data[st1.top()][1] = tmp1;
                st1.pop();
                st2.push(num);
                pos++;
                while(pos<length && str[pos]==')')
                {
                    num = data[st1.top()][0]*data[st1.top()][1]*tmp1;
                    data[st1.top()][1] = tmp1;
                    st1.pop();
                    st2.push(num);
                    pos ++;
                }
            }
        }
        int result = 0;
        while(st2.size())
        {
            result += st2.top();
            st2.pop();
        }
        cout<<result<<endl;
    }
    return 0;
}