CP #43: Stack Problemleri

Cok kisa bir stack hatirlatmasi yapalim sonra problemlere gecegiz.

Stack neydi?

Bir stack uzerinde yapilacak iki temel operasyon vardir: push ve pop. Yani eleman ekleme ve eleman cikarma. Bu islemler de, last-in first-out siralamasi ile olur, yani son giren ilk cikar. 

Eger stack linked list ile implemente edilmisse, push ve pop islemleri her zaman O(1) maliyete sahiptir. Eger array ile implemente edilmisse, belirli bir eleman sayisina kadar O(1) maliyete sahip olur. Ancak bir yerden sonra array resize edilmek zorunda kalir ve pup, pop islemleri bu sefer amortized O(1) maliyete sahip hale gelir. 

Ayrica stack'ten koparmadan (pop etmeden) en ustteki elemani gormek icin genellikle bir peek metodu bulunur. 

Son-giren-ilk-cikar seklindeki davranis, reverse-iteration durumlarinda, yani bir listi geriye dogru itere etme problemlerinde cok kullanisli olur. Su ornekte bir singly-linked listi stack kullanarak tersinden yazdirma goruluyor:   

def print_linked_list_reversed(head):

    datas = []

    while head:

        datas.append(head.data)

        head = head.next

    while nodes:

        print(datas.pop())

Burada bir arrayi (datas) stack olarak kullandik. 

Python list'i stack olarak kullanmak

• s.append(e), stack'te en uste bir eleman ekler, push operasyonu
• s[-1], stack'te en ustte duran elemani pop etmeden gormemizi (peek) saglar
• s.pop() en ustteki elemani kopartir
• "if s" seklinde stack bos mu dolu mu diye kontrol edebilir. Python'da bos list tipi, boolen comparison durumunda False dondurur.
• Stack bos ise, s[-1] ve s.pop() operasyonlari hata olusturacktir, dikkat etmek gerekir

Problemlere gecebiliriz.

Implement A Stack With Max API 

Push ve pop operasyonlarina ek olarak, bir de mevcut elemanlar icinde en buyuk olanini dondurecek bir max() metodu barindiran stack yapisi tasarlayiniz. 

Cozum

Haha ey gidi anilar. Bu soru yillar once (4 yil belki de, ama bu yasta insana cok uzun geliyor, henuz 70 yasinda degiliz ki heey gidi deyince 30 sene oncesini kastedelim. 30 sene once ilkokula baslamistim ben) bir interviewde bana sorulmustu. 

Ilk akla gelen naive yontem ile baslayalim. Nedir efendim, stack yapisi icerisinde bir max degeri tutariz. Ilk degeri -Inf'ten baslayacak sekilde. Daha sonra push islemi olunca, push edilen eleman bizdeki max degerinden buyukse bizdeki max degerini guncelleriz. Buraya kadar guzel, ama pop islemi sirasinda bizdeki max eleman pop olur giderse, simdi elde kalan elemanlar arasindan max olani bulmak icin O(n) maliyete ihtiyacimiz olacak. Yani toplamda push O(1) ama pop O(n) olacak. Ama space maliyeti O(1) cok sukur. 

Bunu iyilestirebilirz. Tabi bunun da bir maliyeti var, kainatta hicbirsey bedava degil. Space maliyetinden biraz feragat ederek, max degerini tek bir deger olarak degil de bir array olarak tutabiliriz. Hatta bir stack olarak davracak ve push operasyonu sirasinda gelen eleman, bizdeki max degerinden buyukse, yeni gelen elemani bu stack'e push edecegiz. Stack yapisindan pop edildiginde, eger bu max eleman ise, tek yapmamiz gereken max stack'inden pop etmek. Geriye yine en ustte, bir onceki max eleman kalacaktir. Yani push ve pop O(1) time compl. sahip olacak ama bizim stack yapisi ekstra olarak da bir O(n) space'e ihtiyac duyacak. Cok fazla konustuk,

class MaxStack:

    def __init__(self):

        self.items = []

        self.maxitems = []

    def push(self, item):

        self.items.append(item)

        # maxitems stacki bos mu? bos ise direk bas

        if not self.maxitems:

            self.maxitems.append(item)

        else:    

            # en ustte duran max item'den buyukse ekle

            if item > self.maxitems[-1]:

                self.maxitems.append(item)

    def pop(self):

        item = self.items.pop()

        # pop edilen item, mevcut max item mi?

        if item == self.maxitems[-1]:

            self.maxitems.pop()

        return item

    def max(self):

        return self.maxitems[-1]

Evet bence guzel bir cozum oldu. Oynat, devam:

Evaluate RPN Expression

Matematiksel ifadeleri yazmanin 3 ana metodu var. Prefix, Infix ve Postfix. Yani operatoru basa mi koyacagiz, sona mi yoksa ortaya mi. Biz normal hayatta Infix gosterim kullaniyoruz, yani 2 + 2 yaziyoruz. Ama bunu 2, 2, + seklinde de yazabiliriz. Bu da postfix ya da Reverse Polish Notation oluyor.

Bu problemde bize string olarak verilen bir RPN ifadesini hesaplayip degerini dondurmemiz isteniyor. Ornek:

1- Ifade sadece bir sayi olabilir "-123" --> 123 dondurecegiz

2- Ifadede bir islem geciyor olabilir, elemanlar virgul ile ayrilir ve operator sondadir: "2, 5, *" --> 10 dondurecegiz

3- Birden fazla ifade ic ice yeraliyor olabilir: "2, 2, 3 +, *" icin once icerideki 2,3,+ islemi yapilir ve ifade su hale gelir:  "2, 5, *" --> 10 dondurecegiz.

4- Bolme islemi integer bolmesi olacak yani 7/2 -> 3 dondurmesi gerekiyor

Cozum

Evet belki daha once bu soruyu cozmusuzdur conku cok meshur bir stack sorusu. Bence hemen gecelim:

def eval_rpn(s):

    # virgullerden kurtulup, ifadeyi tokenize edelim 

    # ve herbir tokenin etrafindaki bosluklari atalim

    tokens = list(map(lambda x: s.strip(), s.split(","))))

    

    # eger sadece tek bir token varsa, direk dondurebiliriz.

    # 1. duruma tekabul ediyor

    if len(tokens) == 1:

        return int(tokens[0])

    # hesaplamalari tutacagimiz stack 

    stack = []

    # operatorleri tanimlayalim

    ops = {

        "+": lambda x, y: x + y,

        "-": lambda x, y: x - y,

        "/": lambda x, y: x // y,  # integer bolmesi isteniyordu

        "*": lambda x, y: x * y 

    }

    for t in tokens:

        # eger elimizdeki token bir operator ise

        # gerekli islemi gerceklestirelim

        if t in tokens:

            # stack'ten ilk pop ettigimiz aslinda 2. operand oluyor

            # cunku stack'e tokenlar ters sirada giriyor

            operand2 = stack.pop()

            operand1 = stack.pop()

            result = ops[t](operand1, operand2)

            # sonucu tekrar stack'e basiyoruz

            stack.append(result)

        else:

            # token bir operator degilse, sayi demektir

            # integere cevirip stack'e basiyoruz

            stack.append(int(t))

    # bu noktada stack'te sadece 1 deger kaliyor ki

    # bu da tum hesaplamalarin sonucu

    return stack.pop()

Evet, simdi bir analiz edelim. Ilk basta stringi tokenize etmek icin split ettik ki O(n) bir islem. Ayrica O(n) ekstra space demek. Daha sonra tum tokenleri traverse ederek islemleri yaptik ki bu da O(n) ve ekstra bir O(n) space daha demek. Aslinda O(2n) time ve O(2n) space compl. var. Tabi ki big-o gosterimde sabit sayilar onemsizdir ve sonucta lineer space ve lineer time compl. bir cozum elde etmis olduk. Guzel. 

Is A String Well-Formed?

Parantezlerden olusan bir string veriliyor. Bu strining gecerli olup olmadigini kontrol ediniz. Kullanilabilecek parantezler: (, [, {.

Ornek: ()[{}] -> gecerli

Ornek: ([{})] -> gecersiz cunku once koseli parantez kapatilmaliydi. 

Cozum

RPN expression cozumlemesine benzer sekilde, her bir karakteri alip inceliyoruz. Egere acilis parantezi ise direk stack'e basiyoruz. Egere kapanis ise, stack'e donup bir bakmamiz lazim. Oncelikle eger ifade gecerli ise, bu noktada stack'te enaz bir eleman (acilis parantezi) olmasi gerekir. Onu kontrol ediyoruz. Daha sonra acilis parantezi ile kapanis parantezi ayni tipten mi (biri { birisi de ] olabilir) kontrol ediyoruz. Egere bu da gecerli ise, stack'teki acilis parantezini (en ustte duruyor), pop ediyoruz. 

Bu sekilde gittigimizde egere en sonda stack'te hic eleman kalmamis ise tum acilis kapanis parantezleri birbirine uyuyor demektir. Ve ifade gecerlidir. 

def i_valid_paran(s):

    # acilis kapanis parantezlerinin esleyelim

    pairs = {

        "(": ")",

        "[": "]",

        "{": "}"

    }

    stack = []

    for c in s:

        # acilis parantezi

        if c in pairs:

            stack.append(c)

        else:

            # kapanis parantezi var elimizde

            # bakalim stack bos mu ?

            if not stack:

                return False

            

            # stackte en ustte duran acilis parantezini alalim

            last = stack[-1]

            last_pair = pairs[last] # bunun pairi ne olmali?

            if c == last_pair: # eger tipler uyuyor ise

                stack.pop()

            else:

                return False # tipler uymuyor ise zaten ifade gecersiz

    # bu noktada stack'te hic parantez kalmamis olmasi lazim

    return len(stack) == 0

Analizi de kolay, bir stack (O(n) space compl. demek), bir de lineer loop ile cozumu tamamladik. 

Normalize Path Names

Bir klasor ya da dosya, pathname adi verilen bir string ile belirtilebilir. Ornegi /usr/bin/gcc gibi. Ancak ayni pathname birden farkli sekilde de gosterilebilir, ornegin: /usr/lib/../bin/gcc de yine ayni klasoru isaret etmektedir. Bu durumda verilen pathname icin en kisa gosterimi hesapyaliniz.

Ornek: scripts//./../scripts/awkscripts/././ --> scripts/awkscripts 

Yani tek nokta mevcut klasoru, iki nokta bir ustteki klasoru belirtir. Eger slashler arasinda bir karakter yok ise (// gibi) bir anlam ifade etmez. 

Cozum

Umarim unix path'leri ile asinasinizdir cunku ben yukarida belki de tam olarak ne olduklarini anlatamadim. Ama mantik olarak aslinda cok basit. Tek nokta demek, mevcut klasorde kal demek. Yani pathname, tek noktaya geldigi anda hangi klasoru gosteriyorsa, nokta da o klasorde kalmasini saglar. Yani direk atilmasinda bir sakinca yok. Iki nokta ise, o noktada hangi klasorde isek, bir yukari cikmamizi saglar. 

Batigimizda stack icin bicilmis kaftan bir mantik var. Pathname'i en soldan baslayarak analiz edecegiz. Eger bir klasor adi gorursek, stack'e basacagiz. Bu bizim mevcut path'imiz oluyor. Eger cift nokta gorursek de stack'te en ustte durani atabiliriz cunku bir ust klasore cikiyoruz demektir. Tabi burada bir edge case var, kodda gorecegiz. Gorelim:

def dir_path_normalize(path):

    # once tokenize edelim

    tokens = path.split("/")

    for t in tokens:

        # tek nokta veya bosluk varsa devam et

        if t == "." or t == "":

            continue

        

        if t == "..":

            # eger stack'te en ustte yine iki nokta varsa

            # bunu silemeyiz, uzerine eklmemiz gerekir

            # yani: /../../ durumu gibi

            if stack and stack[-1] != "..":

                stack.pop()

            else:

                stack.append(t)

        # path'te en basta slash var ise bunu da korumamiz gerek

        # ama split asamasinda bunu kaybediyoruz

        return ("/" if s[0] == "/" else "") + "/".join(stack)

Liner bir loop ile O(n) time compl. ve ekstra tokens arrayi ile de O(n) space compl. ile cozumu tamamladik.

Compute Buildings With A Sunset View

Dogudan batiya dogru tek cizgi halinde binalar var. Bu binalardan tabi ki en batida olani, gun batimini gorebiliyor. Ancak, bu binanin dogusunda olup da, bu binadan daha kisa olan binalar ise gun batimini ne yazik ki goremiyor. Yani soyle bisey:

<-- Dogu           Bati --->

        #

#      #  #      #

#  #  #  #  #  #  #

0  1  2  3  4  5  6

Bize dogu'dan batiya olacak sekilde bir siralama ile bu binalarin yukseklikleri veriliyor. Yukaridaki ornek icin input soyle [2, 1, 3, 2, 1, 2, 1]. Bunlar hangileri gun batimini gorebiliyor? En batida olan gorur. Bir solundaki yine gorur ne de olsa daha yuksek. Bu sekilde devam edersek, [6, 5, 2] indexlere sahip binalarin gun batimini gorebildigini farkediyoruz. 

Verilen bina yuksekligi arrayini kullanarak, gun batimini goren binalari hesaplayiniz.

Cozum

Romantik bir problem oldugunu kabul etmek lazim. Benim aklima ilk gelen yontem, en sagdan baslayarak, her adimda, o ana kadar olan en buyuk binayi (running max) tutmak. Her adimda, o bina, suana kadar gorulen en buyuk binadan buyuk ise sonuc arrayina ekleyebiliriz. Gorelim:

def sunset_view(arr):

    ret = []

    max_sofar = 0

    for i in range(len(arr)-1, -1, -1):

        if arr[i] > max_sofar:

            ret.append(arr[i])

            max_sofar = arr[i]

    return ret

Bakacak olursak time compl. O(n) oldugunu goruyoruz. Space compl. icin upper bound O(n) olabilir, egere tum binalar sunseti gorebiliyorsa, mesela [6,5,4,3] gi bir sequence.  

Follow-up
Peki, bize bina yukseklikleri bir anda array olarak verilmiyor da, bir stream olarak veriliyorsa ne olacak? 

Bu durumda yukaridaki gibi sondan baslyarak itere edemeceyecegiz cunku sonu belli degil. Sadece bir sonraki bina yuksekligini biliyor olacagiz. 

Ilk baslangic asamasina bakarsak, gelen ilk bina yuksekligini (en dogudaki), sunseti gorebiliyor varsayacagiz. Cunku ya baska bina gelmezse? Bu mantikla, her bir gelen bina yuksekligine aday gozuyle bakmamiz gerekiyor. 

Bir sonraki gelecek olan bina yuksekligi bir oncekinden buyuk ise, bu durumda bir oncekine gerek kalmadi demektir, ne de olsa goremeyecek. Hatta sadece 1 onceki de degil, yeni gelen binadan kisa olan tum gecmis binalari atmamiz lazim. Evet, bu da bir stack yapisini animsatiyor. 

Plan su: Ilk gelen binayi stack'e basiyoruz. Daha sonraki gelen binalar icin, bundan kisa olan tum binalari da stack'ten pop'luyoruz. Enson elimizde sadece sunseti gorebilen binala kaliyor!

def sunset_view_stream(seq: Iterator[int]) -> List[int]:

    stack = []

    # python'da naive stream processing

    while building_height in seq: 

        # stack bosalana kadar veya en ustteki bina yuksekligi

        # eldeki olandan buyuk olana kadar

        # stack'te en ustteki binayi popla

        while stack and stack[-1] < building_heigt:

            stack.pop()

        stack.append(building_height)

    return stack

Stream bittiginde, bina yuksekliklerinden olusan bir array dondurecegiz. Yukaridaki sonuctan biraz farkli (orada bina indexlerini dondurduk), ama orasi da biraz modifikasyonla halledilebilir. Onemli olan, binalari nasil soldan baslayarak adim adim process edip, sunset gorenleri hesaplayabilmek. 

Bakacak olursa time compl. yine O(n), space compl. de upper bound O(n) ama buyuk ihtimalle bundan biraz daha az olacaktir. 

Stack konusu bitmez, ama bir sonraki postta queue problemlerine gececegiz. 

O zamana kadar, Bleib gesund!