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

其实这道题抽象一下，我们可以发现它其实就是表达式求值，唯一的问题就是矩阵乘法需要自己定义，还有一个问题就是让输入的字符串和具体的数据如何对应，看代码。

这道题它说的很简单就是总是会有括号，你可以通过括号来判断是否要乘，但下面这个更普适，只要矩阵能够相乘，他可以按乘法结合律从左至右，不需要括号。

这道题的思路就是在矩阵相乘的中间想象有一个乘号

#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

int compute(stack<pair<int, int>>& sp) {//矩阵乘法的计算
    pair<int, int> a, b;
    b = sp.top();
    sp.pop();
    a = sp.top();
    sp.pop();
    int first, second, sum;
    first = a.first;
    second = b.second;
    sum = first * second * a.second;
    sp.push(make_pair(first, second));//最后还要把计算的中间矩阵压入栈
    return sum;

}

bool priority(const char& a, const char& b) {//这里优先级只有括号和乘号
    if (a == '(')return false;
    else return true;
}

int main() {
    int n;
    vector<pair<int, int>> vp;
    while (cin >> n) {
        int row, col;
        for (int i = 0; i < n; i++) {
            cin >> row;
            cin >> col;
            vp.push_back(make_pair(row, col));//放入矩阵数据
        }
        int sum = 0;
        string str;
        cin >> str;
        int N = str.size();
        int cnt = 0;//这里用来遇到字母对应vp的pair
        stack<char> sc;
        stack<pair<int, int>> sp;
        bool flag = false;//判断是否是乘号
        for (int i = 0; i < N; i++) {
            if (str[i] == '(') {
                if (flag) {//代表应该遇到乘号，但是遇到了括号，像这种情况"AB(CD)"
                //B后面那有一个乘号但是遍历的时候是括号，这时要把前面的先计算出来
                    while (priority(sc.top(), '*')) {把前面的结果计算出来
                        sum += compute(sp);
                        sc.pop();
                    }
                    sc.push('*');//把B后面的乘号放进运算符栈
                    flag = false;//下一次应该遇到字母了
                }
                sc.push(str[i]);//括号也放进去
            }
            else if (str[i] == ')') {//遇到反括号应该把里面全部计算出来
                while (sc.top() != '(') {
                    sum += compute(sp);
                    sc.pop();
                }
                sc.pop();//弹出正括号
                flag = true;//反括号后面应该接乘号，但遍历的时候可能是反括号或者
                //字母
            }
            else if (flag) {//这个时候遍历的时候应该是字母但是要加上乘号，像前面
            //那个例子一样遍历到B的时候应该需要加上乘号
                while (priority(sc.top(), '*')) {//如果栈内有比较大的应该先把里
                //面计算出来，像这样"ABC"遇到C的时候要把AB计算出来。
                    sum += compute(sp);
                    sc.pop();
                }
                sc.push('*');//放入乘号
                sp.push(vp[cnt++]);//放入现在遍历字母对应的矩阵数据
                flag = true;//下一个还应该是符号
            }//else if
            else {
                sp.push(vp[cnt++]);//放入第一个数据像没有括号的这种"ABC"
                flag = true;
            }
        }
        cout << sum << endl;
    }//while
}