题目描述
思路:首先要明白以下几点:
什么是矩阵乘法?(大概学过线代的都知道)
什么矩阵不可乘? A a*b B c*d 当 b = c时,两个矩阵可以相乘,同时结果为 C a*d
矩阵乘法的次数如何计算: 可以相乘的情况下 次数 = a*b*d (a*c*d也行) 这可以自己推推.
思路:栈的使用 由于矩阵由三部分组成:名字,行数,列数,所以可以搞一个结构体,通过结构体数组把矩阵名和下标索引进行关联起来.在进行次数计算时,对每个字符进行判断,如果是字母就将其压入栈中;如果是)则弹出两个元素,如果可以运算则计算,不能则结束该字符串的判断并输出error,进行下一个.
当然也可以使用map做,让map的键为矩阵名,值为矩阵结构体.
注意:在从栈中弹出矩阵进行运算时,先弹出的在运算时要放在前面,因为栈的那先进后出的特性.
参考代码
#include<bits/stdc++.h> using namespace std; int n,cnt = 0; struct Matrix { int x; int y; Matrix(int a = 0, int b = 0) :x(a), y(b) {};//构造方法进行初始化 }arr[26]; char ch; string str; bool flag; int main() { cin >> n; while (n--) { cin >> ch; cin >> arr[ch - 'A'].x >> arr[ch - 'A'].y; } while (cin >> str) { stack<Matrix> s;//栈存放的数据可以是索引,也可以是Matrix,但如果存放索引,后期当像栈中存放一个矩阵时还得进行查询,找出对应的索引.有点麻烦. cnt = 0; flag = true; for (int i = 0; i < str.length(); i++) { if (isalpha(str[i])) {//判断是否是字母 s.push(arr[str[i] - 'A']); } else if (str[i] == ')') {//如果是)则出栈两个进行矩阵运算. Matrix m2 = s.top(); s.pop();//栈具有先进后出的特性,所以先出来的一定排在后面(在运算时). Matrix m1 = s.top(); s.pop(); if (m1.y != m2.x) {//无法运算则结束. flag = false; break; } else {//如果可以运算 s.push(Matrix(m1.x, m2.y));//将新的矩阵放入栈中. cnt += m1.x * m1.y * m2.y;//计算乘法的次数 } } } if (!flag) { cout << "error" << endl; } else { cout << cnt << endl; } } return 0; }
