题目的主要信息：

输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则，根据计算法则估算计算量的大小。

方法一：

使用栈。用matrix保存所有矩阵的大小，用ans储存计算量，遍历一遍计算法则：

当前字符如果不是 ')' 也不是 '(' 时，就让矩阵入栈；
当前字符是 ')' 时，从栈顶获得两个矩阵x和y，计算x和y相乘的计算量大小，累加到ans中，同时将他们俩相乘的结果矩阵大小存入栈中。最后遍历结束，ans即为整个过程的计算量。 具体做法：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    int n;
    while(cin >> n) {
        string rule;
        vector<pair<int, int>> matrix;
        for (int i = 0; i < n; ++i) {//输入n个矩阵的行数和列数
            pair<int, int> temp;
            cin >> temp.first >> temp.second;
            matrix.push_back(temp);
        }
        cin >> rule;//输入计算法则
        stack<pair<int, int>> stk;
        int ans = 0, k = 0;
        for (int i = 0; i < rule.size(); ++i) {//遍历一遍计算法则
            if (rule[i] == ')') {//当为右括号时从栈中取出两个矩阵计算
                pair<int, int> y = stk.top();
                stk.pop();
                pair<int, int> x = stk.top();
                stk.pop();
                ans += x.first * x.second * y.second;//计算量
                pair<int, int> temp(x.first, y.second);//结果矩阵的大小
                stk.push(temp);
            } else if(rule[i] != '('){
                stk.push(matrix[k]);//当前为字母时，矩阵进栈
                k++;
            }
        }
        cout << ans <<endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，n为矩阵个数，从栈中遍历一遍所有矩阵进行计算。
空间复杂度： $O (n)$ ，最坏情况下，栈中要保存所有矩阵。

方法二：

采用递归。用compute函数计算法则为str的矩阵计算量大小，保证输入compute函数的首尾均为匹配的括号，因此第一步先将首位括号去除，然后遍历一遍计算法则str，用栈stk保存需要计算的矩阵：

当前字符是 '(' 时，首先找到与之匹配的右括号，对括号内的内容进行递归计算，如果当前栈中为空，则在它之前没有矩阵，无需计算；如果栈不为空，表示需要和之前的矩阵进行计算，累加计算量，然后将计算的结果矩阵存入栈中。
当前字符是矩阵时，无需递归，直接和栈运算，如果当前栈中为空，则在它之前没有矩阵，无需计算；如果栈不为空，表示需要和之前的矩阵进行计算，累加计算量，然后将计算的结果矩阵存入栈中。

最后栈顶元素即为计算法则最终结果的矩阵。

具体做法：

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

using namespace std;

map<char, pair<int, int> > matrix;//矩阵和大小之间的映射
int count;//计算量

pair<int, int> compute(string str){
    stack<pair<int, int> > stk; //记录尚未计算的矩阵
    str = str.substr(1, str.size()-2);//去掉首位的两个括号
    for(int i = 0; i < str.size();i++){
        if(str[i] == '('){ //如果是左括号，需要递归计算
            int layer = 0; 
            int j = i;
            while(j <= str.size()){//找到和当前左括号匹配的右括号
                if(str[j] == '('){
                    layer++;
                }else if(str[j] == ')'){
                    layer--;
                }
                if(layer == 0){
                    break;
                }
                j++;
            }
            pair<int, int> res = compute(str.substr(i, j - i + 1));//递归计算括号中的部分
            i = j ;//从括号后面的内容继续遍历
            if(stk.empty()){ //如果stk为空，表示当前得到的矩阵是第一个矩阵，需要存下，等待下一个矩阵计算
                stk.push(res);
            }else{ //若stk不为空，需要计算
                pair<int, int> temp = stk.top();
                stk.pop();
                count += temp.first * temp.second * res.second;
                stk.push(make_pair(temp.first,res.second));//更新栈中的值
            }
        }else if(isupper(str[i])){ //如果是矩阵的话
            if(stk.empty()){ //stk为空，进入到stk中
                stk.push(matrix[str[i]]);
            }else{ //如果栈不为空，需要计算
                pair<int, int> temp = stk.top();
                stk.pop();
                count += temp.first * temp.second * matrix[str[i]].second;
                stk.push(make_pair(temp.first,matrix[str[i]].second));//更新栈中的值
            }
        }
    }
    return stk.top(); //遍历一遍结束，返回当前计算的矩阵大小
}

int main(){
    int n;
    while(cin >> n){
        count = 0;
        string rule;
        char ch = 'A';
        for(int i = 0; i < n; i++){ //输入n个矩阵的行列数
            cin >> matrix[ch].first >> matrix[ch].second;
            ch++;
        }
        cin >> rule;  //输入运算法则
        stack<char> s; //记录代表矩阵的字符
        compute(rule);
        cout << count << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，n为矩阵个数，从遍历一遍所有矩阵进行计算。
空间复杂度： $O (n)$ ，最坏情况下，每一步计算都需要递归，递归栈大小为n。

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

题目的主要信息：

方法一：

方法二：