Wikipedysta:Yusek/Matematyka dyskretna/Drzewo wyrażeń arytmetycznych

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ą.

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.

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.

Drzewa wyrażeń arytmetycznych

We wczesnych klasach szkoły podstawowych ucząc dzieci obliczać bardziej skomplikowane 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 wykorzystać 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.