Resolução de problemas/Matrix chain multiplication

Tratamento de Expressões

O problema 442 (Matrix Chain Multiplication) é um simples tratamento de multiplicação de matrizes obedecendo a uma gramática dada no problema.

A implementação abaixo é uma sugestão de implementação:

 /*Estrutura para armazenar a entrada com as matrizes*/
 typedef struct matrix_{<br>
 	int m;
 	int n;
 } matrix;
 bool erro;
 matrix m[27];
 /*Número de casos de teste*/
 int t;
 int nexp;
 /*Templates pra fazer o processamento das expressões*/
 list<matrix> l;
 stack<matrix> s;
 /*Função  principal que faz a leitura e impressão do resultado ótimo para a multiplicacao*/
 /*de matrizes dadas como entrada*/
 int main(){
 	char nm;
 	int valor;
 	cin>>t;
 	while(t>0){
 		cin>>nm;
 		cin>>m[nm-'A'].m>>m[nm-'A'].n;
 		//cout<<nm<<" "<<m[nm-'A'].m<<m[nm-'A'].n<<"\n";
 		t--;
 	}
 	getchar();
 	while(1){
 		nexp = 0;
 		erro = false;
 		valor = expcalc();
 		if(valor == -3)
 			break;
 		else if(erro){
 			cout<<"error\n";
 			while(!s.empty()) s.pop();
 			l.clear();
 		}else{
 			cout << valor << "\n";
 		}
 	}
 	return 0;
 } 
 /* Função responsável pela leitura e armazenamento na lista l da expressão*/
 /* Esta função recursiva vai fazer operações de inserção e retirada de matrizes entre/*
 /* a lista e a pilha de tal forma que as matrizes aninhadas mais internas tenham maior*/
 /* precedência em relação as mais externas*/
 int expcalc(){
 	char c;
 	matrix a;
 	int valor;
 	c = getchar();
  	if(c == '\n' && erro)
 		return -1;
 	/*Ao encontrar um (, Algarismo alfanumérico, os valores são inseridos na lista*/
 	if(c == EOF)
 		return -3;
  	if(c == '('){
 		//cout<<"(\n";
 		a.m = -2;
 		a.n = -2;
 		l.push_back(a);
 		return expcalc();
 	/*Ao encontrar um ), os valores sao retirados da lista e inseridos na pilha*/
        /*até encontrar um ( ou a lista ficar vazia*/
 	/*Após é chamada a função para calcular o valor ótimo da subexpressão na pilha*/
 	/*Os valores ótimos das subexpressões são somados e retornados pela função expcalc */ 
 	}else if(c == ')'){
 		//cout<<")\n";
 		a = l.back();
 		while(a.m != -2 && a.n != -2){
 			s.push(a);
 			l.pop_back();
 			a = l.back();
 		}
 		l.pop_back();
 		valor = des1();
 		if(valor == -1)
 			return expcalc();
 		l.push_back(s.top());
 		s.pop();
 		//cout<<valor<<"\n";
 		return valor + expcalc();
 	}else if(c >= 'A' && c <= 'Z'){
 		nexp++;
 		l.push_back(m[c-'A']);
 		//cout<<c<<"\n";
 		return expcalc();
 	}
 	if(nexp == 1){
 		l.pop_front();
 		return 0;
 	}else{
 		valor = des();
 		if(erro)
 			return -1;
 		return valor;
 	}
 	
 } 
 /*des e des1 implementão as funções que multiplicão as subexpressões de entrada, a */
 /*diferença está que des1 utiliza os valores armazenados na pilha enquanto que des os da */
 /*lista*/<br>
 int des1(){
 	matrix a, b, c;
 	int valor;
 	a = s.top();
 	s.pop();
 	if(s.empty()){
 		s.push(a);
 		return 0;
 	}
  	b = s.top();
 	s.pop();
  	if(s.empty()){
 		/*cout<<"OK 1\n";
 		cout<<a.m<<" "<<a.n<<" "<<b.m<<" "<<b.n  <<"\n";*/
 		if(a.n != b.m){
 			erro = true;
 			return -1;
 		}
 		c.m = a.m;
 		c.n = b.n;
 		s.push(c);
 		return a.m*a.n*b.n;
 	}else{
 		if(a.n != b.m){
 			erro = true;
 			return -1;
 		}
 		c.m = a.m;
 		c.n = b.n;
 		s.push(c);
 		valor = a.m*a.n*b.n;
 		return valor + des1();
 	}
  } 
 
 int des(){
 	matrix a, b, c;
 	int valor;
  	a = l.front();
 	l.pop_front();
  	if(l.empty())
 		return 0;
 	b = l.front();
 	l.pop_front();
 	if(l.empty()){
 		/*cout<<"OK\n";*/
 		//cout<<a.m<<" "<<a.n<<" "<<b.m<<" "<< b.n <<"\n";
 		if(a.n != b.m){
 			erro = true;
 			return -1;
 		}
 		return a.m*a.n*b.n;
 	}else{
 		if(a.n != b.m){
 			erro = true;
 			return -1;
 		}
 		c.m = a.m;
 		c.n = b.n;
 		l.push_front(c);
 		valor = a.m*a.n*b.n;
 		return valor + des();
 	}
 }

---

Veja esse problema em: [1]