Conversão/Calculo de Infixa para Posfixa, ajuda por favor

9 respostas
dambros

Bom dia,

Preciso desenvolver um código que realize basicamente três tarefas:

1- Verificar se a expressão é uma expressão válida (em outras palavras se é uma expressão infixa);
2- Converter a expressão para Posfixa;
3- Disponibilizar a possibilidade que seja entrado valores para as variáveis da expressão. Por exemplo entro a expressão A+B-C, então tenho que dar a possibilidade de entrar 3 número referentes a cada letra respectivamente.

Até agora desenvolvi o seguinte código:

import java.io.IOException;

import javax.swing.JOptionPane;

public class InToPost {
	private Stack theStack;

	private String input;

	private String output = "";

	public InToPost(String in) {
		input = in;
		int stackSize = input.length();
		theStack = new Stack(stackSize);
	}

	public String doTrans() {
		for (int j = 0; j < input.length(); j++) {
			char ch = input.charAt(j);
			switch (ch) {
			case '+': 
			case '-':
				gotOper(ch, 1); 
				break; 
			case '*': 
			case '/':
				gotOper(ch, 2);
				break; 
			case '(': 
				theStack.push(ch); 
				break;
			case ')': 
				gotParen(ch); 
				break;
			default: 
				output = output + ch; 
			break;
			}
		}
		while (!theStack.isEmpty()) {
			output = output + theStack.pop();

		}

		return output; 
	}

	public void gotOper(char opThis, int prec1) {
		while (!theStack.isEmpty()) {
			char opTop = theStack.pop();
			if (opTop == '(') {
				theStack.push(opTop);
				break;
			}
			else {
				int prec2;
				if (opTop == '+' || opTop == '-')
					prec2 = 1;
				else
					prec2 = 2;
				if (prec2 < prec1) 
				{ 
					theStack.push(opTop);
					break;
				} else

					output = output + opTop; 
			}
		}
		theStack.push(opThis);
	}

	public void gotParen(char ch){ 
		while (!theStack.isEmpty()) {
			char chx = theStack.pop();
			if (chx == '(') 
				break; 
			else
				output = output + chx; 
		}
	}
	

	public static void main(String[] args) throws IOException {
		int contsinais=0,contvalores=0;

		String input = JOptionPane.showInputDialog(
				"Entre com a expressão desejada");

		char [] seq = new char[input.length()];
		input.getChars(0, input.length(), seq, 0);

		for(int i=0;i<input.length();i++){
			if (seq[i]== '*'|seq[i] == '/'|
					seq[i] == '+'| seq[i] == '-'){
				contsinais++;				

			}else
				contvalores++;
		}

		int [] valores = new int[contvalores];
		char [] sinais = new char[contsinais];

		int isinais=0, ivalores=0;
		for(int i=0;i<input.length();i++){


			if (seq[i]== '*'|seq[i] == '/'|
					seq[i] == '+'| seq[i] == '-'){

				sinais[isinais]=seq[i];
				isinais++;
			}else{
				valores[ivalores]= Integer.parseInt(JOptionPane.showInputDialog("Entre com o valor de "+seq[i]));
				ivalores++;
			}

		}


		String output;
		InToPost theTrans = new InToPost(input);
		output = theTrans.doTrans(); 
		System.out.println("Notação Pósfixa: " + output + '\n');

	}
	class Stack {
		private int maxSize;

		private char[] stackArray;

		private int top;

		public Stack(int max) {
			maxSize = max;
			stackArray = new char[maxSize];
			top = -1;
		}

		public void push(char j) {
			stackArray[++top] = j;
		}

		public char pop() {
			return stackArray[top--];
		}
		public char peek() {
			return stackArray[top];
		}

		public boolean isEmpty() {
			return (top == -1);
		}
	}

}

Como verão, o que ele faz é apenas a conversão para posfixa, independente se a expressão entrada é ou não válida (não está fazendo uma verificação prévia). E também, apesar de estar armazenando os sinais (vetor sinais[]) e valores (vetor valores[]) entrados não consigo transformar esses vetores novamente em uma expressão.

Alguém poderia me dar uma ajuda nesse código?

Sei que provavelmente está bastante confuso, mas ainda sou inexperiente no assunto e não consigo fazer tudo de uma forma concisa e objetiva.

Agradeço desde já.

9 Respostas

dambros

Alterei algumas coisas no código e agora consegui realizar a transformação dos valores entrados para uma expressão.

Mas como podem ver se eu entro uma expressão do tipo A+B-C e coloco os valores 1, 2 e 3 eu obtenho a expressão 1+2-3-

Não sei como posso estar corrgindo isso e nem como posso mandar calcular a expressão na string.

Agradeceria ajuda.

*PS: Não reparem nesse monte de System.out... estou usando para poder me encontrar melhor e achar alguns erros.

import java.io.IOException;

import javax.swing.JOptionPane;

import sun.org.mozilla.javascript.internal.EvaluatorException;

public class InToPost {
	private Stack theStack;

	private String input;

	private String output = "";

	public InToPost(String in) {
		input = in;
		int stackSize = input.length();
		theStack = new Stack(stackSize);
	}

	public String doTrans() {
		for (int j = 0; j < input.length(); j++) {
			char ch = input.charAt(j);
			switch (ch) {
			case '+': 
			case '-':
				gotOper(ch, 1); 
				break; 
			case '*': 
			case '/':
				gotOper(ch, 2);
				break; 
			case '(': 
				theStack.push(ch); 
				break;
			case ')': 
				gotParen(ch); 
				break;
			default: 
				output = output + ch; 
			break;
			}
		}
		while (!theStack.isEmpty()) {
			output = output + theStack.pop();

		}

		return output; 
	}

	public void gotOper(char opThis, int prec1) {
		while (!theStack.isEmpty()) {
			char opTop = theStack.pop();
			if (opTop == '(') {
				theStack.push(opTop);
				break;
			}
			else {
				int prec2;
				if (opTop == '+' || opTop == '-')
					prec2 = 1;
				else
					prec2 = 2;
				if (prec2 < prec1) 
				{ 
					theStack.push(opTop);
					break;
				} else

					output = output + opTop; 
			}
		}
		theStack.push(opThis);
	}

	public void gotParen(char ch){ 
		while (!theStack.isEmpty()) {
			char chx = theStack.pop();
			if (chx == '(') 
				break; 
			else
				output = output + chx; 
		}
	}
	


	public static void main(String[] args) throws IOException {
		int contsinais=0,contvalores=0;

		String input = JOptionPane.showInputDialog(
				"Entre com a expressão desejada");

		char [] seq = new char[input.length()];
		input.getChars(0, input.length(), seq, 0);

		for(int i=0;i<input.length();i++){
			if (seq[i]== '*'|seq[i] == '/'|
					seq[i] == '+'| seq[i] == '-'){
				contsinais++;				

			}else
				contvalores++;
		}

		int [] valores = new int[contvalores];
		char [] sinais = new char[contsinais];

		int isinais=0, ivalores=0;
		for(int i=0;i<input.length();i++){


			if (seq[i]== '*'|seq[i] == '/'|
					seq[i] == '+'| seq[i] == '-'){

				sinais[isinais]=seq[i];
				isinais++;
			}else{
				valores[ivalores]= Integer.parseInt(JOptionPane.showInputDialog("Entre com o valor de "+seq[i]));
				ivalores++;
			}

		}
		String [] strSinais= new String [sinais.length];
		String [] strValores= new String [valores.length];
		String expressao ="";
		for(int i=0; i<contsinais;i++){
			 strSinais[i] = String.valueOf(sinais[i]);
		}
		
		for(int i=0; i<contvalores;i++){
			 strValores[i] = String.valueOf(valores[i]);
		}
		
		int j=-1, z=-1;
		int finalização = 0;
		
		for (int i=0; i<input.length();i++){
			
			if(i>=strValores.length){
				j = strValores.length-1;
				System.out.println("Valor i do strvaloresIF: "+i);
				System.out.println("Valor j do strvaloresIF: "+j);
			}else
			{
				j++;
				System.out.println("Valor j do strvaloresELSE: "+j);
			}
			if(i>=strSinais.length){
				z = strSinais.length-1;
				System.out.println("Valor z do strsinaisIF: "+z);
				System.out.println("Valor i do strsinaisIF: "+i);
				finalização++;
			}else{
				z++;
				System.out.println("Valor z do strsinaisELSE: "+z);
			}if(finalização==2){
				
				System.exit(0);
			}else{
			expressao = expressao.concat(strValores[j]+strSinais[z]);
			System.out.println(expressao);
			}
		}
		String output;
		InToPost theTrans = new InToPost(input);
		output = theTrans.doTrans(); 
		System.out.println("Notação Pósfixa: " + output + '\n');

	}
	class Stack {
		private int maxSize;

		private char[] stackArray;

		private int top;

		public Stack(int max) {
			maxSize = max;
			stackArray = new char[maxSize];
			top = -1;
		}

		public void push(char j) {
			stackArray[++top] = j;
		}

		public char pop() {
			return stackArray[top--];
		}
		public char peek() {
			return stackArray[top];
		}

		public boolean isEmpty() {
			return (top == -1);
		}
	}

}
gallo

Dambros, eu já precisei fazer isso e encontrei um site bem interessante que me ajudou bastante

http://www.microsoft.com/brasil/msdn/Tecnologias/vbnet/visualbasic_Stack.mspx

esse ai esta em .net mas tem o algoritmo e o fonte é “muito parecido” com java.

Espero ter ajudade.

T

Bom, você poderia ao menos colocar alguns comentários no seu código para melhor entendimento nosso. Fiz um trabalho desse tipo mas em C#, não vi no seu código a questão de prioridades na hora de empilhar…por exemplo, não posso empilhar um sinal de ’ + ’ se na pilha tenho empilhado um ’ * '. * tem prioridade em relação ao +…qlqer coisa posta ae q te explico melhor…

dambros

Não conheço a linguagem, mas sem duvida ajuda.

Consegui organizar da forma que queria o código…

Mas um novo problema surgiu. Como eu calculo uma expressão que está dentro de uma string?

Algo do tipo 1+2*3?

T

cara, da uma procurada na net sobre o algoritmo de conversão e de cálculo, eu tenho, mas por regra do fórum não é legal passar o código feito a primeiro instante, e também não posso procurar o link pra vc agora…

dambros

Thiago Domingues:
cara, da uma procurada na net sobre o algoritmo de conversão e de cálculo, eu tenho, mas por regra do fórum não é legal passar o código feito a primeiro instante, e também não posso procurar o link pra vc agora…

Como pode ver, não peguei o código pronto e sim desenvolvi o mesmo.

Acontece que me encontro num beco sem saida, pois meu código encontra uma expressão númerica em forma de String e o Java por sem linguagem compilado não possui nenhum método como Eval ()

Agora não sei o que faço.

T

eu sei q vc não pegou código, não disse isso.

veja se isso ajuda:

public double Calcular(string posfixa, Variavel [] vars)
{
            int i = 0;
            double x, y;

            Pilha pilha3 = new Pilha(posfixa.Length);

            foreach(char c in posfixa.ToUpper())
            {
                if(alfabeto.Contains(c.ToString()))
                {
                    // essa função é q troca as letras pelos numeros
                    pilha3.Push(ChangeValue(c,vars));
                }
                else
                {
                    x = (double)pilha3.Pop();
                    y = (double)pilha3.Pop();

                    switch(c)
                    {
                        case '+': pilha3.Push(x + y); break;
                        case '-': pilha3.Push(x - y); break;
                        case '*': pilha3.Push(x * y); break;
                        case '/': pilha3.Push(x / y); break;
                        case '^': pilha3.Push(Math.Pow(x,y)); break;
                    }
                }
            }

            return (double)pilha3.Pop();
}

lembrando que esse cósigo não está em java, mas o algoritmo é bem parecido

dambros

To vendo que terei que reescrever todo meu código, por não ter como sair da string… belas 6h jogadas fora :confused:

Pelo jeito preciso desenvolver de alguma forma que não termine em uma string.

*EDIT: Depois de revirar descobri que no Java 6.0 existe como realizar um “eval” em string ebaaaa.

Agora relacionado a lógica, juro que é a ultima pergunta, como posso fazer para validar uma expressão infixa?

Aldrin_Leal

Só pra constar (até porque precisei eventualmente fazer isso):

Shunting Yard é o algoritmo.

Criado 16 de abril de 2008
Ultima resposta 18 de abr. de 2008
Respostas 9
Participantes 4