wenn das eine pascal unit wäre ......
ne hab die löung jetzt komplett
meine lösung ist sicher nicht balanced aber ich habs jetzt fast ganz raus
Type KnotenPointer = ^Knoten;
Knoten = Record
Links, Rechts,Oben : KnotenPointer;
Wert : Integer;
Operator : Char;
End;
und eine tabelle der operator vertigkeiten
3 = (
2 * \
1 + -
ein knoten mit einer zahl hat den operator =
ist der nächte oberator in der gleichen klammer höher oder gleich wertig gibts nen links rot insert ansonst rechts rot insert und die evaluierung rekursiev was ja bei den relativ kleinen formeln hier ja noch gut ist
jedes zeichendas eingelesen wird steht für einen neuen knoten (bei zahlen muss man weiter paren weil sie ein element sind das über mehrere zeichen gehen könnte) das schwerste ist es diesen neuen knoten in den baum ausbalanciert einzufügen das selbst gleichberechtigte oprationen verschachtelte strukturen produzieren können muss ich noch ausknobeld wie ich das mit den klammern mache
( ist ein platzhalterknoten damit die klammerzu es wiederfindet.
1.
-> (
2
(
/
-> (
3.
(
/
(
/
-> 1
4.
(
/
(
/
-> +
/
1
5.
(
/
(
/
-> +
/ \
1 5
6.
(
/
->
/
+
/ \
1 5
7.
(
/
-> +
/
+
/ \
1 5
8.
(
/
+
/ \
+ ( <=
/ \
1 5
9.
(
/
+
/ \
+ (
/ \ /
1 5 1 <=
10.
(
/
+
/ \
+ (
/ \ /
1 5 - <=
/
1
11.
(
/
+
/ \
+ (
/ \ /
1 5 - <=
/ \
1 2
12.
(
/
+
/ \
+ <=
/ \ /
1 5 -
/ \
1 2
13.
(
/
+
/ \
+ * <=
/ \ /
1 5 -
/ \
1 2
14.
(
/
+
/ \
+ * <=
/ \ / \
1 5 - 5
/ \
1 2
15.
<=
/
+
/ \
+ *
/ \ / \
1 5 - 5
/ \
1 2
16.
+ <=
/
+
/ \
+ *
/ \ / \
1 5 - 5
/ \
1 2
17.
+ <=
/ \
+ 1
/ \
+ *
/ \ / \
1 5 - 5
/ \
1 2
das ausrechnen dieser struktur geht dann mit evalnode(root)
und die procedur evalnode macht folgendes:
function evalnode (node nodepointer)
begin
case node->operator
"=" : zahl = node->wert;
"+" : zahl = evalnode(links) + evalnode(rechts);
"-" : zahl = evalnode(links) - evalnode(rechts);
"*" : zahl = evalnode(links) * evalnode(rechts);
"/" : zahl = evalnode(links) / evalnode(rechts);
else zahl = 0
endcase
return zahl;
end function
das erzeugen eines nodes geht so logisch:
1. neuen node erzeugen
2. ist das item eine klammerzu gehe nach oben bis zur nächsten klammer auf und lösche dort den operator; break;
3. wenn der aktuelle geparste item eine zahl ist
setz den operator auf = und trage in den wert die zahl ein ansonsten setzt operator = aktuelle item und den wert=0;
4. ist der aktuelle knoten leer trage dort die werte ein ansonst:
5. die priorität des aktuellen knoten ermitteln und die priorität des neuen knoten anhand der tabelle oben
6. hat der neue knoten eine höhere priorität füge ihn rechts(unten) ein hat er eine niedriegere setze den neuen knoten an die aktuelle stelle und füge den alten links(unten an)
das ist schon alles\n\n
<!--EDIT|lichtkind|1083873377-->