Rechnungsparser (Grundrechenarten + Klammern)

Wolle92 · Verfasst: So 18.01.09 22:46

Hallo,

ich brauche einen kleinen Parser für Grundrechenarten und Klammern...
Ich habe zwar den ein oder anderen Ansatz gehabt, letztendlich ist doch ein anderes Ergebnis rausgekommen...

Ich hätte gerne nur Hilfe, nicht direkt einen kompletten Parser, man will ja was dabei lernen...

Grüße,
Wolle

PS: Das ganze wird in PHP realisiert...

_________________
1405006117752879898543142606244511569936384000000000.

Hidden · Verfasst: So 18.01.09 23:31

Hi

So ganz klar ist noch nicht, wo eigentlich das Problem liegt

Ich gehe Mal davon aus, es liegt am Ansatz.

Record mit 2 pointern auf neue records oder zahlenwerte/variablen + benötigter Operator p1 [* / + -] p2
Parse-Methode: Am Anfang Rekursiv für Strings in unterklammern aufrufen und den zurückgegebenen record an der Stelle Einsetzen
ansonsten stets einfach operator und record der nächsten zahl einspeichern

Wie das mit Rekursion und records in php aussieht, weiß ich nicht :nixweiss:

, gehe aber Mal davon aus, das ist für dich kein Problem?

mfG,

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)

jfheins · Beiträge: 918 Erhaltene Danke: 158 Win 10 VS 2013, VS2015

Ein Parser besteht zuersteinmal aus einem sog. Tokenizer.

Dieser nimmt den String und zerteiltz ihn in seine logischen Elemente. Also bei einem Parser, der z.B. Mathematische Ausdrücke ausrechnen soll, trennt er Operatoren von Variablen und Zahlen.

Danach kannst du einen Baum aufbauen, der den Ausdruck repräsentiert.

Hier kommt die Operatorenrangfolge ins Spiel, denn Operatoren, die "schwach" sind werden zuerst behandelt.

Wenn du den Baum hast, kannst du diesen sehr schnell ausrechnen. Falls du Variablen drinhattest (Y oder Pi oder so) setzt du die erst hier ein. Falls sich dein X ändert, kannst du den Ausdruck schnell berechnen, ohne ihn nochmal Parsen zu müssen.

Wenns aber nur um ein mal geht, ist aber die Methode mit der rekursiven Funktion einfacher

miniC# · Beiträge: 75 Wiin XP Home C# VS Express 2008

habe vor paar wochen grade einen geschrieben zum einstieg in c#. sehr schöne quelle dazu : Grammars and parsing with C# 2.0. behandelt eine vereinfachte form des ebnf-parsers.

gruß,
miniC#

_________________
Zitat MDSN : " ... C# (gesprochen: "si scharp") "

Wolle92 · Verfasst: Mo 19.01.09 18:52

Hab mal angefangen mit parsern, dachte mir: "zuerst einmal die Klammern erkennen, die dann ausgerechnet werden"...
Gibt aber nen Problem bei verschachtelten Klammern:

Funktion:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:

function parse($input, $dept = 0){
  preg_match_all('/\(([\d\+\-\*\/\(\)]*)\)/',$input,$matches,PREG_SET_ORDER);
  foreach($matches as $match){
    $input = preg_replace('/'.preg_quote($match[0]).'/',parse($match[1],$dept+1),$input);
  }
  return '{p'.$dept.'}'.$input.'{/p'.$dept.'}';
}

Eingabe:

markieren

Quelltext

1:	20+10(2+3)+(200(2-1))

Ausgabe:

markieren

Quelltext

1:	{p0}20+10{p1}2+3)+{p2}200(2-1{/p2}{/p1}{/p0}

Sollte aber sein:

markieren

Quelltext

1:	{p0}20+10{p1}2+3{/p1}+{p1}200{p2}2-1{/p2}{/p1}{/p0}

Mit U hab ichs schon versucht, nur wird das auch nichts...

Edit: Merke grade, das es kein Problem mit verschachtelten, sondern mit aneinandergereihten Klammern ist... Das könnte man mit U beheben, dann gäbs nen Problem bei den verschachtelten :nut:

_________________
1405006117752879898543142606244511569936384000000000.

Wolle92 · Verfasst: Mo 19.01.09 21:23

So, habs jetzt, verschachtelte Klammer, +,-,*,/ und ^...

Das mit den Klammern hab ich gelöst, indem ich nur die innersten Klammern raussuche, ausrechne und ersetze...
Punkt-vor-Strich-Rechnung ist auch drin

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:

function parse($input){
  while(preg_match('/\(([\d\+\-\*\/\^]*)\)/',$input,$match)){
    $input = preg_replace('/'.preg_quote($match[0]).'/',calc($match[1]),$input);
  }
  return calc($input);
}

function calc($input){
  $input = preg_replace('/(\+|\-|\*|\/|\^|\d+)/',' $1 ',$input);
  $input = preg_replace('/ {2,}/',' ',$input);
  $input = trim($input);
  
  $expr = preg_split('/ /',$input);
  if(preg_match('/\d+/',$expr[0]) && preg_match('/\d+/',$expr[count($expr)-1]) && ((count($expr) % 2) == 1)){
    if(count($expr) == 1) return $expr[0];
    //first, parse all exponents
    $i = 1;
    while($i < count($expr)){
      if(preg_match('/\^/',$expr[$i])){
        $tmp = getResult($expr[$i-1],$expr[$i],$expr[$i+1]);
        array_splice($expr,$i-1,3,array($tmp));
      }
      else $i += 2;
    }
    //after that, check, if only one item left in the array
    if(count($expr) == 1) return $expr[0];
    //then, parse all * and /
    $i = 1;
    while($i < count($expr)){
      if(preg_match('/(\*|\/)/',$expr[$i])){
        $tmp = getResult($expr[$i-1],$expr[$i],$expr[$i+1]);
        array_splice($expr,$i-1,3,array($tmp));
      }
      else $i += 2;
    }
    //then + and -
    $i = 1;
    while($i < count($expr)){
      if(preg_match('/(\+|\-)/',$expr[$i])){
        $tmp = getResult($expr[$i-1],$expr[$i],$expr[$i+1]);
        array_splice($expr,$i-1,3,array($tmp));
      }
      else $i += 2;
    }
    return $expr[0];
  }
}

function getResult($first, $operator, $last){
  switch($operator){
    case '+': return $first + $last;
    case '-': return $first - $last;
    case '*': return $first * $last;
    case '/': return $first / $last;
    case '^': return pow($first, $last);
  }
}

hab nen bisschen hier gespickt

_________________
1405006117752879898543142606244511569936384000000000.

Kha · Verfasst: Mo 19.01.09 21:36

Wenn dir das reicht, dann gut. Solltest du aber etwas mehr Performance brauchen (oder Fehlermeldungen, sollen manchmal ganz nützlich sein

), würde ich einen einfachen Recursive Descent Parser vorschlagen. Dürfte nicht viel länger als dein Code sein, aber eindeutig lesbarer :zwinker:

.

_________________
>λ=

Wolle92 · Verfasst: Mo 19.01.09 21:52

der wird ja noch auskommentiert, dann ist der lesbar

Trotzdem interessiert: was ist nen Recursive Descent Parser?

Edit: Auf die (also diese, nicht jede) Performance kann ich bei ner Internetseite verzichten, das merkt man nicht wirklich... noch weniger, als bei Windoof-Programmen...

_________________
1405006117752879898543142606244511569936384000000000.

miniC# · Beiträge: 75 Wiin XP Home C# VS Express 2008

Wolle92 hat folgendes geschrieben :

Trotzdem interessiert: was ist nen Recursive Descent Parser?

lies mal die pdf , die ich weiter oben gepostet habe

ist scheinbar für erstsemester gedacht, war ne tolle U- und S-Bahn lektüre für einen mathematsichen laien wie mich

_________________
Zitat MDSN : " ... C# (gesprochen: "si scharp") "

Wolle92 · Verfasst: Di 20.01.09 12:27

werds mir mal angucken, bin aber nicht erstsemester sondern 11. Klasse

Auch wenn ich Info + Mathe LK wählen werde

_________________
1405006117752879898543142606244511569936384000000000.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme