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]