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.
[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!
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é +++
