UVa 442 - Matrix Chain Multiplication

题目：给你一些矩阵，以及一些矩阵间的乘法运算（包含括号），判断计算是否合法，合法输出结果。

分析：模拟，递归。见到括号直接递归调用，每次判断乘法左边的行是否等于右边的列即可。

说明：注意cin的读数据的情况，会RE，（zoj1094）。

#include <iostream>
#include <cstring>

using namespace std;

struct node
{
	int 		L,R;
	long long	V;
}Matrix[ 27 ],Error;

bool Flag;

node Calculate( char* Data, int s, int e )
{
	int  count = 0;
	node Save[ 2 ];
	for ( int i = s ; i <= e ; ++ i )
		if ( Data[ i ] == '(' ) {
			int start = i + 1;
			int untop = 1;
			while ( untop && ++ i ) {
				if ( Data[ i ] == '(' ) ++ untop;
				if ( Data[ i ] == ')' ) -- untop;
			}
			Save[ count ++ ] = Calculate( Data, start, i-1 );
			if ( Flag ) return Error;
		}else 
			Save[ count ++ ] = Matrix[ Data[ i ]-'A' ];
			
	node Now = Save[ 0 ];
	for ( int i = 1 ; i < count ; ++ i ) {
		if ( Now.R != Save[ i ].L ) {
			Flag = true;
			return Error;
		}
		Now.V = Now.V + Save[ i ].V + Now.L*Now.R*Save[ i ].R;
		Now.R = Save[ i ].R;
	}
	return Now;
}

char Data[ 260 ];

int main()
{
	int  n;
	char C;
	cin >> n;
	for ( int i = 0 ; i < n ; ++ i ) {
		cin >> C; //从后向前运算的，写在一起就 RE 了。。。 
		cin >> Matrix[ C-'A' ].L >> Matrix[ C-'A' ].R;
		Matrix[ C-'A' ].V = 0LL;
	}
	while ( cin >> Data ) {
		Flag = false;
		node Answer = Calculate( Data, 0, strlen( Data )-1 );
		if ( Flag )
			cout << "error" << endl;
		else 
			cout << Answer.V << endl;
	}
	return 0;
}

UVa 442 - Matrix Chain Multiplication

原文：http://blog.csdn.net/mobius_strip/article/details/44569029