Validar Expressão Matemática

Olá,
Gostaria que me ajudasem a validar expressões matemáticas:

[code]import java.util.Scanner;
public class ExpresaoMath {
public static void main(String[] args) {
Expressao pilha = new Expressao(6);

	Scanner in = new Scanner(System.in);   
	System.out.println("Digite uma expressão algébrica no formato {[()]}\n");     
	String expr = in.nextLine(); 
				
	for (int i = 0; i <= expr.length() - 1; i++) {
		if (pilha.getDelimitador(expr.charAt(i))) {
			pilha.empilha(expr.charAt(i));
		}
	}
	String aux = pilha.retornaFormato();
	if (aux.equals("{[()]}")) {
		System.out.println("Expressão Correta");
	} else {
		System.out.println("Expressão Incorreta");
	}
}

}
class Expressao {
protected String elementos[];
private int topo;
protected char[] delimitadores = {’{’, ‘[’, ‘(’, ‘)’, ‘]’, ‘}’};
public Expressao(int tamanho) {
topo = -1;
elementos = new String[tamanho];
}
public void empilha(char x) {
topo++;
elementos[topo] = String.valueOf(x);
}
public void desempilha() {
topo–;
}
public String elementoTopo() {
return elementos[topo].toString();
}
public boolean pilhaCheia() {
return (topo == elementos.length - 1);
}
public boolean listaVazia() {
return (topo == -1);
}
public boolean getDelimitador(char valor) {
boolean ok = false;
for (int i = 0; i <= delimitadores.length - 1; i++) {
ok = delimitadores[i] == valor ? true : false;
if (ok) {
break;
}
}
return ok;
}
public String retornaFormato(){
String formato = “”;
for (int i = 0; i <= elementos.length-1; i++) {
formato += elementos[i];
}
return formato;
}
}[/code]

Somente validação se a expressão e valida, não precisa fazer os cauclos e dar a resposta.

Antes de mais nada, dá uma lida nesse artigo:

Algumas perguntas:

:arrow: você precisa somente validar a expressão ou vai precisar resolvê-la, em um dado momento ?

:arrow: você quer aprender como faz ou precisa colocar em produção ?

[quote=rmendes08]Antes de mais nada, dá uma lida nesse artigo:

Algumas perguntas:

:arrow: você precisa somente validar a expressão ou vai precisar resolvê-la, em um dado momento ?

:arrow: você quer aprender como faz ou precisa colocar em produção ?[/quote]

Preciso só verificar se a expressão é valida ou não!
sera usada como fim de aprendizagem, pois colocar em pilha por exemplo (a, b, c) e depois remover é uma coisa, mais colocar em uma pilha { [ ( e remover os mesmos usando ) ] } isso eu não consegui.

por isso se alguém souber implementar isso no código eu agradeço.

Bom, eu recomendaria você entender o tema do artigo que eu passei, é uma teoria valiosa, apesar de ser um pouco difícil passar pra código.

O caminho de fato é usar uma pilha para verificar o abre-fecha dos delimitadores. Mas só a pilha não é suficiente, pois você pode empilhar “{,[,[,(” e desempilhar “),],},]” e a palavra seria reconhecida. O caminho é o seguinte:

:arrow: você usa uma única pilha, os únicos caracteres que devem ser empilhados são os caracteres de abertura: {,[ ou (

:arrow: você precisa criar um controle de estados para saber qual é o tipo de delimitador que foi aberto. Por exemplo, se encontrou ‘{’, empilha e vai para o estado A.

No estado A você pode :
- encontrar ‘}’ e desempilhar,
- encontar ‘[’, empilhar e ir para o estado B
- encontrar ‘(’, empilhar e ir para o estado C
- falhar, caso encontre ‘]’, ou ‘)’

e por ai vai …

Não se deixe enganar. Apesar de bem conhecida, a solução para esse problema não é simples de se chegar sozinho. E na boa, não menospreze teoria.

[quote=rmendes08]Bom, eu recomendaria você entender o tema do artigo que eu passei, é uma teoria valiosa, apesar de ser um pouco difícil passar pra código.

O caminho de fato é usar uma pilha para verificar o abre-fecha dos delimitadores. Mas só a pilha não é suficiente, pois você pode empilhar “{,[,[,(” e desempilhar “),],},]” e a palavra seria reconhecida. O caminho é o seguinte:

:arrow: você usa uma única pilha, os únicos caracteres que devem ser empilhados são os caracteres de abertura: {,[ ou (

:arrow: você precisa criar um controle de estados para saber qual é o tipo de delimitador que foi aberto. Por exemplo, se encontrou ‘{’, empilha e vai para o estado A.

No estado A você pode :
- encontrar ‘}’ e desempilhar,
- encontar ‘[’, empilhar e ir para o estado B
- encontrar ‘(’, empilhar e ir para o estado C
- falhar, caso encontre ‘]’, ou ‘)’

e por ai vai …

Não se deixe enganar. Apesar de bem conhecida, a solução para esse problema não é simples de se chegar sozinho. E na boa, não menospreze teoria.[/quote]

você poderia dar inicio no código necessário para que isso seja feito.
pois como você disse uma coisa é entender o que deve ser feito outra é saber como fazer!

como o rmendes08 disse voçe vai precisar daquela teoria pois pelo que ententi tens de usar uma expressao regular… em java existe a biblioteca java.util.regex que da tratamento a isso!

Se precisar de mais alguma ajuda é so dizer

No meu entender o algoritmo tem fazer o seguinte:

Algoritmo ValidaExpressao;
Entrada: {l+9+[c-d]*[a/b]};
Percorra a entrada, coletando os caracteres de abertura até “esbarrar” em um caracter de fechamento;
Adicione os caracteres de abertura na pilha; (EX: {[ onde colchete é o topo da pilha.)
Tendo “esbarrado” em um “]” compare se pertence ao mesmo tipo do topo da pilha;

e vai…

Até percorrer toda sua Entrada (expressão) a pilha deverá estar vazia.

Ex: Data Expresao: {[()]}
Empilhariamos: {[(
Esbarrariamos em: )
Removeriamos: (
A Pilha ficaria: {[
Esbarrariamos em: ]
Removeriamos: [
A pilha ficaria: {
Esbarrariamos em: }
Removeriamos: {

Pilha Vazia TRUE;

Difícil explicar isso escrevendo, vou tentar implementar.

[quote=ruben_m]como o rmendes08 disse voçe vai precisar daquela teoria pois pelo que ententi tens de usar uma expressao regular… em java existe a biblioteca java.util.regex que da tratamento a isso!

Se precisar de mais alguma ajuda é so dizer[/quote]

Não, expressões regulares não são suficientes para resolver esse problema, pois elas definem apenas linguagens regulares. No caso, expressões matemáticas são linguagens livres de contexto, e estas precisam de no mínimo um autômato com pilha para o seu reconhecimento.

Para validar expressões aritméticas, não é possível usar expressões regulares tradicionais (como as implementadas por várias linguagens, entre as quais o Java).

Seria necessário usar expressões regulares recursivas, que só existem em Perl e PHP ( usa-se o “(??{ })” - veja: http://www.perl.com/pub/2003/06/06/regexps.html e obviamente são absurdamente complicadas de usar, e pior, de dar manutenção.

Widglan, tenta implmentar a pilha como descrevi acima, pode não ser completo … mas ja mata a charada quanto a paridade dos parenteses , colchetes e chaves…
Como isso deve ser trabalho de escola, claro que o professor ja vai te dar uma boa nota…

[quote=wspinheiro]Widglan, tenta implmentar a pilha como descrevi acima, pode não ser completo … mas ja mata a charada quanto a paridade dos parenteses , colchetes e chaves…
Como isso deve ser trabalho de escola, claro que o professor ja vai te dar uma boa nota…[/quote]

eu não daria …

a pilha por si não resolve o problema. Isso porque ela pode aceitar entradas como “{( 3 + 5 } - 1)” , que obviamente está errada. Aliás, seria o 1o teste que faria, e já descontaria uma boa nota. Para que a implementação fique completa, é essencial que haja estados de máquina diferentes para cada tipo de delimitador.

Lê Expressao “{( 3 + 5 } - 1)”
É abertura to tipo chave empilha;
É abertura do tipo parentese empilha;
É fecha chave compara com o tipo do topo da pilha;
Tipo do topo da pilha é parentese;
Tipo de fechamento não casa com o de abertura.

Vai ter que fazer essa validação… não importa como , mas claro tem que fazer…

e eu disse: [quote]Tendo “esbarrado” em um “]” compare se pertence ao mesmo tipo do topo da pilha; [/quote]

Fiz um exemplinho só para validar a paridade dos elementos {[()]}:

Caracter.java

package expressaonumerica;

public class Caracter {

	char conteudo;

	public char getConteudo() {
		return conteudo;
	}

	public void setConteudo(char conteudo) {
		this.conteudo = conteudo;
	}

	public String getTipoCaracter(Caracter c){
		String tipo = null;
		if(c.getConteudo()=='{'||c.getConteudo()=='}'){
			tipo = "chaves";
		}else
			if(c.getConteudo()=='['||c.getConteudo()==']'){
				tipo = "colchetes";
			}else
				if(c.getConteudo()=='('||c.getConteudo()==')'){
					tipo = "parenteses";
				}
		return tipo;
	}

	public boolean eAbertura(Caracter c){
		if(c.getConteudo()=='{'||c.getConteudo()=='['||c.getConteudo()=='(')
			return true;
		else
			return false;
	}

	public boolean eFechamento(Caracter c){
		if(c.getConteudo()=='}'||c.getConteudo()==']'||c.getConteudo()==')')
			return true;
		else
			return false;
	}

	@Override
	public String toString() {
		return String.valueOf(conteudo);
	}
}

Pilha.java com lista encadeada, poderia ser utilizada o Stack seria até mais facim… :lol:

package expressaonumerica;
import java.util.LinkedList;
import java.util.List;

public class Pilha {
	LinkedList<Caracter> caracteres = new LinkedList<Caracter>(); 
	
	public void empilha(Caracter c) {
		caracteres.push(c);
	}

	public Caracter desempilha(){
		if(eVazia()){
			System.out.println("Pilha está vazia.");
			return null;
		}
		else{
			Caracter caracterRemovido = this.
			caracteres.pop();
			return caracterRemovido;
		}
	}
	
	public boolean eVazia() {
		return caracteres.isEmpty();
	}

	
	public Caracter primeiroElemento(){
		return this.caracteres.getFirst();
	}

	public boolean valida(Pilha pilha, List<Caracter> caracteres){
		if(pilha.eVazia())
		for (int i = 0; i < caracteres.size(); i++) {
			if(caracteres.get(i).eAbertura(caracteres.get(i)))
				pilha.empilha(caracteres.get(i));
			else
				if(caracteres.get(i).eFechamento(caracteres.get(i)))
					if(pilha.eVazia())
					return false;
				else
					if(pilha.primeiroElemento().getTipoCaracter(pilha.primeiroElemento()).equals(caracteres.get(i).getTipoCaracter(caracteres.get(i))))
						pilha.desempilha();
				if(pilha.eVazia())
					return true;
		}
		return false;
		
	}
}

E testizim

package expressaonumerica;

import java.util.ArrayList;
import java.util.List;
public class TesteExpressao {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Pilha pilha = null;
		List<Caracter> cars = null;
		Caracter car = null;
		String expressao = "{l+9+[c+d]*[a/b]}";
		//String expressao = "{a+b*[x+y+(z*p)+(c/d)])";
		cars = new ArrayList<Caracter>(expressao.length());

		for (int i = 0; i < expressao.length(); i++) {
			car = new Caracter();
			car.setConteudo(expressao.charAt(i));
			cars.add(car);
		}
		pilha = new Pilha();
		if(pilha.valida(pilha,cars))
			System.out.println("Pilha Válida!");
		else 
			System.out.println("Pilha Inválida!");
	}

}

A classe caracter pode ter muitos mais métodos, pode ser separadamente reconhecido que caracter ele é , tipo eParentese, eAbreParentese… atribuir peso aos elementos da expressão para não deixar perder a ordem tipo “({” que aqui não está validado.

pode faltar alguns imports porque selecionei tudo copiei e colei… até +++

Galera,

segue o meio de validação de expressões com chaves, colchetes e parêntese que desenvolvi com base nas fontes passadas aqui:

package conjuntos.Model;

import java.util.Stack;

/**
 *
 * @author Davy
 */
public class Entrada {

    private String expressao;
    
    public Entrada(String pExpressao){
        this.expressao = pExpressao;
    }

    public boolean validarFormacao() {        
        Stack controle = new Stack();

        for (int i = 0; i < this.expressao.length(); i++) {
            if (this.expressao.charAt(i) == '{' || this.expressao.charAt(i) == '[' || this.expressao.charAt(i) == '(') {
                controle.push(this.expressao.charAt(i));
            } else if (this.expressao.charAt(i) == ')' || this.expressao.charAt(i) == ']' || this.expressao.charAt(i) == '}') {
                if (controle.isEmpty()) {
                    return false;
                } else if (this.expressao.charAt(i) == ')' && controle.peek().equals('(')) {
                    controle.pop();
                    //calcular
                    continue;
                } else if (this.expressao.charAt(i) == ']' && controle.peek().equals('[')) {
                    controle.pop();
                    //calcular
                    continue;
                } else if (this.expressao.charAt(i) == '}' && controle.peek().equals('{')) {
                    controle.pop();
                    //calcular
                    continue;
                }
                return false;
            }
        }
        if(controle.isEmpty()) return true;
        return false;
    }

    public String getExpressao() {
        return expressao;
    }
}

Para quem quiser testar, segue ae:

package conjuntos.Control;

import conjuntos.Model.Entrada;
import java.util.Scanner;

/**
 *
 * @author Davy
 */
public class Anfitriao {
    
    public static void main(String[] args) {
        
        System.out.println("Digite a expressao: ");
        Scanner sc = new Scanner(System.in);
        String expressao = sc.nextLine();
                
        System.out.println("Entrada: " + expressao);              
        Entrada entrada = new Entrada(expressao);        
        
        if(entrada.validarFormacao()) {
            System.out.println("Expressao validada!");
        } else {
            System.out.println("Expressao invalida!");
        }
    }    
}

Espero ter ajudado! :slight_smile: