問題:
輸入n個矩陣的維度和一些矩陣鏈乘表達式,輸出乘法的次數.如果無法進行,輸出error.如果A是m*n矩陣,B是n*p的矩陣,乘法次數為m*n*p 如果A的列數不等于B的行數,則乘法無法進行.
A 50*10
B 10*20
C 20*5
（A(BC))乘法次數：10*20*5(BC乘法次數)+50*10*5(A(BC)的乘法次數)

樣例輸入：

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

分析與解答：
stack先進后出，如果加一個終止條件，可以控制輸出時機
剛好這個是兩個數捆在一起了，那么只要找到終止條件就可以得到一個數，而不用考慮最先進棧的是個什么數

1.遇見字母進棧,遇見右括號出棧
2.出棧后棧頂的數是m2棧頂下面那個數m1
通過判斷，m2.a和m1.b，看是否能乘
3.成之后形成一個新矩陣m1.a，m2.b，push到stack里
4.注釋：結構數組只不過類似int[a]的作用,只是輸入到stack里的一個跳板，真正存東西的是stack

#include<cstdio> #include<stack> #include<iostream> #include<string> 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();//注意這里m2是頂端 matrix m1=s.top(); s.pop();if(m1.b != m2.a){//m2.a和m1.b 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; }

總結

以上是生活随笔為你收集整理的(stack 解析表达式)矩阵链乘的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。