Ybadoo - Soluções em Software Livre
Tutoriais
Programação Orientada a Objetos

Desenvolva um programa que interprete expressões aritméticas, escritas na notação pós-fixada, como por exemplo, a expressão 4 3 2 - 1 + * que equivale a expressão (3 - 2 + 1) * 4, na notação infixada.

Utilize o padrão de projeto Interpreter para auxiliar no desenvolvimento do interpretador. Defina uma interface (AbstractExpression) com o método interpret(), que seja comum a todos os nós da árvore sintática abstrata.

Defina uma classe para interpretar as constantes numericas da expressão aritmética (TerminalExpression), e uma classe (NonTerminalExpression) para cada uma das quatro operações aritméticas básicas (adição, subtração, multiplicação e divisão).

Defina uma classe para realizar o parser (Client) da expressão, com o seguinte comportamento:

Leia um token da expressão
Se o token é um número
  Então
    Adicione o token a pilha
  Senão
    Retire dois tokens da pilha
    Aplique o operador sobre os dois tokens da pilha
    Adicione na pilha o resultado

 

Diagrama de classes
Diagrama de classes da solução em Java

Arquivo Expression.java

/**
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)
 *                  Ybadoo - Solucoes em Software Livre (www.ybadoo.com.br)
 *
 * Permission is granted to copy, distribute and/or modify this document
 * under the terms of the GNU Free Documentation License, Version 1.3
 * or any later version published by the Free Software Foundation; with
 * no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
 * A copy of the license is included in the section entitled "GNU
 * Free Documentation License".
 */

package com.ybadoo.tutoriais.poo;

/**
 * Interface responsavel pela declaracao da operacao interpret,
 * que sera comum a todos os nodes na arvore sintatica abstrata
 *
 * AbstractExpression
 */
public interface Expression
{
  /**
   * Interpretar o node da arvore sintatica abstrata
   *
   * @return valor do node na arvore sintatica abstrata
   */
  public int interpret();    
}

Arquivo Number.java

/**
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)
 *                  Ybadoo - Solucoes em Software Livre (www.ybadoo.com.br)
 *
 * Permission is granted to copy, distribute and/or modify this document
 * under the terms of the GNU Free Documentation License, Version 1.3
 * or any later version published by the Free Software Foundation; with
 * no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
 * A copy of the license is included in the section entitled "GNU
 * Free Documentation License".
 */

package com.ybadoo.tutoriais.poo;

/**
 * Implementacao da operacao interpret associada aos
 * simbolos terminais da gramatica
 *
 * TerminalExpression
 */
public class Number implements Expression
{
  /**
   * Terminal
   */
  private final int number;

  /**
   * Construtor para inicializar o terminal
   *
   * @param number terminal
   */
  public Number(int number)
  {
    this.number = number;
  }

  /**
   * Construtor para inicializar o terminal
   *
   * @param number terminal
   */
  public Number(String number)
  {
    this.number = Integer.parseInt(number);
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.Expression#interpret()
   */
  @Override
  public int interpret()
  {
    return number;
  }
}

Arquivo BinaryOperation.java

/**
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)
 *                  Ybadoo - Solucoes em Software Livre (www.ybadoo.com.br)
 *
 * Permission is granted to copy, distribute and/or modify this document
 * under the terms of the GNU Free Documentation License, Version 1.3
 * or any later version published by the Free Software Foundation; with
 * no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
 * A copy of the license is included in the section entitled "GNU
 * Free Documentation License".
 */

package com.ybadoo.tutoriais.poo;

/**
 * Classe responsavel pela representacao das operacoes binarias 
 */
public abstract class BinaryOperation
{
  /**
   * Operando do lado esquerdo
   */
  private final Expression left;

  /**
   * Operando do lado direito
   */
  private final Expression right;

  /**
   * Construtor para inicializar os operandos
   *
   * @param left operando do lado esquerdo
   * @param right operando do lado direito
   */
  protected BinaryOperation(Expression left, Expression right)
  {
    this.left = left;
    this.right = right;
  }

  /**
   * Retornar o operando do lado esquerdo
   *
   * @return operando do lado esquerdo
   */
  protected Expression getLeft()
  {
    return left;
  }

  /**
   * Retornar o operando do lado direito
   *
   * @return operando do lado direito
   */
  protected Expression getRight()
  {
    return right;
  }
}

Arquivo Add.java

/**
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)
 *                  Ybadoo - Solucoes em Software Livre (www.ybadoo.com.br)
 *
 * Permission is granted to copy, distribute and/or modify this document
 * under the terms of the GNU Free Documentation License, Version 1.3
 * or any later version published by the Free Software Foundation; with
 * no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
 * A copy of the license is included in the section entitled "GNU
 * Free Documentation License".
 */

package com.ybadoo.tutoriais.poo;

/**
 * Implementacao da operacao interpret para o
 * operador binario da adicao
 *
 * NonterminalExpression
 */
public class Add extends BinaryOperation implements Expression
{
  /**
   * Construtor para inicializar os operandos
   *
   * @param right operando do lado direito
   * @param left operando do lado esquerdo
   */
  public Add(Expression right, Expression left)
  {
    super(left, right);
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.Expression#interpret()
   */
  @Override
  public int interpret()
  {
    return getLeft().interpret() + getRight().interpret();
  }
}

Arquivo Sub.java

/**
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)
 *                  Ybadoo - Solucoes em Software Livre (www.ybadoo.com.br)
 *
 * Permission is granted to copy, distribute and/or modify this document
 * under the terms of the GNU Free Documentation License, Version 1.3
 * or any later version published by the Free Software Foundation; with
 * no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
 * A copy of the license is included in the section entitled "GNU
 * Free Documentation License".
 */

package com.ybadoo.tutoriais.poo;

/**
 * Implementacao da operacao interpret para o
 * operador binario da subtracao
 *
 * NonterminalExpression
 */
public class Sub extends BinaryOperation implements Expression
{
  /**
   * Construtor para inicalizar os operandos
   *
   * @param right operando do lado direito
   * @param left operando do lado esquerdo
   */
  public Sub(Expression right, Expression left)
  {
    super(left, right);
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.Expression#interpret()
   */
  @Override
  public int interpret()
  {
    return getLeft().interpret() - getRight().interpret();
  }
}

Arquivo Mul.java

/**
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)
 *                  Ybadoo - Solucoes em Software Livre (www.ybadoo.com.br)
 *
 * Permission is granted to copy, distribute and/or modify this document
 * under the terms of the GNU Free Documentation License, Version 1.3
 * or any later version published by the Free Software Foundation; with
 * no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
 * A copy of the license is included in the section entitled "GNU
 * Free Documentation License".
 */

package com.ybadoo.tutoriais.poo;

/**
 * Implementacao da operacao interpret para o
 * operador binario da multiplicacao
 *
 * NonterminalExpression
 */
public class Mul extends BinaryOperation implements Expression
{
  /**
   * Construtor para inicializar os operandos
   *
   * @param right operando do lado direito
   * @param left operando do lado esquerdo
   */
  public Mul(Expression right, Expression left)
  {
    super(left, right);
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.Expression#interpret()
   */
  @Override
  public int interpret()
  {
    return getLeft().interpret() * getRight().interpret();
  }
}

Arquivo Div.java

/**
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)
 *                  Ybadoo - Solucoes em Software Livre (www.ybadoo.com.br)
 *
 * Permission is granted to copy, distribute and/or modify this document
 * under the terms of the GNU Free Documentation License, Version 1.3
 * or any later version published by the Free Software Foundation; with
 * no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
 * A copy of the license is included in the section entitled "GNU
 * Free Documentation License".
 */

package com.ybadoo.tutoriais.poo;

/**
 * Implementacao da operacao interpret para o
 * operador binario da divisao
 *
 * NonterminalExpression
 */
public class Div extends BinaryOperation implements Expression
{
  /**
   * Construtor para inicializar os operandos
   *
   * @param right operando do lado direito
   * @param left operando do lado esquerdo
   */
  public Div(Expression right, Expression left)
  {
    super(left, right);
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.Expression#interpret()
   */
  @Override
  public int interpret()
  {
    return getLeft().interpret() / getRight().interpret();
  }
}

Arquivo Parser.java

/**
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)
 *                  Ybadoo - Solucoes em Software Livre (www.ybadoo.com.br)
 *
 * Permission is granted to copy, distribute and/or modify this document
 * under the terms of the GNU Free Documentation License, Version 1.3
 * or any later version published by the Free Software Foundation; with
 * no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
 * A copy of the license is included in the section entitled "GNU
 * Free Documentation License".
 */

package com.ybadoo.tutoriais.poo;

import java.util.Stack;
import java.util.StringTokenizer;

/**
 * Classe responsavel pela construcao da arvore sintatica
 * abstrata que representa determinada sentenca na linguagem
 * definida pela gramatica
 *
 * Client
 */
public class Parser
{
  /**
   * Interpretar a expressao fornecida pelo usuario
   *
   * @param expression expressao fornecida pelo usuario
   * @return valor da expressão fornecida pelo usuario
   */
  public int parser(String expression)
  {
    Stack<Expression> stack = new Stack<Expression>();

    StringTokenizer tokens = new StringTokenizer(expression, " ");

    while(tokens.hasMoreTokens())
    {
      String token = tokens.nextToken();

      if("+".equals(token))
      {
        stack.push(new Number(
                   new Add(stack.pop(), stack.pop()).interpret()));
      }
      else if("-".equals(token))
      {
        stack.push(new Number(
                   new Sub(stack.pop(), stack.pop()).interpret()));
      }
      else if("*".equals(token))
      {
        stack.push(new Number(
                   new Mul(stack.pop(), stack.pop()).interpret()));
      }
      else if("/".equals(token))
      {
        stack.push(new Number(
                   new Div(stack.pop(), stack.pop()).interpret()));
      }
      else
      {
        stack.push(new Number(token));
      }
    }
    return stack.pop().interpret();
  }
}

Arquivo Application.java

/**
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)
 *                  Ybadoo - Solucoes em Software Livre (www.ybadoo.com.br)
 *
 * Permission is granted to copy, distribute and/or modify this document
 * under the terms of the GNU Free Documentation License, Version 1.3
 * or any later version published by the Free Software Foundation; with
 * no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
 * A copy of the license is included in the section entitled "GNU
 * Free Documentation License".
 */

package com.ybadoo.tutoriais.poo;

/**
 * Classe responsavel pela execucao do interpretador
 */
public class Application
{
  /**
   * Metodo principal da linguagem de programacao Java
   *
   * @param args argumentos da linha de comando (nao utilizado)
   */
  public static void main(String[] args)
  {
    Parser parser = new Parser();

    String expression = "4 3 2 - 1 + *";

    System.out.println(expression + " é igual a "+
      parser.parser(expression));
  }   
}

Saída da solução em Java

4 3 2 - 1 + * é igual a 8