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

//用栈做吧
//遍历一遍输入的字符串就行，如果是'('入栈
//如果是字母就检测栈顶，如果栈顶是数字就做一次矩阵计算，栈顶是'('就入栈
//如果是')'，弹出字母和'('，并检测栈顶，栈顶是数字就需要再做一次矩阵计算，栈顶是'('就入栈

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

int main(){
    int n;
    cin >> n;
    vector<vector<int>> vecinput(n,vector<int>(2,0));
    for(int i = 0;i<n;++i){
        cin >> vecinput[i][0] >> vecinput[i][1];
    }
    string inputstr;
    cin >> inputstr;
    stack<vector<int>> stmat;//矩阵栈
    int sum = 0;
    for(int i = 0;i<inputstr.size();++i){
        if(inputstr[i] == '('){
            stmat.push(vector<int>(1,0));
        }
        else if (inputstr[i] == ')'){
            vector<int> tmp = stmat.top();
            stmat.pop();
            stmat.pop();
            if(!stmat.empty()){
                if(stmat.top().size() == 2){
                    vector<int> tmptop = stmat.top();
                    sum += tmptop[0]*tmptop[1]*tmp[1];
                    stmat.pop();
                    tmptop[1] = tmp[1];
                    stmat.push(tmptop);
                }
                else{
                    stmat.push(tmp);
                }
            }
            else stmat.push(tmp);
        }
        else{
            if(stmat.empty())stmat.push(vecinput[inputstr[i]-'A']);
            else{
                if(stmat.top().size() == 1){//栈顶是左括号
                    stmat.push(vecinput[inputstr[i]-'A']);
                }
                else{//栈顶有数字
                    vector<int> tmp = stmat.top();
                    sum += tmp[0]*tmp[1]*vecinput[inputstr[i]-'A'][1];
                    stmat.pop();
                    tmp[1] = vecinput[inputstr[i]-'A'][1];
                    stmat.push(tmp);
                }
            }
        }
    }
    cout << sum << endl;
    return 0;
}