funzione di valutazione di scrittura String

Question

Sto cercando di scrivere una funzione di valutazione String cioè

evaluate("4 + 1") ; // returns 5 
evaluate("4 + 1 + 3") ; // returns 8 
evaluate("4 + 1 * 3") ; // returns 7 (not 15) 

The operators are + -/and * 

mio iniziale anche se era di usare le espressioni regolari per raccogliere gli operatori e le cifre come queste può essere abbinato. E che dopo aver trovato tali informazioni, in qualche modo capire un modo per dare la priorità agli operatori /* ove -+.

Ecco come ho iniziato:

static String regex = "([\\+\\*-/])+"; 
static String digitRegex = "(\\d)+"; 

public static void main(String[] args) { 
    System.out.println(getOperators("4 + 1 * 3")); 
} 

public static List<String> getOperators(String input) { 
    Pattern p = Pattern.compile(regex); 
    Matcher matcher = p.matcher(input); 

    List<String> operatorList = new ArrayList<String>(); 

    int count = 0; 
    while (matcher.find()){ 
     if (matcher.group(count) != null && matcher.group(count).trim().length() > 0) { 
     operatorList.add(matcher.group(count)); 
     count++; 
     } 
    } 

    return operatorList; 
} 

adesso posso scrivere un altro metodo per estrarre le cifre utilizzando la stessa logica.

public static List<Integer> getDigits(String input) { 
     Pattern p = Pattern.compile(digitRegex); 
     Matcher matcher = p.matcher(input); 

     List<Integer> digitList = new ArrayList<Integer>(); 

     int count = 0; 
     while (matcher.find()) { 
      if (matcher.group(count) != null && matcher.group(count).trim().length() > 0) { 
       digitList.add(Integer.valueOf(matcher.group(count))); 
       count++; 
      } 
     } 

     return digitList; 
    } 

Ora è la parte in cui sono bloccato. # 1 Questo metodo precedente non riesce al terzo esempio:

evaluate("4 + 1 * 3") ; // returns 7 (not 15) 

E questo # 2 Anche se provo esempi precedenti, non riesco a capire come metterli nel giusto ordine.

Sono sulla buona strada, qualcuno ha qualche consiglio utile per favore condividere?

Answer 1

Ho scritto qui qualcosa ... diciamo che veloce & sporco è un eufemismo ...
Con tutti i mezzi, NON DEVE usarlo "così com'è". Ha bisogno di "fissare" - la lettura dei numeri/aritmetica-operazioni dovrebbe essere fatto utilizzando StringTokenizer - ma lascio gli aspetti tecnici a voi;)

public class NewClass { 

    public static int evaluate(String str){ 
     if("".equals(str)){ 
      return 0; 
     } 
     else if(str.length() == 1){ 
      return Integer.valueOf(str); 
     } 
     else{ 
      String _a = String.valueOf(str.charAt(0)); 
      String _b = String.valueOf(str.charAt(1)); 
      if("+".equals(_b) || "-".equals(_b)){ 
       if("+".equals(_b)){ 
        return Integer.valueOf(_a) + evaluate(str.substring(2)); 
       } 
       else{// "-" 
        return Integer.valueOf(_a) - evaluate(str.substring(2)); 
       } 
      } 
      else{// "*" or "/" 
       boolean isMulti = ("*".equals(_b)); 
       String _c = String.valueOf(str.charAt(2));     
       Integer tmp = 0; 
       if(isMulti){ 
        tmp = Integer.valueOf(_a) * Integer.valueOf(_c); 
       } 
       else{ 
        tmp = Integer.valueOf(_a)/Integer.valueOf(_c); 
       } 
       String new_str = String.valueOf(tmp) + str.substring(3);     
       return evaluate(new_str); 
      } 
     } 
    } 

    public static void main(String[] args){   
     String e = "4+1*3"; 
     int t = evaluate(e); 
     System.out.println(e + " = "+t); 
    } 

} 

Answer 2

Si desidera un operator precedence parser. Questo è un parser molto comune basato su tabelle progettato per fare esattamente quello che vuoi. Fondamentalmente, si confronta l'operatore che viene scansionato con quello in cima a uno stack, e si sceglie di ridurre lo stack (ovvero, eseguire i calcoli matematici e spingere il risultato nuovamente in pila), o spingere l'operatore.

Come bonus aggiuntivo, gli OPP sono facili e divertenti da scrivere. È possibile aggiungere supporto per parentesi ecc. Con un piccolo sforzo aggiuntivo.

modifica - Ho appena letto l'articolo wiki. È terribile.

Trova altri esempi di questo tipo di parser.

Edit 2 -

This one shows a sample in c. Note the table.

This one is pretty good.

E ricordate, si sta sostenendo un numero limitato di operatori, in modo da non ottengono intimiditi. inoltre, è lo stesso una volta implementato un tavolo.