Conversão de uma expressão de infxa para posfixa

adiniz · Novembro 23, 2007, 9:49am

Olá Galera,
Sou novo aqui no forum e qualquer coisa que eu fiz errado me avisem, por favor.

Sou iniciante em programação!

Então…
Eu estou tentando fazer um programinha que converta uma expressão da forma infixa para forma posfixa. Eu fiz uma parte(acho que da forma errada) que está funcionando com as expressões que coloquei manualmente, mas se a expressão é alterada ele converte errado.
Gostaria de saber se alguém pode me explicar como fazer ou mostrar um algoritmo de algum que esteja funcionando.

Segue abaixo o que fiz a té agora.

Desde já agradeço a colaboração galera.

[code]public class InfPos{
public static void main(String [] args){
Pilha pilhaI=new Pilha();
Pilha pilhaT=new Pilha();
Pilha pilhaP=new Pilha();
Pilha pilhaPrint=new Pilha();
int cont=0, cont2=0;
char tmp=’ ‘;
//Insere a expressão de forma infixa na pilhaI
// A+BC-D+E/F
// ABC+D-EF/+
System.out.println(“Infixa: A+BC-D+E/F");
System.out.println("Posfixa: ABC+D-EF/+”);
System.out.print("Programa: ");
pilhaI.push(‘F’);
pilhaI.push(’/’);
pilhaI.push(‘E’);
pilhaI.push(’+’);
pilhaI.push(‘D’);
pilhaI.push(’-’);
pilhaI.push(‘C’);
pilhaI.push(’’);
pilhaI.push(‘B’);
pilhaI.push(’+’);
pilhaI.push(‘A’);
// (A+B)(C/D)-(E+F)
// AB+CD/EF±
/ System.out.println(“Infixa: (A+B)*(C/D)-(E+F)”);

  System.out.println("Correto:  AB+CD/*EF+-");

```
  System.out.print("Programa: ");
```
```
  pilhaI.push(')');
```
```
  pilhaI.push('F');
```
```
  pilhaI.push('+');
```
```
  pilhaI.push('E');
```
```
  pilhaI.push('(');
```
```
  pilhaI.push('-');		
```
```
  pilhaI.push(')');
```
```
  pilhaI.push('D');
```
```
  pilhaI.push('/');
```
```
  pilhaI.push('C');
```
```
  pilhaI.push('(');
```
```
  pilhaI.push('*');
```
```
  pilhaI.push(')');
```
```
  pilhaI.push('B');
```
```
  pilhaI.push('+');
```
```
  pilhaI.push('A');
```
```
  pilhaI.push('(');*/
```
```
  //	(A+B)*((C/D)-(E+F))
```
```
  //	AB+CD/EF+-*
```

/* System.out.println(“Infixa: (A+B)*((C/D)-(E+F))”);

  System.out.println("Correto:  AB+CD/EF+-*");

```
  System.out.print("Programa: ");
```
```
  pilhaI.push(')');
```
```
  pilhaI.push(')');
```
```
  pilhaI.push('F');
```
```
  pilhaI.push('+');
```
```
  pilhaI.push('E');
```
```
  pilhaI.push('(');
```
```
  pilhaI.push('-');
```
```
  pilhaI.push(')');
```
```
  pilhaI.push('D');
```
```
  pilhaI.push('/');
```
```
  pilhaI.push('C');
```
```
  pilhaI.push('(');
```
```
  pilhaI.push('(');
```
```
  pilhaI.push('*');
```
```
  pilhaI.push(')');
```
```
  pilhaI.push('B');
```
```
  pilhaI.push('+');
```
```
  pilhaI.push('A');
```

  pilhaI.push('(');*/
  
  //Transforma a expressão de infixa para posfixa
  while(!(pilhaI.isEmpty())){
  	char aux=pilhaI.pop();
  	switch(aux){
  		case '(':{
  			pilhaT.push(aux);
  		}
  		break;
  		case ')':{
  			//Enquanto naum encontrar "(" transfere os operadores da pilhaT para pilhaP
  			//Quando encontrar ele para
  			tmp=pilhaT.pop();
  			while(tmp!='('){
  				pilhaP.push(tmp);
  				tmp=pilhaT.pop();
  				break;	
  			}
  		}
  		break;
  		case '+':{
  			//Ele verifica se na pilhaT tem algum operador "*" ou "/"
  			//Se tiver, ele tira da pilhaT e coloca na pilhaP e depois empilha o "+" na pilhaT
  			//Se naum tiver ele apenas empilha o "+" na pilhaT
  			if(!(pilhaT.isEmpty())){
  				tmp=pilhaT.pop();
  				if(tmp=='('){
  					pilhaT.push(tmp);
  					pilhaT.push(aux);
  				}
  				else{
  					if((tmp=='*')||(tmp=='/')){
  						pilhaP.push(tmp);
  						tmp=pilhaT.pop();
  						while((tmp!='*')||(tmp!='/')){
  							pilhaP.push(tmp);
  							tmp=pilhaT.pop();
  							break;
  						}
  						pilhaT.push(tmp);
  						pilhaT.push(aux);
  					}
  					else{
  						if((tmp=='+')||(tmp=='-')){
  							pilhaP.push(tmp);
  							pilhaT.push(aux);
  						}
  					}
  				}
  				
  			}
  			else{
  				pilhaT.push(aux);
  			}
  		}
  		break;
  		case '-':{
  			//Ele verifica se na pilhaT tem algum operador "*" ou "/"
  			//Se tiver, ele tira da pilhaT e coloca na pilhaP e depois empilha o "-" na pilhaT
  			//Se naum tiver ele apenas empilha o "-" na pilhaT
  			if(!(pilhaT.isEmpty())){
  				tmp=pilhaT.pop();
  				if(tmp=='('){
  					pilhaT.push(tmp);
  					pilhaT.push(aux);
  				}
  				else{
  					if((tmp=='*')||(tmp=='/')){
  						pilhaP.push(tmp);
  						tmp=pilhaT.pop();
  						while((tmp!='*')||(tmp!='/')){
  							pilhaP.push(tmp);
  							tmp=pilhaT.pop();
  							break;
  						}
  						pilhaT.push(tmp);
  						pilhaT.push(aux);
  					}
  					else{
  						if((tmp=='+')||(tmp=='-')){
  							pilhaP.push(tmp);
  							pilhaT.push(aux);
  						}
  					}
  				}
  				
  			}
  			else{
  				pilhaT.push(aux);
  			}
  		}
  		break;
  		case '*':{
  			//Apenas empilha o "*" na pilhaT
  			pilhaT.push(aux);
  		}
  		break;
  		case '/':{
  			//Apenas empilha o "/" na pilhaT
  			pilhaT.push(aux);
  		}
  		break;
  		default :{
  			//Empilha na pilhaP a letra encontrada na pilhaI
  			pilhaP.push(aux);
  		}
  		break;				
  	}
  }
  //Transfere o que sobrou na pilhaT para pilhaP
  if(pilhaI.isEmpty()){
  	while(!(pilhaT.isEmpty())){
  		tmp=pilhaT.pop();
  		if((tmp=='(')||(tmp=='0')){
  			
  		}
  		else{
  			pilhaP.push(tmp);
  		}		
  	}
  }
  //Inverte os valores da pilha
  while(!(pilhaP.isEmpty())){
  	pilhaPrint.push(pilhaP.pop());
  }
  //Imprime a expressão de forma Pósfixa
  while(!(pilhaPrint.isEmpty())){
  	char auxPrint=pilhaPrint.pop();
  	if(auxPrint=='0'){
  			
  	}
  	else{
  		System.out.print(auxPrint);
  	}
  }

}
}[/code]

peczenyj · Novembro 23, 2007, 10:18am

Amigo

Essa conversão não é trivial. Dependendo da procedencia dos operadores vc terá trabalho.

procurando no google eu encontrei este exemplo:

http://www.java2s.com/Code/JavaScript/Development/InfixtoPostfixConversion.htm

ok, é javascript mas… não custa nada dar uma olhada.

Aqui tem um artigo explicando bem (mas é C#)
http://www.microsoft.com/brasil/msdn/Tecnologias/vbnet/visualbasic_Stack.mspx

adiniz · Novembro 23, 2007, 11:16am

Valeu pela ajuda cara… vou tentar enteder o que vc me passou e ver se consigo concertar o meu cód.

Abração.

adiniz · Dezembro 11, 2007, 11:44am

Galera,

Consegui terminar o programinha para converssão de uma expressão infixa para posfixa a tempo.

quero agradecer a ajuda de vcs e em especial a do nosso amigo “peczenyj”. valeu cara.

e como agradecimento ao forum segue abaixo o programinha funcionando 100% e também a pilha.
se quizerem usar o código, fiquem a vontade, mas naum esqueçam de colocar meu nome como colaborador. rsrsrsrs

abraço a todos

“Esse é o código do programa”

[code]/*

Autor: Ademir Diniz
Data: 21/10/2007
Objetivo: Ler uma expressão de forma infixa e convertê-la para forma posfixa
*/

import java.util.Scanner;
import javax.swing.JOptionPane;
public class InfPos{
public static void main(String [] args){
// Declaracao e criacao das pilhas e variaveis
Scanner scan=new Scanner(System.in);
JOptionPane janela=new JOptionPane();
Pilha pilhaT=new Pilha();
Pilha pilhaP=new Pilha();
Pilha pilhaPrint=new Pilha();
String expr;
char tmp, auxPrint, aux, auxLimp;
int tamexpr=0, i=0, opc=0;

	while(opc!=2){
		
		//	Limpa as pilhas pilhaP, pilhaT e pilhaPrint
		while(!pilhaP.isEmpty()){
			auxLimp=pilhaP.pop();
		}
		while(!pilhaT.isEmpty()){
			auxLimp=pilhaT.pop();
		}
		while(!pilhaPrint.isEmpty()){
			auxLimp=pilhaPrint.pop();
		}
		i=0;
		tamexpr=0;
		
		//	Captura a expressao e o tamanho da expressao
		expr=JOptionPane.showInputDialog("CONVERTE UMA EXPRESSAO DA FORMA INFIXA PARA POSFIXA\n\nDigite a expressao de forma infixa");
		System.out.print("\n\n\t\tEXPRESSAO DE FORMA INFIXA: "+expr);
		tamexpr=expr.length();

		//	Le caractere por caractere e transforma a expressão para posfixa
		while(i<tamexpr){
			aux=expr.charAt(i);
			i=i+1;
			switch(aux){
				case '(':{
					pilhaT.push(aux);
				}
				break;
				case ')':{
					//	Enquanto naum encontrar "(" transfere os operadores da pilhaT para pilhaP
					//	Quando encontrar ele para
					tmp=pilhaT.pop();
					while(tmp!='('){
						aux=pilhaT.pop();
						if(aux=='('){
							pilhaP.push(tmp);
							break;
						}
						else{
							if(checaPrio(tmp)>=checaPrio(aux)){
								pilhaP.push(tmp);
								tmp=aux;
							}
							else{
								pilhaP.push(aux);
								tmp=pilhaT.pop();
							}
						}
					}
				}
				break;
				case '+':{
					if(!(pilhaT.isEmpty())){
						tmp=pilhaT.pop();
						if(checaPrio(tmp)>=checaPrio(aux)){
							pilhaP.push(tmp);
							while(!(pilhaT.isEmpty())){
								tmp=pilhaT.pop();
								if(checaPrio(aux)==checaPrio(tmp)){
									pilhaP.push(tmp);
									break;
								}
								else{
									pilhaT.push(tmp);
									break;
								}
							}
							pilhaT.push(aux);
						}
						else{
							pilhaT.push(tmp);
							pilhaT.push(aux);
						}
					}
					else{
						pilhaT.push(aux);
					}
				}
				break;
				case '-':{
					if(!(pilhaT.isEmpty())){
						tmp=pilhaT.pop();
						if(checaPrio(tmp)>=checaPrio(aux)){
							pilhaP.push(tmp);
							while(!(pilhaT.isEmpty())){
								tmp=pilhaT.pop();
								if(checaPrio(aux)==checaPrio(tmp)){
									pilhaP.push(tmp);
									break;
								}
								else{
									pilhaT.push(tmp);
									break;
								}
							}
							pilhaT.push(aux);
						}
						else{
							pilhaT.push(tmp);
							pilhaT.push(aux);
						}
					}
					else{
						pilhaT.push(aux);
					}
				}
				break;
				case '*':{
					if(!(pilhaT.isEmpty())){
						tmp=pilhaT.pop();
						if(checaPrio(tmp)>=checaPrio(aux)){
							pilhaP.push(tmp);
							while(!(pilhaT.isEmpty())){
								tmp=pilhaT.pop();
								if(checaPrio(aux)==checaPrio(tmp)){
									pilhaP.push(tmp);
									break;
								}
								else{
									pilhaT.push(tmp);
									break;
								}
							}
							pilhaT.push(aux);
						}
						else{
							pilhaT.push(tmp);
							pilhaT.push(aux);
						}
					}
					else{
						pilhaT.push(aux);
					}
				}
				break;
				case '/':{
					if(!(pilhaT.isEmpty())){
						tmp=pilhaT.pop();
						if(checaPrio(tmp)>=checaPrio(aux)){
							pilhaP.push(tmp);
							while(!(pilhaT.isEmpty())){
								tmp=pilhaT.pop();
								if(checaPrio(aux)==checaPrio(tmp)){
									pilhaP.push(tmp);
									break;
								}
								else{
									pilhaT.push(tmp);
									break;
								}
							}
							pilhaT.push(aux);
						}
						else{
							pilhaT.push(tmp);
							pilhaT.push(aux);
						}
					}
					else{
						pilhaT.push(aux);
					}
				}
				break;
				default :{
					//	Empilha na pilhaP a letra encontrada na pilhaI
					pilhaP.push(aux);
				}
				break;				
			}
		}
		//	Transfere o que sobrou na pilhaT para pilhaP
		while(!(pilhaT.isEmpty())){
			tmp=pilhaT.pop();
			if((tmp=='(')||(tmp=='0')){
				
			}
			else{
				pilhaP.push(tmp);
			}		
		}
		//	Inverte os valores da pilhaP para impressao
		while(!(pilhaP.isEmpty())){
			pilhaPrint.push(pilhaP.pop());
		}
		//	Imprime a expressão de forma Pósfixa
		System.out.print("\n\t\tEXPRESSAO DE FORMA POSFIXA: ");
		while(!(pilhaPrint.isEmpty())){
			auxPrint=pilhaPrint.pop();
			if(auxPrint=='0'){
					
			}
			else{
				System.out.print(auxPrint);
			}
		}
		System.out.print("\n\n");
		
		System.out.print("\n\t\tDESEJA CONVERTER OUTRA EXPRESSAO?");
		System.out.print("\n\t\t1-Sim\t2-Nao\n\t\tEscolha um das opcoes acima e precione enter: ");
		opc=scan.nextInt();
	}
}
//	Checa a prioridade do caracter
public static int checaPrio (char caracter){
	int prioridade=0;
	if(caracter=='('){
		prioridade=1;
	}
	else{
		if((caracter=='-')||(caracter=='+')){
			prioridade=2;
		}
		else{
			if((caracter=='*')||(caracter=='/')){
				prioridade=3;
			}
		}
	}
	return (prioridade);
}

}[/code]

"Esse é o código do estrutura utilizada (pilha)"

[code]public class Pilha {
public char [] vet = new char [30];
public int topo = 0;

public boolean push(char dado) {
	boolean res = false;
	
	if(!isFull()) {
		vet[topo] = dado;
		topo++;
		res = true;
	}
	return(res);
}

public char pop() {
	char res = '0';
	
	if(!isEmpty()) {
		topo--;
		res = vet[topo];
	}
	return(res);
}

public boolean isFull() {
	boolean res = (topo == vet.length) ? true : false;
	return(res);
}
	
public boolean isEmpty() {
	boolean res = (topo == 0) ? true : false;
	return(res);
}

}[/code]

system · Dezembro 23, 2015, 9:25pm

Conversão de uma expressão de infxa para posfixa

“Esse é o código do programa”

"Esse é o código do estrutura utilizada (pilha)"

Cursos de Mobile

Cursos de Programação

Cursos de Front-end

Cursos de DevOps

Cursos de Design & UX

Cursos de Business

Cursos de Data & BI