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

23 de novembro de 2007 3 respostas

adiniz 23 de novembro de 2007

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.

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+B*C-D+E/F
		//	ABC*+D-EF/+
		System.out.println("Infixa:   A+B*C-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);
			}
		}
	}
}

3 Respostas

peczenyj 23 de nov. de 2007

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 23 de nov. de 2007

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

Abração.

adiniz 11 de dez. de 2007

:D 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"
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------

/*	
 *	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);
	}
}

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

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);
	}
}

Criado 23 de novembro de 2007

Ultima resposta 11 de dez. de 2007

Respostas 3

Participantes 2

3 Respostas

Topicos relacionados