Exercício 10.31

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

Arquivo Expression.java

/**
 * Copyright (C) 2009/2025 - 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/2025 - 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/2025 - 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/2025 - 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/2025 - 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/2025 - 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/2025 - 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/2025 - 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/2025 - 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

Tutoriais - Programação Orientada a Objetos
Tutoriais
Programação Orientada a Objetos

Implementação na linguagem de programação Java

Arquivo Expression.java

Arquivo Number.java

Arquivo BinaryOperation.java

Arquivo Add.java

Arquivo Sub.java

Arquivo Mul.java

Arquivo Div.java

Arquivo Parser.java

Arquivo Application.java

Saída da solução em Java

Tutoriais - Programação Orientada a ObjetosTutoriaisProgramação Orientada a Objetos

Exercício 10.31

Implementação na linguagem de programação Java

Arquivo Expression.java

Arquivo Number.java

Arquivo BinaryOperation.java

Arquivo Add.java

Arquivo Sub.java

Arquivo Mul.java

Arquivo Div.java

Arquivo Parser.java

Arquivo Application.java

Saída da solução em Java

Tutoriais - Programação Orientada a Objetos
Tutoriais
Programação Orientada a Objetos