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

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

//矩阵乘法计算量估算
class EstimaMatrixMulti {
  private:
    //矩阵数量
    int n;

    //每个矩阵的行数和列数
    vector<pair<int, int>> vpii;
    stack<pair<int, int>> spii;

    //计算法则（算式）
    string rules;
    stack<char> sc;

  public:
    //构造函数
    EstimaMatrixMulti(const int n);

    //析构函数
    ~EstimaMatrixMulti();

    //估算计算量
    const int EstimatCalcQuant(void);
};

EstimaMatrixMulti::EstimaMatrixMulti(const int n) {
    this->n = n;
    this->vpii.clear();
    pair<int, int> pii;
    for (int i = 0; i < n; i++) {
        cin >> pii.first >> pii.second;
        this->vpii.push_back(pii);
    }

    //清空栈
    while (!this->spii.empty()) {
        this->spii.pop();
    }

    cin >> this->rules;
    while (!this->sc.empty()) {
        this->sc.pop();
    }
    return;
}

EstimaMatrixMulti::~EstimaMatrixMulti() {
}

const int EstimaMatrixMulti::EstimatCalcQuant(void) {
    //计算量
    int CalcQuant = 0;
    //数组下标
    int j = 0;

    //根据计算规则进行估算
    for (int i = 0; i < this->rules.size(); i++) {
        //如果遇到括号，不进行计算，直接入符号栈
        if (this->rules[i] == '(') {
            this->sc.push(this->rules[i]);
            continue;
        }
        // 如果遇到代表矩阵的大写字母，查看符号栈顶
        // 如果符号栈顶也是矩阵，进行一次计算，更新计算量和数组下标并将数据栈顶改为结果矩阵
        // 否则入栈，更新数组下标
        if (('A' <= this->rules[i]) && (this->rules[i] <= 'Z')) {
            //先判断栈是否为空，避免取栈顶出错
            if ((this->sc.empty()) || (this->sc.top() == '(')) {
                this->sc.push(this->rules[i]);
                this->spii.push(this->vpii[j]);
                j++;
                continue;
            }
            if (('A' <= this->sc.top()) && (this->sc.top() <= 'Z')) {
                CalcQuant += this->spii.top().first * this->vpii[j].second *
                             this->spii.top().second;
                this->spii.top().second = this->vpii[j].second;
                j++;
                continue;
            }
        }
        // 如果遇到右括号，符号栈出栈两次，得到矩阵，判断符号栈顶
        // 如果是矩阵，数据栈也出栈，将得到的数据与新栈顶进行计算，更新计算量并将数据栈顶改为结果矩阵
        // 否则将得到的矩阵符号入栈
        if (this->rules[i] == ')') {
            char ch = this->sc.top();
            this->sc.pop();
            this->sc.pop();
            if ((this->sc.empty()) || (this->sc.top() == '(')) {
                this->sc.push(ch);
                continue;
            }
            if (('A' <= this->sc.top()) && (this->sc.top() <= 'Z')) {
                pair<int, int> pii(this->spii.top());
                this->spii.pop();
                CalcQuant += this->spii.top().first * pii.second * pii.first;
                this->spii.top().second = pii.second;
                continue;
            }
        }
    }
    return CalcQuant;
}

int main() {
    int a;
    while (cin >> a) { // 注意 while 处理多个 case
        cout << EstimaMatrixMulti(a).EstimatCalcQuant() << endl;
    }
}
// 64 位输出请用 printf("%lld")