DOMANDA Esercizio Albero Espressioni

[Paakiv]

Salve a tutti.
E' tutto il giorno che faccio esercizi in java e ho trovato questo esercizio sull' eserciziario dell' università.

Spoiler: Testo

Le espressioni aritmetiche manipolate da una calcolatrice tascabile sono ottenute a partire dai numeri interi (positivi e negativi) tramite le operazioni di addizione sottrazione, moltiplicazione e divisione. Esempi sono i seguenti: (2 + 3) ∗ 4, (21/5) ∗ (−1) + 7. Una naturale rappresentazione per queste espressioni è quella tramite alberi, in cui i nodi interni rappresentano le operazioni e le foglie rappresentano invece i numeri. Per esempio, (2 + 3) ∗ 4 corrisponde all’albero la cui radice è etichettata con ∗ e i cui due figli sono l’albero corrispondente a 2 + 3 (composto da tre nodi) e l’albero corrispondente a 4 (composto da un singolo nodo). Data un’espressione, si potrebbe essere interessati a calcolarne il valore (per esempio, l’espressione (2 + 3) ∗ 4 ha valore 20). Inoltre potrebbe essere interessante, data un’espressione, il numero di istanze degli operatori elementari in essa contenuti (per esempio, l’espressione (2+3)∗4 contiene due istanze di operatori aritmetici). Si progetti e si implementi una gerarchia di classi JAVA che sia in grado di rappresentare e manipolare le espressioni utilizzate dalla calcolatrice tascabile.

Non ho la più pallida idea di come si faccia. Qualcuno mi può dare suggerimenti?
Grazie!

 

[Marcus Aseth]

Questo mi pare di capire sia l'esempio da te riportato:

non credo ti serva una marea di classi per risolvere l'esercizio, una funzione recursiva dovrebbe bastare.
Quello che vuoi fare è scomporre un'espressione arbitraria in una serie di "tokens" (è un numero? è un simbole come il + o il -? è una parentesi? Se si, dove si chiude l'altra parentesi?) e poi vuoi ragrupparli e risolverli mantenendo il giusto ordine di precedenza delle operazioni che sicuramente ti hanno insegnato a scuola :)

 

[Paakiv]

Il mio problema è proprio che l'espressione è sempre diversa e non semplice come l'esempio.
Non capisco come dare priorità alle parentesi e hai segni * e /.
Sul fatto che sia ricorsiva si, ho fatto un altro esercizio, è stato ostico ma ce l'ho fatta, ma era più semplice...
L'idea dei token mi piace...

 

[Marcus Aseth]

Forse questo può aiutarti, codice di Bjarne Stroustrup http://www.stroustrup.com/Programming/Solutions/Ch7/e7-1.cpp
In particolare questa parte qua:

 The grammar for input is:

    Expression:
        Term
        Expression + Term
        Expression - Term
    Term:
        Primary
        Term * Primary
        Term / Primary
        Term % Primary
    Primary:
        Number
        Name
        Name = Expression
        ( Expression )
        - Primary
        + Primary
    Number:
        floating-point-literal

Expression, Term, Primary in pratica sono le funzioni che ha implementato per gestire i vari casi elencati nella lista sopra ed ognuna di esse scompone il problema in un problema piu piccolo, inoltre ha una variabile globale che è lo stream di tokens al quale tutte le funzioni possono accedere.
Ci sono un bel pò di pagine nel suo libro dedicate alla spiegazione, è un pò complicato ma con un pò di impegno si può capire xD

 

[rodhellas]

Il testo ti chiede di creare un parser. Cerca online a riguardo

 

[DispatchCode]

Salve a tutti.
E' tutto il giorno che faccio esercizi in java e ho trovato questo esercizio sull' eserciziario dell' università.

Spoiler: Testo

Le espressioni aritmetiche manipolate da una calcolatrice tascabile sono ottenute a partire dai numeri interi (positivi e negativi) tramite le operazioni di addizione sottrazione, moltiplicazione e divisione. Esempi sono i seguenti: (2 + 3) ∗ 4, (21/5) ∗ (−1) + 7. Una naturale rappresentazione per queste espressioni è quella tramite alberi, in cui i nodi interni rappresentano le operazioni e le foglie rappresentano invece i numeri. Per esempio, (2 + 3) ∗ 4 corrisponde all’albero la cui radice è etichettata con ∗ e i cui due figli sono l’albero corrispondente a 2 + 3 (composto da tre nodi) e l’albero corrispondente a 4 (composto da un singolo nodo). Data un’espressione, si potrebbe essere interessati a calcolarne il valore (per esempio, l’espressione (2 + 3) ∗ 4 ha valore 20). Inoltre potrebbe essere interessante, data un’espressione, il numero di istanze degli operatori elementari in essa contenuti (per esempio, l’espressione (2+3)∗4 contiene due istanze di operatori aritmetici). Si progetti e si implementi una gerarchia di classi JAVA che sia in grado di rappresentare e manipolare le espressioni utilizzate dalla calcolatrice tascabile.

Non ho la più pallida idea di come si faccia. Qualcuno mi può dare suggerimenti?
Grazie!

Di norma su usano delle LIFO, una per gli operatori ed una per i valori.

Ho trovato due vecchi codici scritti in piccoli esercizietti risalenti ad anni fa.
Qui utilizzo la notazione RPN:

import java.util.Scanner;
import java.util.Stack;

class RPNNotation {

 private RPNNotation() {}

 public static double execute(String expression) {
   Stack<Double> stack = new Stack<Double>();
   Scanner scanner = new Scanner(expression);
   scanner.useDelimiter(" ");
   
   double v1 = 0.0;
   
   while(scanner.hasNext()) {
     String item = scanner.next();

     switch(item) {
       case "*":
         v1 = stack.pop();
         stack.push(stack.pop() * v1);
         break;
       case "+":
         v1 = stack.pop();
         stack.push(stack.pop() + v1);
         break;
       case "-":
         v1 = stack.pop();
         stack.push(stack.pop() - v1);
         break;
       case "/":
         v1 = stack.pop();
         if(v1 == 0) return Double.NaN;
         stack.push(stack.pop() / v1);
         break;
       default:
         stack.push(Double.parseDouble(item));
     }
   }
   
   return stack.pop();
 }
}

class TestRPN {
 public static void main(String[] args) {
   System.out.println(RPNNotation.execute("10 5 * 20 + 5 4 31 + / -")); // 8571428571
 }
}
)

E l'altro che da quanto ho scritto nelle prime righe (chiedo venia ma sono da smartphone, spero non sia formattato male).
Se hai domande chiedi pure.

import java.util.Stack;
import java.util.Scanner;


class EvaluateExpression {

  private EvaluateExpression() {}
  
  private static boolean isNumeric(String str) 
  {
    return str.matches("-?\\d+(\\.\\d+)?");
  }
  // --------------------------------------------------------------------------------
  
  
  // Verifica la priorita' degli operatori
  // @return  true if token1 has a higher priority than token2
  // --------------------------------------------------------------------------------
  private static boolean isHightPriority(String token1, String token2) 
  {
    switch(token2) 
    {
      case "^":
        if(!token1.equals("^")) return true;
        else return false;
      case "*":
      case "/":
        if(token1.equals("+") || token1.equals("-")) return true;
        else return false;
      case "+":
      case "-":
        return false;
    }
    
    return false;
  }
  // --------------------------------------------------------------------------------- 
  
  
  // Parsing Infix Expression
  // @return Postfix Expression
  // ---------------------------------------------------------------------------------
  private static String evaluate(String exp) 
  {
    Stack<String> stack = new Stack<String>();
    StringBuilder sb = new StringBuilder();
    
    Scanner scanner = new Scanner(exp);
    scanner.useDelimiter(" ");
    
    while(scanner.hasNext()) 
    {
      String token = scanner.next();
      
      if(isNumeric(token)) 
      {
        sb.append(token);
        sb.append(" ");
      }
      else if(!token.equals("(") && !token.equals(")")) 
      {
        if(!stack.isEmpty() && isHightPriority(token,stack.peek())) 
        {
          sb.append(stack.pop());
          sb.append(" ");
        }
        stack.push(token);
      }
      else if(token.equals("(")) 
      {
        stack.push(token);
      }
      else if(token.equals(")")) 
      {
        String e;
        
        while(!(e = stack.pop()).equals("(")) 
        {
          sb.append(e);
          sb.append(" ");
        }
      }
    }
    
    while(!stack.isEmpty()) sb.append(stack.pop());
    
    return sb.toString().trim();
  }
  // -----------------------------------------------------------------------------------
  
  
  // Parsing Postfix expression
  // @return  number (result)
  // -----------------------------------------------------------------------------------
  public static double calculate(String exp) 
  {
    Stack<Double> stack = new Stack<Double>();
    Scanner scanner = new Scanner(evaluate(exp));
    scanner.useDelimiter(" ");
    
    while(scanner.hasNext()) 
    {
      String item = scanner.next();
        
      switch(item) 
      {
        case "*":
          stack.push(stack.pop()*stack.pop());
          break;
        case "/":
          stack.push(stack.pop()/stack.pop());
          break;
        case "+":
          stack.push(stack.pop()+stack.pop());
          break;
        case "-":
          stack.push(stack.pop()-stack.pop());
          break;
        case "^": // Non funziona proprio correttamente in alcuni casi, ma l'ho aggiunta comunque
          double f = stack.pop();
          double s = stack.pop();
          stack.push(Math.pow(s,f));
          break;
        default:
          stack.push(Double.parseDouble(item));
      }
    }
    
    return stack.pop();
  }
  // -------------------------------------------------------------------------------------
  
  
}

class TestExp {
  public static void main(String[] args) {
    // This is the correct format of the input string
    System.out.println(EvaluateExpression.calculate("( 1 + 3 * ( 4 ^ 2 ) + ( ( 2 + 3 + 5 ) * 2 + 2 * 4 ) * 2 ) ^ 2"));
  }
}

 

[Paakiv]

Grazie, mi ero arreso, ci riproverò...