题意:
给出一个矩阵表达式,计算总的乘法次数。
分析:
基本的数学知识:一个m×n的矩阵A和n×s的矩阵B,计算AB的乘法次数为m×n×s。只有A的列数和B的行数相等时,两个矩阵才能进行乘法运算。
表达式的处理:可以用一个栈来存储,遇到字母入栈,遇到右括号将栈顶两个元素出栈,然后将乘积入栈。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxn = 30; 5 int n; 6 char s[100]; 7 8 struct Matrix 9 { 10 int n, m; 11 Matrix(int n=0, int m=0):n(n), m(m) {} 12 int times(const Matrix& rhs) const 13 { 14 if(m == rhs.n) return n * m * rhs.m; 15 return -1; 16 } 17 Matrix operator * (const Matrix& rhs) const 18 { return Matrix(n, rhs.m); } 19 }mat[maxn], stack[maxn]; 20 21 int ID(char c) { return c - 'A'; } 22 23 int main() 24 { 25 //freopen("in", "r", stdin); 26 scanf("%d", &n); 27 getchar(); 28 for(int i = 0; i < n; ++i) 29 { 30 int n, m; 31 char name; 32 scanf("%c %d %d", &name, &n, &m); 33 getchar(); 34 mat[ID(name)] = Matrix(n, m); 35 } 36 37 while(scanf("%s", s) == 1) 38 { 39 int l = strlen(s); 40 int ans = 0, p = 0, ok = 1; 41 for(int i = 0; i < l; ++i) 42 { 43 if(s[i] == '(') continue; 44 else if(s[i] == ')') 45 { 46 Matrix B = stack[--p]; 47 Matrix A = stack[--p]; 48 int t = A.times(B); 49 if(t != -1) 50 { 51 ans += t; 52 stack[p++] = A * B; 53 } 54 else { ok = 0; break; } 55 } 56 else 57 { 58 stack[p++] = mat[ID(s[i])]; 59 } 60 } 61 62 if(ok) printf("%d ", ans); 63 else puts("error"); 64 } 65 66 return 0; 67 }