Calcular o valor postfix

4 de dezembro de 2009 6 respostas

nellaf 4 de dezembro de 2009

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

6 Respostas

davidbuzatto 4 de dez. de 2009

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:

E => T E'
E' => '+' T E' | '-' T E' | ep
T => F T'
T' => '*' F T' | '/' F T' | ep
F => '0'..'9' | '(' E ')'

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.

E => T E'
E' => '+' T E' | '-' T E' | ep
T => F T'
T' => '*' F T' | '/' F T' | ep
F => Numero | '(' E ')'
Numero => '0'..'9' | '0'..'9' Numero

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

nellaf 4 de dez. de 2009

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

davidbuzatto 4 de dez. de 2009

nellaf:
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

nellaf 4 de dez. de 2009

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

davidbuzatto 4 de dez. de 2009

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 '[code]/**
 * 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 );
        
    }
    
}

' quer dizer // que faltaram tokens para reconhecer, então dispara um erro if ( token != '

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

' ) { 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 = '

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

'; } }

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

}

}[/code]

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

[]´s

nellaf 5 de dez. de 2009

davidbuzatto:
nellaf:
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

Criado 4 de dezembro de 2009

Ultima resposta 5 de dez. de 2009

Respostas 6

Participantes 2

6 Respostas

Topicos relacionados