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

利用栈进行计算，先将矩阵入栈，遇到右括号时出栈两个矩阵，计算乘法次数，然后将两个矩阵相乘得到的矩阵入栈。

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

string cal_multime(string &m1, string &m2, int &times) {
    int m1_row, m1_col, m2_col;
    stringstream ss(m1);
    ss >> m1_row >> m1_col;
    ss.clear();
    ss.str(m2);
    ss >> m1_col >> m2_col;
    times = m1_row * m1_col * m2_col;
    ss.clear();
    ss.str("");
    ss << m1_row << ' ' << m2_col;
    return ss.str();
}

int pop_and_cal(vector<string> &values) {
    string m1, m2, m3;
    int ret;
    m2 = values.back();
    values.pop_back();
    m1 = values.back();
    values.pop_back();
    m3 = cal_multime(m1, m2, ret);
    values.push_back(m3);
    return ret;
}

int solve(vector<string> &inputs, string &rules) {
    vector<string> values;
    int result = 0;
    int i=0;

    for(char c : rules) {
        if (c == ')') {
            result += pop_and_cal(values);
        } else if (c >= 'A' && c <= 'Z') {
            values.push_back(inputs[i]);
            i++;
        }
    }
    while(values.size() > 1) result += pop_and_cal(values);
    return result;
}

int main() {
    int total;

    while(cin >> total) {
        vector<string> inputs;
        string ops;
        string line;
        getchar();
        for(int i=0; i<total; i++) {
            getline(cin, line);
            inputs.push_back(line);
        }
        getline(cin, ops);
        cout << solve(inputs, ops) << endl;
    }
    return 0;
}