【练习-3】（Uva 442）Matrix Chain Multiplication(矩阵链乘）

直接翻译：

输入n个矩阵的维度和一些矩阵链乘的表达式，输出乘法的次数。如果乘法无法进行，则输出error。嘉定A是mn的矩阵，B是np的矩阵，那么AB是mp的矩阵，乘法次数为mn*p。如果A的列数不等于B的行数，则乘法无法进行。
例如，A是50 * 10的，B是10 * 20的，C是20 * 5的，则(A(BC))的乘法次数为10 * 20 * 5（BC的乘法次数） + 50 *10 * 5((A(BC))的乘法次数) = 3500.

简单的表达式解析可以借助栈来完成。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
struct node{
    
	int x;
	int y;
}a[26];
int main()
{
    
	int n;
	char ch;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
    
		cin>>ch;
		cin>>a[ch-'A'].x;
		cin>>a[ch-'A'].y;
	}
	string s;
	while(cin>>s)
	{
    
		stack<node> st;
		int f=1,ans=0;
		int len = s.size();
		if(len == 0 )
		{
    
			cout<<0<<endl;
			continue;
		}
		for(int i=0;i<len;i++)
		{
    
			if(s[i]>='A' && s[i]<='Z')
				st.push(a[s[i]-'A']);
			else if(s[i]==')')
			{
    
				node x2 = st.top();st.pop();
				node x1 = st.top();st.pop();
				if(x1.y != x2.x){
    
					f = 0;
					break;
				}
				ans+=x1.x*x1.y*x2.y;
				node tmp;
				tmp.x=x1.x,tmp.y=x2.y;
				st.push(tmp);
			}
		}
		if(f)
			cout<<ans<<endl;
		else
			cout<<"error"<<endl;
		
	}
}

思路：
①用结构体存放每个字母的两个值。
②用栈来存放结构体
③遇到‘(’时忽略，遇到’)'时进行一次操作。
④操作的内容：把栈的前两个元素拿出来进行矩阵链乘（注意先拿出来的是后面的，AB进行矩阵链乘，栈首先弹出B后弹出A），把新得到的元素放进栈。
⑤如果不能进行矩阵链乘则标记并退出。

一开始没想明白，想要把字符char放进栈里，但是这样的话实现 把新得到的元素进栈 是挺麻烦的，如果是直接放进把结构体放进栈里就可以很容易的实现了。
在这里可以在结构体中写一个构造函数，直接初始化定义结构体(C++里学过），那样的话可以少定义一个tmp结构体。