题解 | #矩阵乘法计算量估算#
矩阵乘法计算量估算
https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
//用栈做吧
//遍历一遍输入的字符串就行，如果是'('入栈
//如果是字母就检测栈顶，如果栈顶是数字就做一次矩阵计算，栈顶是'('就入栈
//如果是')'，弹出字母和'('，并检测栈顶，栈顶是数字就需要再做一次矩阵计算，栈顶是'('就入栈
#include <iostream>
#include <stack>
#include <vector>
#include <string>
using namespace std;
int main(){
int n;
cin >> n;
vector<vector<int>> vecinput(n,vector<int>(2,0));
for(int i = 0;i<n;++i){
cin >> vecinput[i][0] >> vecinput[i][1];
}
string inputstr;
cin >> inputstr;
stack<vector<int>> stmat;//矩阵栈
int sum = 0;
for(int i = 0;i<inputstr.size();++i){
if(inputstr[i] == '('){
stmat.push(vector<int>(1,0));
}
else if (inputstr[i] == ')'){
vector<int> tmp = stmat.top();
stmat.pop();
stmat.pop();
if(!stmat.empty()){
if(stmat.top().size() == 2){
vector<int> tmptop = stmat.top();
sum += tmptop[0]*tmptop[1]*tmp[1];
stmat.pop();
tmptop[1] = tmp[1];
stmat.push(tmptop);
}
else{
stmat.push(tmp);
}
}
else stmat.push(tmp);
}
else{
if(stmat.empty())stmat.push(vecinput[inputstr[i]-'A']);
else{
if(stmat.top().size() == 1){//栈顶是左括号
stmat.push(vecinput[inputstr[i]-'A']);
}
else{//栈顶有数字
vector<int> tmp = stmat.top();
sum += tmp[0]*tmp[1]*vecinput[inputstr[i]-'A'][1];
stmat.pop();
tmp[1] = vecinput[inputstr[i]-'A'][1];
stmat.push(tmp);
}
}
}
}
cout << sum << endl;
return 0;
}
