紫书P141
输入n个矩阵的维度和一些矩阵链乘表达式，输出乘法的次数。如果乘法无法进行，输出error。假定A是mn矩阵，B是np矩阵，那么AB是mp矩阵，乘法次数为mn*p。若果A列数不等于B行数，则乘法无法进行。
输出乘法次数或error。
示例： 输入 9 A 50 10 B 10 20 C 20 5 D 30 35 E 35 15 F 15 5 G 5 10 H 10 20 I 20 25 A B C (AA) (AB) (AC) (A(BC)) ((AB)C) (((((DE)F)G)H)I) (D(E(F(G(HI))))) ((D(EF))((GH)I)) 输出 0 0 0 error 10000 error 3500 15000 40500 47500 15125 不管左括号，读入矩阵链乘表达式，碰到右括号就计算一次，出错返回错误，否则生成一个新的矩阵继续计算。
#include <iostream> #include <cstdio> #include <string> #include <stack> using namespace std; struct Matrix{ int a,b; Matrix(int a=0,int b=0):a(a),b(b){} }m[26]; stack<Matrix> s; int main() { int n; cin >> n; for(int i=0;i<n;i++){ string name; cin >> name; int k = name[0] - 'A'; cin >> m[k].a >> m[k].b; } string expr; while(cin>>expr){ int len = expr.length(); bool error = false; int ans = 0; for(int i=0;i<len;i++){ if(isalpha(expr[i])) s.push(m[expr[i]-'A']); else if(expr[i]==')'){ Matrix m2 = s.top(); s.pop(); Matrix m1 = s.top(); s.pop();//1是先入栈的 if(m1.b!=m2.a) {error = true;break;} ans += m1.a*m1.b*m2.b; s.push(Matrix(m1.a,m2.b)); //新矩阵入栈 } } if(error) printf("error\n"); else printf("%d\n",ans); } return 0; }