[exercise-3] (UVA 442) matrix chain multiplication

Translate directly ：

Input n Dimensions of matrices and expressions of matrix chain multiplication , Output the number of multiplications . If multiplication doesn't work , The output error. Jiading A yes mn Matrix ,B yes np Matrix , that AB yes mp Matrix , The number of multiplications is mn*p. If A The number of columns is not equal to B The number of rows , Then multiplication cannot be performed .
for example ,A yes 50 * 10 Of ,B yes 10 * 20 Of ,C yes 20 * 5 Of , be (A(BC)) Is multiplied by 10 * 20 * 5（BC The number of multiplications ） + 50 *10 * 5((A(BC)) The number of multiplications ) = 3500.

Simple expression parsing can be done by stack .

AC Code ：

#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;
		
	}
}

Ideas ：
① Use a structure to store two values of each letter .
② Stack the structure
③ encounter ‘(’ Ignore , encounter ’)' Operate once when .
④ Content of operation ： Take out the first two elements of the stack for matrix chain multiplication （ Note that the first one is the back one ,AB Perform matrix chain multiplication , Stack pops up first B Pop up after A）, Put the newly obtained element on the stack .
⑤ If matrix chain multiplication cannot be performed, mark and exit .

I didn't understand at first , Want to put characters char Put it in the stack , But in this way Put the newly obtained elements on the stack It's very troublesome , If you put the structure directly into the stack, it can be easily implemented .
Here you can write a Constructors , Directly initialize the definition structure (C++ I learned it in school ）, In that case, you can define one less tmp Structure .