UVa442 - Matrix Chain Multiplication

题目地址：点击打开链接

C++代码：

#include <iostream>
#include <stack>
#include <string>
using namespace std;
const int maxsize = 100;
int main()
{
	int mat[maxsize][2];
	int n,i,a,b;
	string s;
	cin>>n;
	for(i=0;i<n;++i)
	{
		cin>>s>>a>>b;
		mat[s[0]-‘A‘][0]=a;
		mat[s[0]-‘A‘][1]=b;
	}
	cin.get();
	while(getline(cin,s))
	{
		stack<int> shu;
		stack<char> fu;
		int ans=0;
		int size=s.size();
		for(i=0;i<size;++i)
		{
			if(s[i]==‘(‘)
				fu.push(s[i]);
			else
			{
				if(s[i]!=‘)‘)
					shu.push(s[i]-‘A‘);
				else
				{
					b=shu.top();
					shu.pop();
					a=shu.top();
					shu.pop();
					fu.pop();
					if(mat[a][1]!=mat[b][0])
						break;
					ans+=mat[a][0]*mat[a][1]*mat[b][1];
					mat[n][0]=mat[a][0];
					mat[n][1]=mat[b][1];
					shu.push(n++);
				}
			}
		}
		if(i<size)
			cout<<"error"<<endl;
		else
			cout<<ans<<endl;
	}
	return 0;
}

UVa442 - Matrix Chain Multiplication,布布扣,bubuko.com

UVa442 - Matrix Chain Multiplication

原文：http://blog.csdn.net/leizh007/article/details/19931083