题解 | #矩阵乘法计算量估算#
矩阵乘法计算量估算
https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
#include <cctype> #include <iostream> #include <stack> #include <vector> using namespace std; int main() { int n; cin >> n; vector<vector<int>> m(n, vector<int>(2, 0)); for (int i = 0; i != n; ++i) { cin >> m[i][0] >> m[i][1]; } string op; cin >> op; stack<vector<int>> t; stack<char> p; long result = 0; for (int i = 0; i != op.size(); ++i) { if (op[i] == '(') p.push(op[i]); else if (isalpha(op[i])) { vector<int> k = { m[static_cast<int>(op[i] - 'A')][0], m[static_cast<int>(op[i] - 'A')][1] }; t.push(k); if (isalpha(op[i + 1]) || op[i + 1] == '(') p.push('*'); } else if (op[i] == ')') { while (!p.empty() && p.top() != '(') { vector<int> k = t.top(); t.pop(); vector<int> k2 = t.top(); t.pop(); result += k2[0] * k2[1] * k[1]; p.pop(); vector<int> new_v = { k2[0], k[1] }; t.push(new_v); } if (!p.empty()) { p.pop(); if (i < op.size() - 1 && (isalpha(op[i + 1]) || op[i + 1] == '(')) p.push('*'); } } } cout << result; }
依然使用双栈法,先进先出,遇到括号就开始往外弹出