Schreiben String Bewertungsfunktion

Question

Ich versuche, eine String Bewertungsfunktion heißt

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

The operators are + -/and * 

Meine anfängliche obwohl reguläre Ausdrücke zu verwenden war zu schreiben, Operatoren und Ziffern, da diese sammeln können angepasst werden. Und dann, nachdem Sie diese Informationen gefunden haben, finden Sie irgendwie eine Möglichkeit, /* Ove -+ Betreiber zu priorisieren.

Hier ist, wie ich begann:

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

Jetzt kann ich eine andere Methode schreibt die Ziffern mit der gleichen Logik zu extrahieren.

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

Jetzt ist der Teil, wo ich feststecke. # 1 Dieses obige Verfahren nicht auf dem dritte Beispiel:

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

Und das # 2 Auch wenn ich die vorherigen Beispiele versuchen, ich kann es nicht herausgefunden, wie man sich in der richtigen Reihenfolge zu setzen.

Bin ich überhaupt auf dem richtigen Weg, hat jemand einen nützlichen Ratschlag, bitte teilen?

Answer 1

Ich schrieb hier etwas ... lassen Sie uns sagen, dass schnell & schmutzig ist eine Untertreibung ...
Auf jeden Fall sollten Sie es nicht verwenden "wie es ist". Es muss „Fixierung“ - das Lesen der Zahlen/Arithmetik-Operationen sollte mit StringTokenizer getan werden - aber ich werde die technisch Sie überlassen;)

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

Sie möchten eine operator precedence parser. Dies ist ein sehr gängiger tabellenbasierter Parser, der genau das macht, was Sie wollen. Im Grunde vergleichen Sie den zu scannenden Bediener mit demjenigen, der sich oben auf einem Stapel befindet, und wählen Sie, den Stapel zu reduzieren (dh, führen Sie die Berechnungen durch und schieben Sie das Ergebnis zurück auf den Stapel), oder drücken Sie den Operator.

Als zusätzlichen Bonus, OPPs sind einfach und Spaß zu schreiben. Sie können Unterstützung für Klammern usw. mit wenig zusätzlichem Aufwand hinzufügen.

bearbeiten - Ich habe gerade gelesen, dass Wiki-Artikel. Es ist schrecklich.

Finden Sie weitere Beispiele für diesen Typ von Parser.

Edit 2 -

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

This one is pretty good.

Und denken Sie daran, Sie sind eine kleine Anzahl von Operatoren unterstützt, so werden nicht eingeschüchtert. Außerdem ist es gleich, wenn Sie eine Tabelle implementieren.