Mam problem... Potrzebuje program, który oblicza wartość wyrażenia matematycznego w stringu (np.: 1,98*(12+4) ).Probowalem taki [glowa] napisać, ale podaje głupie wyniki w niektórych przypadkach.
Prosiłbym o podesłanie wyżej opisanego programu [email protected]
Z góry thx.
0
0
[niewinnosc]
Prosiłbym o podesłanie wyżej opisanego programu [email protected]
He he.
Nie wiem czy zdajesz sobie sprawę z tego, że napisanie takiego programu to kawał roboty. Prawdę mówiąc, nie sądzę żeby ktokolwiek napisał go dla Ciebie za darmo.
Możliwe są dwa podejścia:
-
Przeładowanie operatorów. ( Dostępne w C++ ) Każdy średnio-zaawansowany programista powinien sobie poradzić z napisaniem takiego programu korzystając z przeładowania operatorów arytmetycznych względem zmiennych typu String. ( Obecność tego mechanizmu jest prawdopodobnie największą siłą C++ )
-
Zdefiniowanie operacji arytmetycznych, określenie ich priorytetów, napisanie interpretatora i odkładanie coraz to prostszych wyrażeń na stos (tzw. "Dziel i zwyciężaj), całość rekurencyjna (jest to po prostu najbardziej naturalna i czytelna obsługa LIFO, czyli "last in first out"), oczywiście dochodzą do tego zagadnienia dynamicznego przydziału pamięci, (bo przecież nie wiemy z góry, na ile członów rozpada się wyrażenie). Już jest źle ? Będzie gorzej - obecność nawiasów komplikuje to wszystko, gdyż z punktu widzenia interpretatora wymagają one osobnego potraktowania.
Mam nadzieję że odrobinę przybliżyłem Tobie złożoność tego pozornie niewinnego problemu.
Pozdrawiam.
0
Mam nadzieję że odrobinę przybliżyłem Tobie złożoność tego pozornie niewinnego problemu.
Tym niemniej kiedys na forum ktos sie kiedys chwalil, ze napisal taki program. Nie pamietam kto, no i program pewnie byl jakos ograniczony, po problem na pewno nie jest banalny.
--
Pawel {Delphi 6 Personal}
Po pierwsze: naciśnij F1
0
Hej pq ! :-)
W odpowiedzi na twojego posta mogę powiedzieć że to bardzo prawdopodobne.
Chciałem jedynie pokazać, że nie istnieje coś takiego jak prosta konwersja wyrażenia zapisanego w formie literału na wyrażenie w formie arytmetycznej.
Niemniej napisanie takiego programu nie jest niemożliwe. W gruncie rzeczy implementacja sprowadza się to do rozpisania rekurencyjnie zagnieżdżonego Interpretatora. (gdybyśmy użyli rekurencji to prawdopodobnie za cenę szybkości programu odpada problem dynamicznego przydzielania pamięci, a nie jest to wygórowana cena za taki towar )
Naprawdę da się to zrobić, aczkolwiek wymaga to trochę pracy. (chyba że piszemy w C++, wtedy można to zrobić w jakieś 40 minut).
Pozdrawiam.
0
Jak się nie mylę to w przykładach tu na stronie jest zrobione proste dodawanie!. Ja napisałem interpreter, pozwalający w postaci łancucha wprowadzić strukturę elektrycznej sieci zastępczej (ileśtam rezystorów, kondensatorów itp w połączeniach równoległych i szeregowych) procedura była rekurencyjna i zajmowała ze 50 lini, ale czas na debugi to około 2 tygodni dobrego gmerania i tropienia wyjątków.
0
He he.
Nie wiem czy zdajesz sobie sprawę z tego, że napisanie takiego programu to kawał roboty. Prawdę mówiąc, nie sądzę żeby ktokolwiek napisał go dla Ciebie za darmo.
I tu się mylisz. Prosty kalkulator umożliwiający operacje:
+, -, *, / przedstawił już tutaj (chyba) Sheitar i RFL.
Ja też brałem się za takie coś (fragmenty ich kodu dot. operacji na nawiasach ściągnąłem) i napisałem sobie prosty kalkulator obsługujący:
+, -, *, /, mod, div, not, and, or, xor i ^ (potęgowanie).
Oprócz tego próbowałe rozszerzyć o kilka predefinowanych funkcji (sin i cos). Niestety ta ostatnia operacja doprowadziła do pewnych problemów, które występowały w kalkulatorze RFLa, a ja usunąłem (np. podwójny '-' czy wielokrotne znaki białe). Nie kończyłem tego, bo właśnie dorwałem się do kompilatorów i tu mam bardzo ciekawe algorytmy. Zamierzam umieścić tu artykuł na ten temat, więc Paweł, jezeli nie potrzebujesz tego na gwałt, to poczekaj kilka dni (do niedzieli), a umieszczę tu artykuł wraz z kodem (jeżeli potrzebujesz natychmiast to mogę przesłać ten wcześniejszy kalkulatorek - jak tylko wrócę do stanu działającego, czyli bez funkcji).
- Przeładowanie operatorów. ( Dostępne w C++ ) Każdy średnio-zaawansowany programista powinien sobie poradzić z napisaniem takiego programu korzystając z przeładowania operatorów arytmetycznych względem zmiennych typu String. ( Obecność tego mechanizmu jest prawdopodobnie największą siłą C++ )
W Delphi przeładowanie operatorów występuje tylko w typie Variant. Ale tu męczenie się z przeładowaniem operatorów to zbędna robota.
- Zdefiniowanie operacji arytmetycznych, określenie ich priorytetów, napisanie interpretatora i odkładanie coraz to prostszych wyrażeń na stos (tzw. "Dziel i zwyciężaj), całość rekurencyjna (jest to po prostu najbardziej naturalna i czytelna obsługa LIFO, czyli "last in first out"), oczywiście dochodzą do tego zagadnienia dynamicznego przydziału pamięci, (bo przecież nie wiemy z góry, na ile członów rozpada się wyrażenie). Już jest źle ? Będzie gorzej - obecność nawiasów komplikuje to wszystko, gdyż z punktu widzenia interpretatora wymagają one osobnego potraktowania.
Zgadza się, rekurencyjna metoda jest najłatwiejsza. Ale pomysł wprowadzony przez Sheitara i RFLa w sprytny sposób pozbywa się konieczności używania stosu i usuwa praktycznie wszystkie problemy z nawiasami. (a tak przy okazji można to też zrobić w wersji iteracyjnej - znacznie szybszej i odporniejszej na sporo błędów)
Mam nadzieję że odrobinę przybliżyłem Tobie złożoność tego pozornie niewinnego problemu.
Nie taki złożony, jeżeli to mają być proste wyrażenia matamatyczne :)
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667
0
Thx za probe pomocy, ale rozwiazalem problem :) (w niecały tydzień) Chociaz troszke wolny, ale wystarczający...
0
Stos i odwrotna notacja.
Jak to zrobiłeś, to jestem ciekaw czy to obliczy:
-(-(((1)-)), chodzi mi czy sprawdza zgodność nawiasów?
--
Carl Friedrich Gauss(1777-1855) - Niemiec, książe matematyków
0
Stos i odwrotna notacja.
Jak to zrobiłeś, to jestem ciekaw czy to obliczy:
-(-(((1)-)), chodzi mi czy sprawdza zgodność nawiasów?
U mnie wywal błąd przy nieodpowiedniej ilości nawiasów odtwierających i zamykających (czyli tak jak być powinno). Tego nie przepuściłoby nawet z tego powodu, że po '-' brakuje wyrażenia.
A tak w ogóle to ja bym tego nie robił na stos, ale na kolejkę (taki mały szczegół).
Odwrotna notacja? Odwrotna notacja to jest notacja Łukasiewicza (polish notation). Tutaj przydałoby się raczej stosować notację postfixową.
2+34 -> 234+
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667
0
A swoją drogą to jestem NIEZMIERNIE ciekaw jak rozwiazales ten problem panie Pawel200x.5.
Chcialem kiedys napisac program do rysowania wykresow funkcji, ale nie napisalem. Powalil mnie wlasnie ten problem co u Ciebie.
Jak bys byl na tyle mily to wyslij tu na forum ten kod.
0
Wszyscy piszą że to wcale nie jest taki trudny program ... Uwierzę dopiero wtedy, kiedy zobaczę taki na własne oczy (oczywiście idioto odporny), według mnie to minimum 500 linii kodu.
0
Wszyscy piszą że to wcale nie jest taki trudny program ... Uwierzę dopiero wtedy, kiedy zobaczę taki na własne oczy (oczywiście idioto odporny), według mnie to minimum 500 linii kodu.
Po pierwsze: nie istnieje program idiotoodporny (chyba, że nic nie robi pożytecznego)
Po drugie: mój kod zajmuje ok. 370 linijek, przy czym łamie się przy niektórych wyrażeniach (wszystko przez to, że umieściłem w nim obsługę funkcji). Jeżeli przywrócę go do stanu pierwotnego, z obsługą prostych operatorów to sądzę, że obliczy każde poprawne wyrażenie (przy innym wywali błąd, albo padnie).
Po trzecie: znalazłem fajny fragment kodu w książce "Compilers: principles, techniques and tools" i po niewielkim przerobieniu go przedstawię ci. Na 90% powinien poradzić sobie z każdym poprawnym wyrażeniem. Poczekaj przynajmniej do niedzieli (brakuje mi teraz trochę czasu).
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667
0
Po pierwsze: nie istnieje program idiotoodporny (chyba, że nic nie robi pożytecznego)
[niewinnosc]
he he
co ty gadasz stary??
Wpadłem na inny pomysł: czemu by nie zdefiniować abstrakcyjnej klasy "Interpreter" w której można by definiować dowolne operacje opisując dla każdej:
- priorytet operatora
- napis będący symbolem operatora
- ilość argumentów (powiedzmy że trzy+ argumentowych operatorów nie będziemy używać).
Można by potem dziedziczyć po klasie Interpreter, definiować własne operatory (czemu się ograniczać) a całość by się sprowadzała do tzw. atomizacji wyrażenia i odpowiedniej sekwencji (prawdopodobnie rekurencyjnej) wywołań funkcji. Odnoszę wrażenie że analizator zorientowany wyłącznie na proste wyrażenia arytmetyczne to odrobinę za mało, aby można było mówić o pożytecznym narzędziu.
Dryobates, czy ty się na mnie uwziąłeś ? Kiedy widzę z jakim entuzjazmem wytykasz mi błędy, to jestem zażenowany.
0
Rozumiem że napisałeś/liście funkcję/procedurę która jest odpowiednikiem matlabowskiego eval. Bo o to chyba sie rozchodzi.
--
Carl Friedrich Gauss(1777-1855) - Niemiec, książe matematyków
0
Rozumiem że napisałeś/liście funkcję/procedurę która jest odpowiednikiem matlabowskiego eval. Bo o to chyba sie rozchodzi.
Mniej więcej. Ja robię sobie Od razu podłoże pod prosty interpreter. Z mozliwością operacji na zmiennych. Żeby obliczało np. coś takiego:
a := 2+3;
b := 5*3;
c := a+(b-3)*10;
Kapustka: ja się nie uwziąłem, tylko "prostuję" twoje wypowiedzi. W dziedzinie, z której niewiele wiem nie będę Cię poprawiał. Ale jeżeli czegoś jestem pewien to nie pozostawię tego bez odzewu.
A tak przy okazji to możesz zobaczyć dzieło Sheitara i RFLa (choć sypie się przy nadmiarze spacji i podwójnych --)
http://www.4programmers.net/forum/viewtopic.php?id=15981
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667
0
Często wspominasz o książce dedykowanej budowie kompilatora, zgaduję że chodzi o dzieło Ullmana ? (o ile pamiętam "Kompilatory reguły i narzędzia").
0
Często wspominasz o książce dedykowanej budowie kompilatora, zgaduję że chodzi o dzieło Ullmana ? (o ile pamiętam "Kompilatory reguły i narzędzia").
Nie. Co prawda Ullman jest współ autorem.
Tzw. "Dragon Book"
Pełny tytuł:
"Compilers: principles, techniques and tools" - Aho, Sethi, Ullman.
Od czasu do czasu posiłkuję się:
"Algorithms" - Sedgewick (choć to raczej nie na temat kompilatorów, ale jest dział w którym zagadnienia poboczne do kompilatorów są poruszane).
Próbowałem też zdobyć "Modern Compilers Design" (nie pamiętam autora), bo podobno świetna książka. Niestety nie jest to takie proste.
A tak à propos twojego niedowierzania w to, że nie istnieje program idiotoodporny. Takie są prawa Murphy'ego ;) A najgorzsze jest to, że się sprawdzają (kto zostaje beta testerem? Ten kto wyprawia z programem rzeczy, które normalnemu człowiekowi nie przyszłyby do głowy).
A tak przy okazji. To jakie książki o algorytmach byś mi polecił?
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC: #4programmers, warszawa.ircnet.pl (POLNet)
0
Tzw. "dragon book", to jest właśnie ta książka (czyli "Kompilatory, reguły, metody i narzędzia" ostatnio wznowione w serii KI).
Sedgewick - super! Przyjeżdża do Polski w następnym roku i wprost nie mogę się już doczekać jego wykładu w ramach ETAPS'u.
Prawa Murphyego - prawdę mówiąc nie znam ich. Niemniej jestem pewien że program może być idiotoodporny, czyli protestować gdy otrzymuje takie dane których nie może prawidłowo zinterpretować i niekoniecznie musi być bardzo prosty. (w pewnym sensie dobrze napisany kompilator jest właśnie takim złożonym, 100% idiotoodpornym programem).
Uwielbiam książkę "Algorytmika-istota informatyki" autorstwa Davida Harrel'a, aczkolwiek podejrzewam że tak znakomitą lekturę już przeczytałeś. Sporo ciekawych pomysłów jest w "Perełkach oprogramowania" John'a Bentley'a, oraz oczywiście w biblii informatyki, jaką bez wątpienia jest trzytomowa "Sztuka Programowania" (mam trzy tomy w domu i ponownie kupiłem trzy tomy do pracy - i wiecie co? zupełnie nie żałuję). Jeżeli zaś potrzebujesz jakiegoś bardzo konkretnego algorytmu do sprecyzowanego zastosowania to niezastąpionym opracowaniem jest wtedy książka "Wprowadzenie do algorytmów" (nazwa jest odrobinę myląca, gdyż to "wprowadzenie" ma 1000 stron) WNT.
Natomiast o "Modern Compilers Design" nie słyszałem.
Poważnie się zastanawiam, aby zarwać kilka nocy i napisać abstrakcyjną klasę "Interpretator". Ostatnio pisałem wiersz poleceń pewnej konsoli i musiałem budować interpretatora od zera, obecnie buduję bazodanową aplikację zarządzającą biblioteką i ponieważ jest ona osadzona w wierszu poleceń, ponownie muszę pisać interpretator. Rozpisanie uniwersalnego interfejsu staje się powoli koniecznością (po prostu zbyt wiele czasu tracę powtarzając podobny kod).
Daje do myślenia ...
Pozdrawiam
niewyspana Kapustka
0
Kod tej funkcji u mnie zajmuje ok 150 lini i niestety czasem się łamie :(. Nie wiem o jakich metodach mówicie (ucze się dopiero w gimnazjum) i tą funkcjię potrzebowałem do programu (do rysowania) który by obsługiwał skrypt. Udało mi się, chciaż ta funkcja jeszcze nie oblicza takich rzeczy jak funkcje trygonometryczne, ale dorobienie tego to jest 30 min roboty. Nie zrobiłem tego bo nie potrzebowałem. Algorytm po prostu analizuje kolejne znaki. Jeśli jest to liczba to dobisuje ją do tablicy liczb, a jeśli znak to do tablicy znaków. Później po kolei na podstawie znaków i liczb oblicza wartości poszczególnych nawiasów (rekurencja). I tak dopóki nie zostaną żadne nawiasy. A problem priorytetu działań jest rozwiązany w ten sposub że priorytetowe działania bierze w nawias. Sam nie wiem jak to udało mi się napisać :)
0
Tzw. "dragon book", to jest właśnie ta książka (czyli "Kompilatory, reguły, metody i narzędzia" ostatnio wznowione w serii KI).
Ja cytuję tytuł jaki jest w bibliotece. Może to ma takie polskie tłumaczenie (nie widziałem niestety polskiej wersji tej książki).
Sedgewick - super! Przyjeżdża do Polski w następnym roku i wprost nie mogę się już doczekać jego wykładu w ramach ETAPS'u.
W Białymstoku to się na pewno nie pojawi :(
Prawa Murphyego - prawdę mówiąc nie znam ich. Niemniej jestem pewien że program może być idiotoodporny, czyli protestować gdy otrzymuje takie dane których nie może prawidłowo zinterpretować i niekoniecznie musi być bardzo prosty. (w pewnym sensie dobrze napisany kompilator jest właśnie takim złożonym, 100% idiotoodpornym programem).
I takie programy da się wywalić ;)
Uwielbiam książkę "Algorytmika-istota informatyki" autorstwa Davida Harrel'a, aczkolwiek podejrzewam że tak znakomitą lekturę już przeczytałeś. Sporo ciekawych pomysłów jest w "Perełkach oprogramowania" John'a Bentley'a, oraz oczywiście w biblii informatyki, jaką bez wątpienia jest trzytomowa "Sztuka Programowania" (mam trzy tomy w domu i ponownie kupiłem trzy tomy do pracy - i wiecie co? zupełnie nie żałuję). Jeżeli zaś potrzebujesz jakiegoś bardzo konkretnego algorytmu do sprecyzowanego zastosowania to niezastąpionym opracowaniem jest wtedy książka "Wprowadzenie do algorytmów" (nazwa jest odrobinę myląca, gdyż to "wprowadzenie" ma 1000 stron) WNT.
Przyznam się bez bicia, że niewiele książek przeczytałem. Nie stać mnie na kupno tak drogich książek (wspomniane "dragon book" kosztuje jakieś 70$, dzieło Knuth'a chyba jeszcze więcej). Mogę skorzystać tylko tyle co znajdę w wersji elektronicznej w sieci lub w bibliotece (niestety biblioteka uboga i mniej popularne, albo drogie pozycje, są dostępne jedynie w czytelni. Całych dni nie będę przesiadywał w czytelni...)
Poważnie się zastanawiam, aby zarwać kilka nocy i napisać abstrakcyjną klasę "Interpretator". Ostatnio pisałem wiersz poleceń pewnej konsoli i musiałem budować interpretatora od zera, obecnie buduję bazodanową aplikację zarządzającą biblioteką i ponieważ jest ona osadzona w wierszu poleceń, ponownie muszę pisać interpretator. Rozpisanie uniwersalnego interfejsu staje się powoli koniecznością (po prostu zbyt wiele czasu tracę powtarzając podobny kod).
W czym to piszesz? Domyślam się, że raczej nie w Delphi. Właśnie w jednej z niewielu książek jakie mam (jedynej o Delphi) jest taki prosty programik do analizy wiersza poleceń. Jego możliwości można łatwo rozszerzać o nowe przełączniki. Przerobienie tego na obiekt nie powinno sprawić większych problemów...
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC: #4programmers, warszawa.ircnet.pl (POLNet)