# UVa 442 - Matrix Chain Multiplication

---
# 題目大意
給許多由A~Z表示的矩陣，接下來有許多矩陣乘法算式，任兩個矩陣的乘法皆由括號包住，接著對每個算式輸出總共需要做幾次乘法運算。

---
# 題解
a*b的矩陣乘以c*d的矩陣需要 a*b*d 次運算，而需要b=c才能相乘。由於任兩個乘法皆由括號包住，所以只需要管 ) ，碰到 ) 就把stack最上面兩個矩陣做運算再把結果扔回去就好。最後看stack中是否只有一個元素及是否出現不能相乘的情況。

---

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define ft first
#define sec second
#define pr pair<int,int>
#define ISCC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int n ,m ,a ,b ,sum ,ok;
string s;
char c;
int main() 
{	
	ISCC;
	while(cin >> n)
	{
		pr M[30];
		map<char ,int> mp;
		for(int i=1 ;i<=n ;i++)
		{
			cin >> c; mp[c] = i;
			cin >> M[i].ft >> M[i].sec;
		}
		getline(cin ,s);
		while(getline(cin ,s))
		{
			sum = ok =  0;
			stack<pr> stk;
			pr a ,b;
			for(int i=0 ;i<s.size() ;i++) if(s[i] != '(')
			{
				if(s[i]==')')
				{
					if(stk.size()>1)
					{
						a = stk.top(); stk.pop();
						b = stk.top(); stk.pop();
						if(a.ft == b.sec) //因為是stack，這裡是b*a
						{
							sum += b.ft * b.sec * a.sec;
							stk.push({b.ft ,a.sec});
						}
						else{ok = 1; break;}
					}
				}
				else stk.push({M[mp[s[i]]].ft ,M[mp[s[i]]].sec});
			}
			if(stk.size() == 1 && !ok) cout << sum << '\n';
			else cout << "error\n"; 
		}
	}
	return 0;	
}