Calcular o valor postfix

Thread.start() Membro desde: 18/04/2009 23:54:51 Mensagens: 32 Offline

Boas

Será que alguém me pode ajudar com este código onde quero calcular o valor de uma expressão em postfix,isto é o que tentei fazer e acho que está perto do código correct:

public double calculadora(String ex){
          double total = 0.0;
          int temp1 = 0;
          int temp2 = 0;
          char[] c = ex.toCharArray();
          Stack<Integer> stack = new Stack<Integer>(); 
          for(int n = 0; n < c.length; n++){
               switch(c[n]){
                    case 0:
                    case 1:
                    case 2:
                    case 3:
                    case 4:
                    case 5:
                    case 6:
                    case 7:
                    case 8:
                    case 9:
                         
                         stack.push(Integer.valueOf(c[n]));
                         break;
                    case '+':
                         temp1 = stack.pop();
                         temp2 = stack.pop();
                         stack.push(temp2 + temp1);
                         break;
                    case '-':
                         temp1 = stack.pop();
                         temp2 = stack.pop();
                         stack.push(temp2 - temp1);
                         break;
                    case '*':
                         temp1 = stack.pop();
                         temp2 = stack.pop();
                         stack.push(temp2 * temp1);
                         break;
                    case '/':
                         temp1 = stack.pop();
                         temp2 = stack.pop();
                         stack.push(temp2 / temp1);
                         break;
               }
               total = stack.pop();
          }
          return total;
     }

Desde já muito obrigado

This message was edited 8 times. Last update was at 05/12/2009 09:52:01

Oi nellaf,

Bem, existiam alguns erros tanto da lógica da manipulação da pilha e do método em sí.
Abaixo coloco o código corrigido e comentado

import java.util.*;

public class Teste {

public static void main( String[] args ) {
    	System.out.println( new Teste().calculadora( "34+" ) );
    }
    
    public double calculadora(String ex){
    
        double total = 0.0;
        int temp1 = 0;
        int temp2 = 0;
        char[] c = ex.toCharArray();
        
        Stack<Integer> stack = new Stack<Integer>(); 
            
        for(int n = 0; n < c.length; n++){
            
            switch(c[n]){
                
                // os cases precisam testar os caracteres de 0 a 9, sendo assim, faltou o abre e fecha das aspas simples
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                    /* vc estava inserindo o valor que representa o caracter e não o número em sí.
                     * para calular o inteiro que representa o caracter, basta subtrair o caracter 0
                     * por exemplo, caso c[n] seja '3'. O valor de '0' é 48, o valor de '3' é 51, sendo assim, 
                     * '3' - '0' = 3 ou seja 51 - 48 = 3 que é o valor de interesse.
                     */
                    stack.push( c[n] - '0' );
                    break;
                    
                case '+':
                    temp1 = stack.pop();
                    temp2 = stack.pop();
                    stack.push(temp2 + temp1);
                    break;
                    
                case '-':
                    temp1 = stack.pop();
                    temp2 = stack.pop();
                    stack.push(temp2 - temp1);
                    break;
                    
                case '*':
                    temp1 = stack.pop();
                    temp2 = stack.pop();
                    stack.push(temp2 * temp1);
                    break;
                    
                case '/':
                    temp1 = stack.pop();
                    temp2 = stack.pop();
                    stack.push(temp2 / temp1);
                    break;
                    
            }
            
        }
        
        /* vc estava removendo o topo da pilha a cada iteração do for.
         * no seu caso, o resultado vai estar computado (e empilhado)
         * quanto o for terminar.
         */
        total = stack.pop();
                
        return total;
        
    }    
    
}

Algumas observações.
Se vc quiser mesmo um parser para expressões pós-fixadas em que a precedência dos operadores deve ser respeitada, que se possa usar parênteses e os números não estejam apenas nas unidades (apenas um dígito) vc vai precisar melhorar um pouco sua estrutura e trabalhar com reconhecimento de gramáticas.
Por exemplo, a gramática:

Reconhece expressões desse tipo (mas com números de um dígito)
Mudando um pouquinho ela conseguimos reconhecer números inteiros de vários dígitos.

Mas como falei, para reconhecer esse tipo de estrutura vc precisa melhorar um pouco seu método, construindo para isso um analizador léxico e um sintático. Entretanto, acho que o que vc quer mesmo é só fazer expressões simples como 45+ 76- 97* 29/
Para isso, o que eu te passei já resolve. Note também que não usei uma notação formal para as gramáticas. Ah, e não esquecendo de dize que ep é o símbolo vazio (epson). É possível reconhecer os parênteses usando a pilha, acho até que é possível tratar a precedência da forma que você está fazendo, mas acho que um analisador ficaria mais fácil de entender.

[]´s

P.S. Faltou falar também que as gramáticas que passei reconhecem expressões infixadas.
P.S.2 Faltou a produção inicial das gramáticas. Já arrumei

Thread.start() Membro desde: 18/04/2009 23:54:51 Mensagens: 32 Offline

Muito obrigado, já funciona correctamente.
Agora estava a querer fazer o mesmo para calcular a partir do preFixa, é possivel?

nellaf wrote:Muito obrigado, já funciona correctamente.
Agora estava a querer fazer o mesmo para calcular a partir do preFixa, é possivel?

É possível sim.

Seria algo como:

import java.util.*;

public class Infixa {

public static void main( String[] args ) {
    	System.out.println( new Infixa().calculadora( "+34+3*4-5/7" ) );
    }
    
    public double calculadora(String ex){
    
        double total = 0.0;
        Integer temp1 = null;
        Integer temp2 = null;
        char[] c = ex.toCharArray();
            
        for(int n = 0; n < c.length; n++){
            
            switch(c[n]){
                    
                case '+':
                    temp1 = c[++n] - '0';
                    if ( temp2 == null ) {
                    	temp2 = c[++n] - '0';
                    	total = temp2 + temp1;
                    } else {
                    	total += temp1;
                    }
                    break;
                    
                case '-':
                	temp1 = c[++n] - '0';
                    if ( temp2 == null ) {
                    	temp2 = c[++n] - '0';
                    	total = temp2 - temp1;
                    } else {
                    	total -= temp1;
                    }
                    break;
                    
                case '*':
                	temp1 = c[++n] - '0';
                    if ( temp2 == null ) {
                    	temp2 = c[++n] - '0';
                    	total = temp2 * temp1;
                    } else {
                    	total *= temp1;
                    }
                    break;
                    
                case '/':
                	temp1 = c[++n] - '0';
                    if ( temp2 == null ) {
                    	temp2 = c[++n] - '0';
                    	total = temp2 / temp1;
                    } else {
                    	total /= temp1;
                    }
                    break;
                    
            }
            
        }
                
        return total;
        
    }    
    
}

Perceba que não há necessidade de usar uma pilha. Como lhe falei, seria melhor vc usar um esquema de análise mais robusto pois esse algoritmo que está usando é muito simples e muito pouco flexível.

Vou preparar um código aqui para reconhecimento da primeira gramática que postei no post anterior. Logo posto para vc.

[]´s

Thread.start() Membro desde: 18/04/2009 23:54:51 Mensagens: 32 Offline

Eu sou iniciante em java e talvez por isso o algoritmo seja muito simples. Por acaso conclui a pouco o algoritmo para o prefixa, é o seguinte:

public double calculadoraPre(String ex){  
          
          double total = 0.0;  
          double temp1 = 0.0;  
          double temp2 = 0.0;  
          char[] c = ex.toCharArray(); 
          boolean moreDigit = false; 
          
          Stack<Double> stackN = new Stack<Double>();
          Stack<String> stackS = new Stack<String>();
          
          for(int n = 0; n < c.length; n++){  
               
               switch(c[n]){  
                    
                    case '0':  
                    case '1':  
                    case '2':  
                    case '3':  
                    case '4':  
                    case '5':  
                    case '6':  
                    case '7':  
                    case '8':  
                    case '9':
                         if(n == (c.length - 1)){     
                              stackN.push( (double)(c[n] - '0') );
                              while(stackN.size() > 1){
                                   temp1 = stackN.pop();
                                   temp2 = stackN.pop();
                                   stackN.push(cal(stackS.pop(), temp2, temp1));
                              }
                         }   
                         else if(stackN.size() == 2 && n != (c.length - 1)){
                              if(moreDigit == false){
                                   stackN.push( (double)(c[n] - '0') );
                                   temp1 = stackN.pop();
                                   temp2 = stackN.pop();
                                   stackN.push(cal(stackS.pop(), temp2, temp1));
                                   moreDigit = true;
                              }
                              else
                              {
                                   temp1 = stackN.pop();
                                   temp2 = stackN.pop();
                                   stackN.push(cal(stackS.pop(), temp2, temp1));
                                   stackN.push( (double)(c[n] - '0') );
                                   moreDigit = true;
                              }
                         }
                         else
                              stackN.push( (double)(c[n] - '0') );  
                         break;  
                         
                    default: 
                         if(stackN.size()>=2){
                         
                         temp1 = stackN.pop();
                         temp2 = stackN.pop();
                         stackN.push(cal(stackS.pop(), temp2, temp1));
                         stackS.push(Character.toString(c[n]));
                         moreDigit = false;
                    }
                         else
                              stackS.push(Character.toString(c[n]));
                         break;
               }  
          } 
          total = stackN.pop();     
          return total; 
     } 
     
     private double cal(String c, double n1, double n2){
          char sinal = c.charAt(0);
          double num1 = n1;
          double num2 = n2;
          double t = 0;
          switch(sinal){
               case '+': t = num1 + num2;break;
               case '-': t = num1 - num2;break;
               case '*': t = num1 * num2;break;
               case '/': t = num1 / num2;break;
          }
          return t;
     }

Poderia dizer o que cada case está a fazer, é que não estou a conseguir ler a lógica do algoritmo.
Pode ver outro post meu em http://www.guj.com.br/posts/list/146336.java e ver se é possivel simplificar ou alterar alguma coisana classe ArvExp.java?

Muito obrigado

This message was edited 2 times. Last update was at 04/12/2009 23:57:36

Fiz o exemplo da gramática:

/**
 * Parser para a gramática:
 *
 * E => T Ei
 * Ei => '+' T Ei | ep
 * T => F Ti
 * Ti => '*' F Ti | ep
 * F => '0'..'9' | '(' E ')'
 *
 * @author David Buzatto
 */
public class Parser {

private char token;
    private int posToken;
    private char[] entrada;

public static void main( String[] args ) {
        System.out.println( new Parser().parse( "(2+2+2)+2*3".toCharArray() ) );
    }

public int parse( char[] entrada ) {

this.entrada = entrada;
        posToken = 0;

// vai para o próximo token
        proximoToken();

int resultado = E();

// se o token corrente for diferente de '\0' quer dizer
        // que faltaram tokens para reconhecer, então dispara um erro
        if ( token != '\0' ) {
            erro();
        }

return resultado;

}

private int E() {
        int esquerda = T();
        int direita = Ei();
        return esquerda + direita;
    }

private int T() {
        int esquerda = F();
        int direita = Ti();
        return esquerda * direita;
    }
    
    private int Ei() {

// 0 é o elemento neutro da adição
        int resultado = 0;

if ( token == '+' ) {
            proximoToken();
            int esquerda = T();
            int direita = Ei();
            resultado = esquerda + direita;
        }

return resultado;

}

private int Ti() {

// 1 é o elemento neutro da multiplicação
        int resultado = 1;

if ( token == '*' ) {
            proximoToken();
            int esquerda = F();
            int direita = Ti();
            resultado = esquerda + direita;
        }

return resultado;

}

private int F() {

int resultado = 0;

if ( token == '(' ) {

proximoToken();
            resultado = E();

if ( token == ')' ) {
                proximoToken();
            } else {
                erro();
            }

return resultado;

} else {
            return numero();
        }

}

private int numero() {

int resultado = 0;

if ( token >= '0' && token <= '9' ) {
            resultado = token - '0';
            proximoToken();
        } else {
            erro();
        }

return resultado;

}

private void proximoToken() {
        
        while ( posToken < entrada.length && entrada[posToken] == ' ' ) {
            posToken++;
        }
        
        if ( posToken < entrada.length ) {
            token = entrada[posToken];
            posToken++;
        } else {
            token = '\0';
        }
        
    }

private void erro() {
        
        if ( posToken == 0 ) {
            posToken = 1;
        } else if ( posToken >= entrada.length ) {
            posToken = entrada.length;
        }
        
        String strEntrada = new String( entrada, posToken - 1, entrada.length - posToken + 1 );
        String strErro = "Erro em \"" + strEntrada + "\"";
        System.out.print( strErro );
        
        throw new RuntimeException( strErro );
        
    }
    
}

É analisador léxico e sintático muuuuuito simples para expressões com as operações de adição e multiplicação, respeitando a precedência dos operadores e o uso de parênteses.
Se quiser colocar as outras operações é só queimar um pouco de fosfato

[]´s

Thread.start() Membro desde: 18/04/2009 23:54:51 Mensagens: 32 Offline

davidbuzatto wrote:

nellaf wrote:Muito obrigado, já funciona correctamente.
Agora estava a querer fazer o mesmo para calcular a partir do preFixa, é possivel?

É possível sim.

Seria algo como:
[code...[/code]

Perceba que não há necessidade de usar uma pilha. Como lhe falei, seria melhor vc usar um esquema de análise mais robusto pois esse algoritmo que está usando é muito simples e muito pouco flexível.

Vou preparar um código aqui para reconhecimento da primeira gramática que postei no post anterior. Logo posto para vc.

[]´s

Obrigado por tudo...
Poderia ver outro post meu (http://www.guj.com.br/posts/list/146336.java) a ver se há maneira de simplificar a classe AevExp.class??

Obrigado

Notícias, artigos e o maior fórum brasileiro sobre Java