String mit mathmatischem Inhalt analysieren

[muyao]

Guten Abend zusammen:)

ich habe eine kleine Frage bei meiner HA und habe schon im Internet durchgesucht, leider nichts zu finden
Ich möchte aus einem beliebigen String einen mathematischen Term bilden und diese berechnen.

a='(1*1+1)*(1+1)'
Am Ende will ich die Ergebnis bekommen, nämlich ist hier 4. Ich habe eine Idee, dass man mit dem Int Befehl ein String nach Zahlen umwandeln kann.
Das Problem ist dabei die Übergabe der mathematischen Operatoren. Hier im Beispiel wird int(+) "invalid literal for int() with base 10: '+' " übergeben, welshalb solve sich auch nicht berechnen lässt.

Vielleicht kann jemand mir einige Hinweise geben, wie man das Problem lösen kann?
Ich bedanke mich im Voraus für eine Antwort.

Viele Grüße
Muyao

[Sirius3]

@muyao: so eine Arbeit entsteht ja nicht einfach so. Was hast Du schon gelernt? Was dürft ihr benutzen? Weißt Du was ein Parser ist? Wie viel Zeit ist dafür geplant? Du kannst Dich ja mit KunoZ zusammentun.

[MagBen]

Kennst Du die Python Funktion eval?

Code: Alles auswählen

a = eval('(1*1+1)*(1+1)')
print a

[snafu]

Jepp, das war bestimmt das Ziel für eine Programmieraufgabe über die Weihnachtsferien, dass man eval() benutzt...

[MagBen]

Jepp, das war bestimmt das Ziel für eine Programmieraufgabe über die Weihnachtsferien, dass man eval() benutzt...

Du meinst es war keine effiziente, sondern eine akademische Lösung gefragt?

[snafu]

Jepp, das war bestimmt das Ziel für eine Programmieraufgabe über die Weihnachtsferien, dass man eval() benutzt...

Du meinst es war keine effiziente, sondern eine akademische Lösung gefragt?

Davon kann man bei Aufgaben (vermutlich) für die Uni stark ausgehen. Zumal jeder halbwegs begabte Programmierer weiß, dass eval() aus Sicherheitsgründen nicht zum Evaluieren von Mathe-Formeln genutzt werden soll. Es ist einzig dazu da, einen Code 1 zu 1 auszuführen mit all den Risiken, die das mit sich bringen kann.

[muyao]

@Sirius3: Tatsächlich haben wir Python nur weniger als 3 Monaten gelernt, deswegen beherrsche ich jetzt nicht so viele effiziente Python Befehle Leider ist es einfach so...Ich bin auch nicht so begabt beim Programmieren, nur benutze die Basic Sachen, die ich gelernte habe :K z.B. if elif else; Schleifen; Funktionen; Stringoperationen; Typumwandelung; String mit split. join; Methode für Listen; Tupel Mengen Built in Funktion usw.... Wir müssen die HA vor 1.1 abgeben.

@MagBen: Danke für deine Antwort! Das sieht so effizient aus Aber ich glaube, dass wir keine Funktion außer der Folien benutzen dürfen
Trotzdem Danke und frohe Weihnachten!

@snafu: Ja, du hast Recht studiere jetzt mit viel Stress. Die Sache ist einfach so, für die begabten Programmierer, es kostet vielleicht nur halbe oder eine Stunde, meine HA zu lösen. Aber für mich, ganzen Tag vor meinem Laptop zu sitzen und kriege trotzdem nichts naja, maybe Some People are Born to programming，but not me

[muyao]

"In dieser Aufgabe soll ein Ausdruck analysiert und ausgewertet werden. Dabei wird ein Ausdruck als String gespeichert. Dieser soll bei der Auswertung in eine ganze Zahl konvertiert werden. Beim Auswerten ist die Klammerung, sowie Punkt vor Strich zu beachten.
Wir definieren korrekte Ausdrücke und ihre Tiefe rekursive. Ein Ausdruck w0, der aus genau einer (ganzen) Zahl besteht, ist korrekt und hat Tiefe t0=0. Wenn w1 und w2 korrekte Ausdrücke der Tiefe t1 bzw. der Tiefe t2 sind, dann sind
w1+w2 und w1*w2 korrekte Ausdrücke der Tiefe max(t1,t2)
(w1),[w1] und {w1} korrekte Ausdrücke der Tiefe t1+1
Schreibe eine Funktion parser(String), die einen Ausdruck analysiert.

Code: Alles auswählen

parser('1+(1+1)*(1+1)')
(5,1)

Nur für lesen, besser meine Frage zu verstehen. Ich weiß, niemand meine HA lösen will

[Sirius3]

@muyao: die Aufgabenstellung verhindert ja schön, dass man »eval« benutzen kann. Welche Gedanken hast Du Dir denn schon gemacht? In welche Teilprobleme muß man das Problem aufteilen?

[BlackJack]

@Sirius3: Naja, sie verhindert es nicht wirklich, man kann es ja auch aufteilen in den Teil den `eval()` abdeckt und den wo man Klammern zählen muss. Ob man dafür dann Punkte bekommt ist eine andere Frage.

@muyao: Was ist denn auf den Folien so drauf. Kommen dort Begriffe wie Tokenizer, Token, reguläre Ausdrücke, Grammatik, Ableitungsbaum, Parser, recursive descent, … vor? Und wo liegt das konkrete Problem bei der Umsetzung?

[BlackJack]

@muyao: Was sollen in der Aufgabenbeschreibung denn die eckigen und geschweiften Klammern bedeuten?

[Sirius3]

@BlackJack: ich vermute mal, dass die verschiedenen Klammern keine unterschiedliche Bedeutung haben. Um »eval« benutzen zu können, muß mal also den Text durchgehen, Klammern zählen und Umwandeln und hat dann immer noch keine Punkte.

Die Grammatik wurde ja sehr einfach gehalten, da nur +, *, Klammern und Zahlen vorkommen. Das kann man explizit ein 50 Zeilen herunterschreiben, nur mit etwas Stringgefrickel.

[BlackJack]

Nur mal so zum Spass: Sicheres auswerten ohne `eval()` mit Beschränkung auf Zahlen und Grundrechenarten ohne selbst einen Parser schreiben zu müssen:

Code: Alles auswählen

#!/usr/bin/env python
from __future__ import absolute_import, division, print_function
import ast
from operator import add, floordiv, mul, sub
from singledispatch import singledispatch

OP_TO_FUNCTION = {
    ast.Add: add,
    ast.Div: floordiv,
    ast.Mult: mul,
    ast.Sub: sub,
}


@singledispatch
def evaluate(node):
    raise NotImplementedError(repr(node))


@evaluate.register(ast.Num)
def evaluate_num(num):
    return num.n


@evaluate.register(ast.BinOp)
def evaluate_binop(bin_op):
    function = OP_TO_FUNCTION[type(bin_op.op)]
    return function(evaluate(bin_op.left), evaluate(bin_op.right))


def parse(string):
    expression = ast.parse(string, mode='eval')
    return evaluate(expression.body)


def main():
    print(parse('1+(1+1)*(1+1)'))


if __name__ == '__main__':
    main()

Braucht in Python 2.7 den Backport von `singledispatch`. Und hilft nicht beim anderen Aufgabenteil, weil die Klammern natürlich nicht mehr im Ableitungsbaum vorhanden sind.

[muyao]

@BlackJack :Tokenizer, Token, reguläre Ausdrücke, Grammatik, Ableitungsbaum, Parser, recursive descent....habe ich noch nie gehört Ich glaube, wir 'eval' nicht benutzen dürfen. und mit den eckigen und geschweiften Klammern, vermute ich, sie keine unterschiedliche Bedeutung haben, weil im Beispiel ist es so:

Code: Alles auswählen

parser('{1+1}*[1+1]+38')
(42,1)
parser('[{1}+5]*({2}+[{1*(3)}+2])')
(42,4)

[muyao]

@Sirius3: Eigentlich habe ich schon am Anfang Problem gehabt... ich habe doch keine Idee, wie man aus dem String die Zahlen und Operatoren auskriegen kann mit int Befehl für jede Element im String? Aber der Befehl funktioniert nicht für Operatoren :K

[Sirius3]

@muyao: Du kannst nicht erwarten, dass auf wundersame Weise eine Funktion existiert, die genau das tut, was Du willst und Deine Aufgabe nur noch ist, diese Funktion zu finden. Programmieren bedeutet, eine Problem so in Teile zu Teilen, dass es für diesen Teil eine Lösung schon existiert. In Deinem Fall mußt Du den String in Klammern, Operatoren und Ziffernfolgen aufteilen und für das Problem, einen String mit Ziffern in eine Zahl zu verwandeln, kennst Du »int«. Wie würdest Du »[{1}+5]*({2}+[{1*(3)}+2])« mit Papier und Bleistift berechnen?

[muyao]

@Sirius3 Danke:)es ist ein bisschen klar geworden mit deinen Hinweise. Ich überlege gerade jetzt, wie ich die Klammern, Operatoren und Ziffernfolge aufteilen kann wenn ich die Gleichung jetzt am Hand hätte, dann würde ich sagen, dass wir zuerst die Zahl aus den nächsten Klammern ausklammern, in diesem Fall sind {1},{2} und(3). Jetzt haben wir [1+5]*(2+[{1*3}+2]), dann rechnen wir die Zahlen, die es dazwischen keine Klammer gibt, [6]*(2+[{3}+2]).Werden die Zahlen wieder aus den nächsten Klammern ausgeklammert, kriegen wir jetzt 6*(2+[3+2]) .Dann berechnen wir noch einmal, 6*(2+[5]) . Mit den beiden Schritten sieht es folgende aus, 6*(2+5) 6*(7) 6*7 42
Ich habe das Gefühl, die Zwei Schritte kommen stimmt im Programm vor Aber mehr exact kann ich jetzt leider nicht......

[snafu]

Hier mal ein billiger selbst gebastelter Tokenizer, der mit Unterlisten für die geklammerten Terme arbeitet, indem er sich selbst aufruft:
http://pastebin.com/rJ6TxVvS

Ich habe darauf verzichtet, eigene Klassen für die verschiedenen Token-Typen zu definieren, sondern beschränke mich auf die Rückgabe von Integern zum Repräsentieren der Zahlen sowie Strings für die Operatoren. Darauf aufbauend könnte man jetzt natürlich die mathematische Logik zum Auswerten der Ausdrücke implementieren. Das Erkennen von ungleichmäßigen Klammerpaaren ist auch noch nicht enthalten.

EDIT: Die Bezeichnung Stackfür die Hilfsklasse ist auch nicht wirklich passend. Mir fiel dafür nichs besseres ein.

EDIT²: Der sogenannte Stack heißt jetzt PushbackIterator und die Klasse basiert auf collections.Iterator.
http://pastebin.com/aUd9naBi

[Sirius3]

@snafu: Deinem Tokenizer ist es egal, ob schließende Klammern fehlen; außerdem macht er mehr, als ein ›normaler‹ Tokenizer tut: er baut schon einen halben Baum auf.

[snafu]

Der Code erhebt keinen Anspruch darauf, ein reiner Tokenizer zu sein. Wahrscheinlich ist es eher ein Parser. Das mit den Klammern hatte ich ja bereits erwähnt. Der Code war als erster Ansatz gedacht wie man es machen könnte.