itam serdecznie wszystkich programist≤w. W tym artykule chcia│bym przedstawiµ m≤j w│asny prosty algorytm (napisany w Pascalu) obliczania warto╢ci wyra┐enia arytmetycznego ze zmiennej typu string. Powiedzmy, ┐e chcieliby╢my stworzyµ prosty kalkulator, kt≤ry oblicza warto╢µ wyra┐enia. U┐ytkownik powinien wpisaµ ca│e wyra┐enie arytmetyczne (na pocz▒tek ograniczmy siΩ do samych liczb, znak≤w dzia│a±, nawias≤w i jednej zmiennej np. x) a program powinien obliczyµ jego warto╢µ. Wyra┐enie bΩdziemy przechowywaµ w zmiennej typu string. Problem pojawia siΩ w momencie gdy chcemy obliczyµ warto╢µ tego wyra┐enia. Je┐eli u┐ytkownik wpisa│ sam▒ liczbΩ to rozwi▒zanie jest proste - wystarczy u┐yµ standardowej procedury val, kt≤ra przypisze nam odpowiedni wynik. Co jednak zrobiµ gdy we wpisanym wyra┐eniu wystΩpuj▒ znaki dzia│a±? Dla przyk│adu przeanalizujmy prosty przyk│ad, w kt≤rym do obliczenia bΩdzie wyra┐enie:
2 + 2 = ??? (oczekiwany wynik :4)
Algorytm, kt≤ry przedstawiΩ opiera siΩ na rozdzieleniu liczb, znak≤w dzia│a± oraz nawias≤w do trzech osobnych tablic. Zdeklarujmy je:
liczba:array [1..100] of real;
znak:array [1..100] of char;
nawias:array [1..100] of integer;
Wyobra╝ sobie te tablice jako jakie╢ kom≤rki, w kt≤rych co╢ tam siΩ znajduje (liczby, znaki dzia│a± i nawiasy).
Oto przyk│ad jak mog│yby wygl▒daµ takie kom≤rki po roz│o┐eniu naszego wyra┐enia "2+2" :
Aby wykonaµ dzia│anie matematyczne z tablicy znak o indeksie i nale┐y wykonaµ te dzia│ania na elementach tablicy liczba o indeksach i oraz i+1 a nastΩpnie odpowiednio zmodyfikowaµ tablice.
Oto schemat wykonania dodawania dla wyra┐enia 2 + 2 :
Krok 1. Tablica zaraz po roz│o┐eniu wzoru:
Krok 2. Znaleziono znak dodawania (na pozycji i=1) - obliczanie sumy
Krok 3. Wstawienie wyniku sumowania do tablicy liczba na pozycjΩ i+1 (w naszym przypadku na poz. 2)
Krok 4. PrzesuniΩcie element≤w tablicy w lewo (pocz▒wszy od pozycji i+1 czyli 2 w naszym przyk│adzie)
O ile kroki 1-3 nie wymagaj▒ komentarza to nale┐a│oby dok│adniej opisaµ krok 4:
Poniewa┐ ka┐de z dzia│a± matematycznych wykonywane jest na dw≤ch sk│adnikach (dw≤ch elementach tablicy) wiΩc po wykonaniu obliczenia nale┐y usun▒µ obydwa sk│adniki (oraz znak dzia│ania) a w ich miejsce wstawiµ wynik obliczenia. Bardzo prosto mo┐na by to wykonaµ stosuj▒c zamiast tablic listΩ. Ale poniewa┐ chcia│em aby algorytm by│ zrozumia│y nawet dla bardzo pocz▒tkuj▒cych programist≤w (kt≤rzy nie znaj▒ dynamicznych struktur danych) nie zdecydowa│em siΩ na u┐ycie list (je┐eli wiesz co to jest lista i umiesz j▒ w miarΩ wprawnie obs│ugiwaµ to nie powiniene╢ mieµ problem≤w z przerobieniem algorytmu). Naj│atwiejszym sposobem uzyskania efektu z│▒czenia element≤w tablicy jest jej odpowiednie (czΩ╢ciowe) przesuniΩcie w lewo dziΩki czemu jeden z element≤w tablicy zostanie zamazany przez jego "s▒siada".
Po analizie powy┐szego przyk│adu mo┐emy pokusiµ siΩ o stworzenie zarysu algorytmu (na razie bez uwzglΩdnienia nawias≤w):
K1.Ustal warto╢µ zmiennej i na 1
K2. Pobierz element (rodzaj dzia│ania do wykonania) o indeksie i z tablicy znak
K3. Wykonaj odpowiednie dzia│anie na elementach tablicy liczba o indeksach i oraz i+1
K4. Wynik dzia│ania zapisz w tablicy liczba na pozycji i+1
K5. Przesu± wszystkie tablice w lewo o jedn▒ pozycjΩ pocz▒wszy od elementu o indeksie i+1
K6. Je┐eli w tablicy znak znajduj▒ siΩ jeszcze jakie╢ elementy to wykonaj skok do K2.
Po zako±czeniu algorytmu wynik wyra┐enia znajdzie siΩ w tablicy liczba na pozycji 1.
Powy┐szy algorytm nie jest jednak poprawny - nie uwzglΩdnia bowiem kolejno╢ci dzia│a± wystΩpuj▒cych w matematyce. Wiadomo, ┐e w wyra┐aniu powinno zostaµ wykonane mno┐enie przed dodawaniem - jednak powy┐szy algorytm traktuje wszystkie dzia│ania r≤wno (wykonuje dzia│ania od lewej do prawej bez uwzglΩdnienia rodzaju dzia│ania). Co zrobiµ aby zmusiµ algorytm do zachowania kolejno╢ci? Prostym i skutecznym rozwi▒zaniem jest stworzenie dw≤ch pΩtli - pierwsza wykonywaµ bΩdzie wszystkie mno┐enia i dzielenia (obydwa dzia│ania maj▒ ten sam priorytet), druga za╢ dodawania i odejmowania. Po wykonaniu pierwszej pΩtli, w wyra┐eniu (tablicach) nie bΩd▒ ju┐ wystΩpowa│y znaki mno┐enia oraz dzielenia wiΩc bez obaw mo┐na wykonaµ pozosta│e dzia│ania (jeszcze raz podkre╢lam, ┐e na razie zajmujemy siΩ wyra┐eniami nie zawieraj▒cymi nawias≤w). Oto jak wygl▒daµ bΩdzie schemat krokowy naszego poprawionego algorytmu:
{pΩtla pierwsza odpowiedzialna za mno┐enia i dodawania}
K 1. Ustal warto╢µ zmiennej i na 1
K 2. Pobierz element o indeksie i z tablicy znak.
K 3. Je┐eli znak dodawania lub odejmowania to zwiΩksz i o jeden oraz wykonaj skok do K7.
K 4. Wykonaj odpowiednie dzia│anie na elementach tablicy liczba o indeksach i oraz i+1
K 5. Wynik dzia│ania zapisz w tablicy liczba na pozycji i+1
K 6. Przesu± wszystkie tablice w lewo o jedn▒ pozycjΩ pocz▒wszy od elementu o indeksie i+1
K 7. Je┐eli w tablicy znak znajduje siΩ jeszcze mno┐enie lub dzielenie to skok do K2.
{pΩtla druga odpowiedzialna za dodawania i odejmowania}
K 8. Ustal warto╢µ zmiennej i na 1
K 9. Pobierz element o indeksie i z tablicy znak.
K10. Je┐eli znak mno┐enia lub dzielenia to zwiΩksz i o jeden oraz wykonaj skok do K14.
K11. Wykonaj odpowiednie dzia│anie na elementach tablicy liczba o indeksach i oraz i+1
K12. Wynik dzia│ania zapisz w tablicy liczba na pozycji i+1
K13. Przesu± wszystkie tablice w lewo o jedn▒ pozycjΩ pocz▒wszy od elementu o indeksie i+1
K14. Je┐eli w tablicy znak znajduje siΩ jeszcze dodawanie lub odejmowanie to skok do K9.
Pierwsza pΩtla przemiata tablicΩ (od indeksu pierwszego do ko±ca) znak w poszukiwaniu znak≤w mno┐enia lub dzielenia, druga w poszukiwaniu dodawania lub odejmowania. Po wykonaniu obydw≤ch pΩtli, wynik (tym razem ju┐ poprawny) znajdzie siΩ w tablicy liczba na pozycji pierwszej.
Oczywi╢cie w jΩzyku Pascal mo┐na powy┐szy algorytm zrealizowaµ w postaci dw≤ch prostych pΩtli (patrz: kod ╝r≤d│owy).
Do tego momentu unikali╢my obliczania wyniku dla wyra┐e± zawieraj▒cych nawiasy. Pojawienie siΩ nawias≤w zaburza w znacznym stopniu kolejno╢µ dzia│a±. Wpierw nale┐y wykonywaµ wszystkie operacje w nawiasach a nastΩpnie pozosta│e. Na pocz▒tek nale┐y zastanowiµ siΩ w jaki spos≤b bΩdziemy przechowywaµ informacje o nawiasach. Ja umie╢ci│em te informacje w trzeciej tablicy (nawias). Oto w jaki spos≤b przechowywane s▒ informacje. We╝my np. pewne wyra┐enie : "((2 + 3) * 2)", po roz│o┐eniu na tablice otrzymamy :
| liczba | 2 | 3 | 2 | | | | |
| znak | + | * | | | | | |
| nawias | (( | ) | ) | | | | |
Pojawienie siΩ na pozycji i nawiasu oznacza, ┐e w obliczanym wyra┐eniu wystΩpuje on przed (je┐eli jest to nawias otwieraj▒cy) lub po (zamykaj▒cy) liczbie z pozycji i. Wci▒┐ jednak wystΩpuje problem jak przechowywaµ informacje czy na danej pozycji nawias otwieramy czy zamykamy (na schemacie umie╢ci│em po prostu symbole nawias≤w "(" oraz ")"). Ja przyj▒│em nastΩpuj▒c▒ regu│Ω :
- Je┐eli na pozycji i wystΩpuje otwarcie nawiasu(≤w) to w tablicΩ nawias na pozycjΩ i wpisz dodatni▒ liczbΩ r≤wn▒ ilo╢ci otwieranych nawias≤w.
- Je┐eli na pozycji i wystΩpuje zamkniΩcie nawiasu(≤w) to w tablicΩ nawias na pozycjΩ i wpisz ujemn▒ liczbΩ r≤wn▒ ilo╢ci zamykanych nawias≤w.
Stosuj▒c tak▒ regu│Ω z wyra┐enia ((2 + 3) * 2) otrzymamy:
| liczba | 2 | 3 | 2 | | | | |
| znak | + | * | | | | | |
| nawias | 2 | -1 | -1 | | | | |
Wystarczy jeszcze tylko opisaµ w jaki spos≤b algorytm ma korzystaµ z informacji zapisanych w tablicy nawias. Po pierwsze nasz poprzedni algorytm nale┐y przerobiµ w funkcjΩ, kt≤ra wykonuje dzia│ania na wybranym fragmencie tablicy (okre╢lonej przez parametry) i zwraca wynik po wykonaniu operacji na tym fragmencie. Nale┐y tak┐e przed wykonywaniem jakichkolwiek dzia│a± sprawdziµ czy w danym fragmencie nie wystΩpuj▒ nawiasy - je┐eli tak to nale┐y wywo│aµ nasz▒ funkcjΩ (REKURENCJA !!!) w│a╢nie na obszarze jaki obejmuj▒ nawiasy i, co najwa┐niejsze, skasowaµ obliczony ju┐ nawias z tablicy (inaczej funkcja siΩ zapΩtli). Oto schemat krokowy algorytmu (funkcji) uwzglΩdniaj▒cego nawiasy:
funkcja Oblicz (pocz▒tek, koniec)
K1. Sprawd╝ czy w rozpatrywanym fragmencie tablicy (tzn. od elementu pocz▒tek do koniec) wystΩpuj▒ nawiasy - je┐eli tak to :
- wywo│aj funkcjΩ oblicz dla obszaru jaki obejmuj▒ nawiasy
- skasuj nawiasy, w kt≤rych dokonali╢my oblicze±
- ponownie sprawd╝ czy s▒ nawiasy (skok na pocz▒tek K1)
K2. Sprawd╝ czy w rozpatrywanym fragmencie tablicy wystΩpuj▒ znaki mno┐enia lub dzielenia - je┐eli tak to wykonaj dzia│ania
K3. Sprawd╝ czy w rozpatrywanym fragmencie tablicy wystΩpuj▒ znaki dodawania lub odejmowania - je┐eli tak to wykonaj dzia│ania
K4. Zwr≤µ warto╢µ funkcji r≤wn▒ elementowi o indeksie pocz▒tek z tablicy liczba
Koniec funkcji.
Kroki K2 i K3 to po prostu dwie pΩtle z poprzedniego algorytmu.
Aby otrzymaµ wynik z ca│ego wyra┐enia wystarczy wywo│aµ funkcjΩ oblicz z parametrami: pocz▒tek = 1, koniec = ilo╢µ element≤w w tablicy znak.
Obja╢nie± wymaga jeszcze krok K1 - a dok│adniej w jaki spos≤b skasowaµ nawiasy. Narzucaj▒cym siΩ rozwi▒zaniem jest po prostu przypisanie danemu elementowi tablicy nawias warto╢ci zero. BúíD. Sp≤jrzmy ponownie na przyk│ad z wyra┐eniem ((2 + 3) * 2):
| liczba | 2 | 3 | 2 | | | | |
| znak | + | * | | | | | |
| nawias | 2 | -1 | -1 | | | | |
Je┐eli po obliczaniu nawiasu (2+3) (w naszej tablicy s▒ to pozycje od 1 do 2) nawiasom 1 i 2 przypisaliby╢my warto╢ci zero, w≤wczas otrzymaliby╢my paradoksalny efekt:
| liczba | 2 | 3 | 2 | | | | |
| znak | + | * | | | | | |
| nawias | 0 | 0 | -1 | | | | |
Widaµ wyra╝nie, ┐e na pozycji 3 ko±czy siΩ JAKIª nawias - no w│a╢nie JAKIª bo przecie┐ ten nawias siΩ nigdzie nie zaczyna ?!?. Dlatego nie zerujemy nawias≤w, a postΩpujemy wed│ug poni┐szej regu│y (kt≤r▒ stosujemy oczywi╢cie tylko do kasowanych nawias≤w):
- element tablicy z nawiasem otwieraj▒cym zmniejszamy o 1
- element tablicy z nawiasem zamykaj▒cym zwiΩkszamy o 1
Je┐eli post▒pimy wed│ug tych regu│ to po obliczeniu nawiasu (2+3) otrzymamy:
| liczba | 2 | 3 | 2 | | | | |
| znak | + | * | | | | | |
| nawias | 1 | 0 | -1 | | | | |
Co jednoznacznie wskazuje, ┐e na pozycji pierwszej zaczyna siΩ nawias a na pozycji trzeciej ko±czy.
Ostatni▒ spraw▒ wymagaj▒c▒ obja╢nie± jest obs│uga zmiennych. Naj│atwiej jest zast▒piµ jej nazwΩ konkretn▒ warto╢ci▒ ju┐ podczas fazy rozdzielania wzoru ze zmiennej string na tablice.
