Bilgisayar Olimpiyatı 2009, 1. Aşama, Soru 14

## [11-15] soruları için açıklama
Yığıt son-eklenen-ilk-çıkar mantığı ile çalışan, eleman ekleme ve eleman çıkarma operasyonlarının yapılabildiği bir veri yapısıdır. Bu yapıda ilk erişilebilecek eleman, ya da ilk çıkarılabilecek eleman yığıta en son eklenen elemandır. Bu son eleman yığıttan çıkarıldıktan sonra, doğal olarak bir sonraki eleman yığıta en son eklenen eleman haline dönüşmekte ve bir sonraki adımda da bu elemana ulaşmak ya da çıkarmak mümkün olmaktadır.
Bu şekilde herhangi bir yığıtta, yığıta en yeni eklenen elemandan ilk eklenen elemana doğru bir sırada elemanlara erişmek olasıdır. Yığıta yeni eleman eklenmesi sonucunda da bu yeni eleman ilk çıkarılabilecek eleman olmaktadır. Bu şekilde tanımlanan yığıt veri yapısı üzerindeki işlemler şunlardır:
- EKLE(p): p'yi yığıt'a son eleman olarak ekler.
- ÇIKAR(): son elemanı yığıttan çıkarır ve sonuç olarak verir.
Örneğin tamsayı değerlerin saklandığı bir yığıtta aşağıdaki işlemler uygulanmış olsun:
EKLE(3)
EKLE(2)
EKLE(4)
d = ÇIKAR()
EKLE(1)
d = ÇIKAR()
EKLE(5)
Bu durumda yığıttan ilk ÇIKAR0 işlemi sonucunda 4, ikincisinin sonucunda da 1 değerleri çıkarılmış olur. Kalan değerler çıkarılmak istenirse de sırasıyla 5, 2 ve 3 değerleri elde edilir.
Aşağıdaki sorularda kullanılan yığıtta elemanlar olarak tamsayılar ve değişik matematiksel işlemler saklanmaktadır. Bu yapı üzerinde bir de X0 işlemi tanımlanmaktadır. Yığıta X işlemi uygulandığında yığıttan peş peşe 3 adet eleman çıkarılmakta (ilk olarak bir tamsayı, ortada bir matematiksel işlem, son olarak bir tamsayı daha) ve bu bu matematiksel işlem bu iki tamsayı üzerinde (ilk tamsayı matematiksel işlemin sağında, ikincisi solunda olacak şekilde) uygulanmakta ve elde edilen sonuç da yığıta eklenmektedir. "Örneğin, çıkarılan elemanlar 2, -, 3 ise 3 - 2 işlemi yapılmakta ve sonuç değeri 1 yığıta eklenmektedir. X işleminin tanımı şöyledir:
\[X(0) = \left\{ \begin{array}{l}
say_{2} = ÇIKAR() \\
islem = ÇIKAR() \\
say_{1} = ÇIKAR() \\
say_{3} = say_{1} \quad islem \quad say_{2} \\
EKLE(say_{3})
\end{array} \right.\]
Aşağıdaki sorularda yığıt üzerinde sadece EKLE ve X işlemleri uygulanacaktır ve EKLE(p) işlemi sadece p ile gösterilecektir. Örneğin "3 - 2" ifadesi
EKLE(3)
EKLE(-)
EKLE(2)
işlemlerinin yapıldığını göstermektedir. Ya da "3 - 2X" ifadesi sonucunda yığıta önce 3, - ve 2 değerleri eklenip, sonra X işleminin gereği olarak, 2, - ve 3 değerleri yığıttan çıkarılmakta ve matematiksel çıkarma işlemi uygulanmakta, bunun sonucunda da elde edilen 1 değeri yığıta eklenmektedir.
Buna göre aşağıdaki soruları yanıtlayınız. Bu sorularda standart matematiksel işlemler
+,-,*, / işlemleri kullanılmaktadır. / (bölme) işlemi 'tamsayı bölme' anlamındadır
(4/2 = 2, 5/2 = 2, 8/3 = 2 gibi). İfadelerde elemanlar arasında (tamsayı, matematiksel işlem ve X) boşluk bırakılmamıştır.
[GÖRSEL]
A) 0
B) 5
C) 10
D) 15
E) 20
Soruda verilen yapı için adım adım ilerleyelim.
- İlk eklemelerden sonra yapıda sırasıyla 13 + 4 bulunur. İlk X'ten sonra yapıda sadece 17 kalır. Sonraki 4 eklemeden sonra ise yapı sırasıyla 17 - 2 * 3 halini alır.
- Ardından tekrar X işlemine sokulur ve yapıda 17 - 6 kalır. Tekrar X e sokulduğunda ise elimizde 11 kalır.
- Sıradaki eklemelerle yapı 11 - 10 - 4 halinde gelir ve X sonrası 11-6 olur. Sonraki X'te ise sadece 5 kalır. Cevap 5 olur.

---

13 - 4 - 2 + 6 + 1XXX*2*3/4/3/2XX/3X*2XXX*3XX - 7XX işleminin sonucu yığıtta kalan değer aşağıdaki- lerden hangisidir?

Şıklar:
A) 0 | B) 5 | C) 10 | D) 15 | E) 20

Cevap: D 15

Çözüm:
Adımlar sonucunda yığıt sırasıyla Şu şekilde olur:
- 13 - 4 - 2 + 6 + 1
- 13 - (-5)*2*3/4/3/2
- 13 - (-5)*2*3/4
- 13 - (-5)*2*3/4/3
- 13*(-5)*2*3/1*2
- 13 - (-5)*2 - 3
- 13 - (-5)*(-1)
- 13 - 5
- 13 - 5 - 7
- 15
Dolayısıyla cevap 15 olur.