Matematyka dyskretna/Drzewo wyrażeń arytmetycznych
Z Wikibooks, biblioteki wolnych podręczników.
Spis treści |
[edytuj] Wstęp
Jesteśmy przyzwyczajeni do arytmetyki infixowej czyli takiej w której działania są między argumentami, których to działanie dotyczy. Arytmetyka ta ma niestety wady np. nie jest jednoznaczna, więc niestety wymaga stosowania piorytetów i nawiasów. W informatyce często stosuje się arytmetki post- i prefixową.
[edytuj] Arytmetyka posfixowa
W arytmetyce postfixowej (zwanej też notacją polską lub notacją Łukasiewicza). działania występnują po swoich argumentach. np. 2,3+ w wyrażeniach tych nie trzeba używać nawiasów. W tej artmetyce używa się stosu. Aby obliczyć wyrażenie w postaci postfixowej kładziemy kolejne argumenty na stos, w przypadku natrafienia na działanie zdejmujemy dwa argumenty obliczamy ich wartość a następnie kładziemy na stos. Na końcu powinna zostać nam jedna liczba, która jest wynikiem. W przypadku kiedy wyrażenie się skończyło a na stosie pozostała na więcej niż jedna liczba zgłaszamy błąd. Przykład obliczenia wyrażenie postfixowego. 2,3*45,9/,+
| element | stos |
| 2 | 2 |
| 3 | 2,3 |
| * | 6 |
| 45 | 6,45 |
| 9 | 6,45,9 |
| / | 6,5 |
| + | 11 |
Koniec pozostała na stosie liczba 11 jest wynikiem.
aby to sprawdzić możemy przerobić to wyrażenie na postać infixową. 2*3+45/9=6+5=11. Czyli wszysto się zgadza.
[edytuj] Arytmetyka prefixowa
Arytmetyka prefixowa jest rzadziej używana. Działania występują przed argumentami, np. +2,3 w tej arytmetyce też nie stosuje się nawiasów. Podczas rozwiązywania równań prefixowych używa się kolejki. Przykład: +,*,2,3,/,45,9.
[edytuj] Drzewa wyrażeń arytmetycznych
We wczesnych klasach szkoły podstawowych ucząc dzieci obliczać bardziej skąplikowane wyrażenia stosuje się drzewa. Na liściach drzewa wpisuje się liczby a na węzłach działania. Dodatkowo obok węzłów można wpisywać podwyniki. Drzewa te można także wykorzytać w arytmetyce pre i postfixowej. W przypadku arytmetyki prefixowej tworząc drzewo piszemy działanie a następnie jego argumenty jeżeli zamiast argumentu znajdziemy działanie to wpisujemy to działanie a następnie wpisujemy argumenty do tego działania w przypadku kiedy miejsca na argumenty się skończyły przesuwamy się wyżej i tam wpisujemy argument.
