algoritmus na vyriešenie mat. výrazu

[Don Ferignon]

Práve riešim vyhodnotenie mat. výrazu zo stringu. Výraz obsahuje iba zátvorky a +,-,*,/.
Vedel by mi niekto poradiť nejakú elegantnú rekurziu ?

btw riešim to v jave.

[galen]

skus tento parser, a pripadne sa pohraj so zdrojakmi - vysekaj co potrebujes
http://sourceforge.net/projects/jep/

[Don Ferignon]

uf, tak to je poriadne masívna knižnica
Kým by som v tom našiel tento konkrétny algoritmus tak by som zošedivel. Ale ďakujem.
Skúsme na to dojsť spoločne
Zatiaľ ma napadlo niečo takéto :

-najprv prejdem výraz či neobsahuje nepovolené znaky a či nemá rôzny počet otvorených a zatvorených zátvoriek (to ešte pred algoritmom). Ak áno, koniec.

algoritmus:
-ak obsahuje zátvorky, výraz rozdelím tam kde je prvá otvorená zátvorka po ďalšiu zatvorenú (ak by bola medzi nimi ďalšia otvorená, tak až po druhú, atď) - spustím pre každý rekurzívne túto funkciu
-ak obsahuje delenie/násobenie, výraz rozdelím tam kde je prvé delenie, alebo násobenie a rekurzívne vyhodnotím oba stringy
-ak obsahuje sčítanie/odčítanie, stringy rozdelím tam kde je prvé sčítanie alebo odčítanie a rekurzívne vyhodnotím oba stringy
-ak je string číslo, vráť jeho hodnotu

Problém mám hlavne so zátvorkami, konkrétne s vnorenými výrazmi.
Okrem toho by to mohlo fungovať, nie ?

[pEpinko]

No v principe je ten tvoj pristup dobre, akurat je strasne tazkopadny. Prave take vnorene vyrazy by sa robili zle. Da sa to ale tazko.

Podla mna je to najlepsie urobit takto:

1. Tokenizacia stringu na cisla zatvorky a operacie.
2. Pomocou LL parsera urobim strom vyrazu.
3. Strom vyrazu vyhodnotim.

Najtazsi je asi krok 2, aby si ho urobil musis vediet aku ma ten tvoj vyraz gramatiku a co je to syntakticky parser... Hm... asi som ti velmi nepomohol. Nicmenej minimalne tu tokenizaciu si urob urcite.

[faugusztin]

Vsak si najdi kniznicu, naco riesit nieco co existuje.

http://www.bestcode.com/html/jbcparser.html

[Don Ferignon]

Vsak si najdi kniznicu, naco riesit nieco co existuje.

http://www.bestcode.com/html/jbcparser.html

Toto nie je open source. Platiť za to predsa nebudem.
To čo postoval galen je zas obrovské (950kB čistého kódu, tipujem tak 50k riadkov).

pepinko:
O LL parseri počujem prvý krát.

Tokenizáciu tiež neviem presne ako by som urobil.