Routine für Lösg. math. Funktionen: Brauche Idee oder Vorschlag (page 3) (C und C++)

lichtkind

2004-05-06 20:40

User since
2004-03-22
5701 articles
ModeratorIn + EditorIn

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

Code: (dl )

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

Tutorien in der Wiki, mein zeug:
kephra, baumhaus, garten, gezwitscher

Es beginnt immer mit einer Entscheidung.

lichtkind

2004-05-07 00:11

User since
2004-03-22
5701 articles
ModeratorIn + EditorIn

@janek falls du heute nicht mehr willst,
bin ab morgen im ausland also nur über mail zu erreichen

Tutorien in der Wiki, mein zeug:
kephra, baumhaus, garten, gezwitscher

Es beginnt immer mit einer Entscheidung.

janek

2004-05-07 02:04

User since
2004-02-02
17 articles
BenutzerIn
[default_avatar]

danke lichtkind. ich bin leider erst jetzt wieder da.
Ich werde mir das ganze in Ruhe anschauen und morgen versuchen in Code zu packen.

Ich hoffe es geht für Dich in Urlaub... wie lange denn überhaupt?

Wenn ich nicht mehr weiter weiß, löcher ich dich mit Fragen per Mail.

Ansonsten nochmals vielen Dank für deine Hilfe und viel Spaß -hoffentlich- im Ausland.

Crian

2004-05-07 18:03

User since
2003-08-04
5873 articles
ModeratorIn

Verlang einfach die logische Eingabe ;)

Dann wird aus

((1+5)+(1-2)*5)+1

+ + + 1 5 * - 1 2 5 1

*gg

Viel Spaß damit, diese Notation kommt ohne Klammern aus, da man zu jedem Operator weiß wieviele Stellen er hat. Intern würd ich auf jeden Fall versuchen, in diese Form zu wandeln.

Lustiger Weise hatten wir diese in Logik / Rekursionstheroie (reine Mathe) ziemlich am Ende zu fassen. Es ist halt die eigentlich viel natürlichere Form, wir sind nur "unsere" Form gewohnt.\n\n

s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite

Ishka

2004-05-07 18:05

User since
2003-08-04
771 articles
HausmeisterIn

mist - nicht geschaut, welches Forum das hier ist..\n\n

sub z{if(@_){1while$x[$k=rand 10];t($t=$x[$k]=1)}print map"$z[$x[$_]]$_".($_%3?
"":"\n"),1..9}sub t{$j=0;$x[$_+1]==$t&&($j+=2**$_)for 0..8;z,die"Gewinner $z[$t]
"if grep$_==($j&$_),7,56,73,84,146,273,292,448;z,die"Gleichstand\n"if@x>9&&!grep
!$_,@x}@x=4;@z=qw{. [ (};z$^T&1;while(<>){next if$_>9||$x[$_];t$t=$x[$_]=2;z 1}

Ronnie

2004-05-07 18:24

User since
2003-08-14
2022 articles
BenutzerIn
[default_avatar]

[quote=Crian,07.05.2004, 16:03]+ + + 1 5 * - 1 2 5 1[/quote]
Der glückliche Besitzer eines HP48 erkennt freudig die UPN/RPN.

Crian

2004-05-07 20:11

User since
2003-08-04
5873 articles
ModeratorIn

OT: Ist das ein HP Taschenrechner? So einen hatte ich auch mal, mit roten Leuchtziffern und er war in geringem Maße programmierbar, weiß aber die Nummer nicht mehr. Eines Tages rührte sich einfach nichts mehr und ich musste einen anderen anschaffen.

s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite

Ronnie

2004-05-07 21:11

User since
2003-08-14
2022 articles
BenutzerIn
[default_avatar]

@crian: Ja, der ist von Hewlett Packard - leider ohne rotleuchtende Ziffern - aber mit umgekehrter polnischer Notation. Diese Geräte gibt es heute noch z.B. bei Dynatech, haben aber zu Unrecht den Ruf schwer bedienbar zu sein. Die heutigen Geräte haben wahlweise algebraiche oder UP-Notation (auf die ich sehr viel Wert lege).

Crian

2004-05-08 04:52

User since
2003-08-04
5873 articles
ModeratorIn

die rotleuchtenden Ziffern stammten aus der pre-LCD-Zeit und verbrannten ordentlich Batterien ;)
Interessant, dass es solche Rechner noch gibt :-)

s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite

janek

2004-05-08 14:50

User since
2004-02-02
17 articles
BenutzerIn
[default_avatar]

Quote
Verlang einfach die logische Eingabe

Dann wird aus

((1+5)+(1-2)*5)+1

+ + + 1 5 * - 1 2 5 1

Was meinst Du denn mit der logischen Eingabe? Kannst Du mir vieleicht das mit +++15*-1251 erklären?