W tym punkcie rozważymy problem obliczania wartości wyrażeń algebraicznych (termów). Algorytm rozwiązujący ten problem używa, jako pomocniczej struktury danych, stosów.

Definicja 6.1 Zbiorem wyrażeń algebraicznych WA nazywać będziemy najmniejszy zbiór napisów nad alfabetem {x,y,z, +,*,-,(,)}, taki że

(1) x, y, z są wyrażeniami algebraicznymi,
(2) jeśli w i w' należą do WA, to (w+w') , (w-w') oraz (w*w') też należą do WA.

Przykładami wyrażeń algebraicznych są następujące termy ((x+y)*z), ((x+(y*z))+(x-z)). W dalszym ciągu rozważać będziemy wyrażenia algebraiczne w strukturze liczb rzeczywistych, co oznacza, że zmienne przyjmować będą wartości rzeczywiste, a operacje + i * są po prostu dodawaniem, odejmowaniem i mnożeniem liczb rzeczywistych.

Jak obliczamy wartość wyrażenia? Niech nasze wyrażenie ma postać ((x+y) * (y+z)). Działaniem głównym jest *. Aby wyliczyć wartość tego iloczynu, musimy znać wartości zmiennych x, y, z oraz najpierw wyliczyć sumy (x+y) i (y+z). Czyli, aby obliczyć wartość wyrażenia musimy najpierw obliczyć wartości jego prostszych podwyrażeń. Zauważmy, że jeżeli przeglądamy znaki naszego wyrażenia od lewej do prawej, to musimy zapamiętać wartość zmiennej x oraz operację +, bo np. prawy argument może być skomplikowanym wyrażeniem, które trzeba wcześniej wyliczyć, zanim przystąpimy do wykonania operacji +. Naturalną strukturą, która pomoże nam pamiętać kolejność wykonywania operacji, jest stos.

Załóżmy, że wyrażenie algebraiczne jest dane w postaci tablicy znakowej o elementach tab[1], tab[2], ..., tab[n], a wartości zmiennych w nim występujących są zapisane w obiekcie val, którego atrybutami są x, y, z.

Idea algorytmu jest następująca: Czytamy kolejne znaki wyrażenia. Napotkane symbole operacji wpisujemy na stos operacji, a napotkane argumenty - na stos argumentów. Pojawienie się nawiasu zamykającego oznacza zakończenie wczytywania jakiegoś poprawnego wyrażenia algebraicznego. Można więc obliczyć jego wartość. Pobieramy nazwę operacji ze stosu operacji i argumenty ze stosu argumentów, i wykonujemy obliczenie. Wynik wkładamy na stos argumentów, bo wartość obliczonego wyrażenia może być argumentem innej operacji.

Dany jest ciąg znaków tab[1], tab[2], ..., tab[n] pewnego wyrażenia algebraicznego oraz obiekt val taki, że val.x, val.y, val.z są wartościami zmiennych x, y i z. W przedstawionym algorytmie używać będziemy dwóch stosów pomocniczych Arg i Op, o których zakładamy, że są początkowo puste. Na stosie Arg umieszczać będziemy wartości zmiennych lub obliczone wartości podwyrażeń, natomiast na stosie Op zapisywać będziemy symbole operacji. Użyta w algorytmie instrukcja postaci case s of ...esac, zastępuje wielokrotną instrukcję warunkową uzależniającą rodzaj wykonywanej akcji od wartości zmiennej s.

Oblicz{
	for i := 1 to n do
	if (tab[i] = '+' or tab[i] = '' or tab[i] = '-') then*	// przeczytany znak, to symbol operacji
	Op := push(tab[i], Op);	//wpisujemy na stos operacji
	else
	if (tab[i] = 'x' or tab[i] = 'y' or tab[i] ='z') then	// przeczytany znak, to zmienna
	case tab[i] of
	'x' : Arg := push(val.x, Arg);	//wpisujemy na stos argumentów jej wartość
	'y' : Arg := push(val.y, Arg);
	'z' : Arg := push(val.z, Arg);
	esac
	else
	if (tab[i] = ')' ) then	// przeczytany znak to nawias ')'
	operacja := top(Op); Op := pop(op);	//zdejmujemy ze stosu symbol operacji
	a2 := top(Arg); Arg := pop(Arg);	// zdejmujemy ze stosu argumenty
	a1 := top(Arg); Arg := pop(Arg);
	case operacja of	//wynik zapisujemy ponownie na stosie argumentów
	'+' : Arg := push(a1 + a2, Arg);
	'-' : Arg := push(a1 - a2, Arg);
	'' : Arg := push(a1 a2, Arg);
	esac;
	fi
	fi
	fi
	od;
}

Zauważmy, że algorytm ignoruje całkowicie nawiasy otwierające, nie rozważamy też problemu poprawności wyrażenia. Zakładamy, że jest ono poprawnie zbudowane.

Rozważmy wyrażenie algebraiczne postaci ((x+(y*z)) +(z-x)). Niech wartościami zmiennych x, y, z będą odpowiednio liczby 3, 4, 5. Na rysunku 6.11 przedstawiono, kolejne etapy obliczania wartości tego wyrażenia.

Na szarym pasku zapisano kolejne znaki rozważanego wyrażenia, a powyżej, ewentualne zmiany zawartości stosów argumentów i operacji w wyniku odczytania odpowiedniego znaku. Na zakończenie, wyliczona wartość wyrażenia znajduje się na stosie argumentów. J

Pytanie 8: Jaki jest koszt algorytmu Oblicz, jeśli rozmiarem danych jest długość n danego wyrażenia algebraicznego, a miarą kosztu - liczba operacji wykonanych na stosie?


	stos argumentów									stos operacji


							5								3
					4	*	4	20					5	-	5	2
		3	+		3	+	3	3	+	23	+		23	+	23	23	+	25
(	(	x	+	(	y	*	z	)		)	+	(	x	-	z	)		)

									Rysunek 6.11