အခန်း ၄ ။ Stack

ဒီ အခန်း မှာ Stack နဲ့ ပတ်သက်ပြီးတော့ stack ကို အဓိက ရေးသားထားပါတယ်။ နောက်ထပ် အခန်းတွေမှာ Queue , List, Recursion , Sorting , Searching စသည်တို့ကို ဖော်ပြပေးသွားပါမယ်။

Data Strucutre ရဲ့ အဓိက ရည်ရွယ်ချက်ကတော့ stack, queue , deque, list စတာတွေ ကို သိရှိနားလည် စေဖို့ပါ။ ဒီ အခန်းမှာ အဓိက အားဖြင့် Stack ဆိုတာဘာလဲ။ Queue ဆိုတာဘာလဲ စတာတွေကို မိတ်ဆက်ပေးသွားပြီးတော့ အဓိက Array ကို နားလည်ပြီး အသုံးချတတ်ဖို့ အတွက်ပါ။ အဓိကတော့ code တွေကို ဖတ်ရုံမကပဲ ကိုယ်တိုင် ရေးကြည့်ပါ။ အသစ်တွေ ထပ်ဖြည့်ပြီး စမ်းကြည့်ပါ။ လေ့ကျင့်ခန်းတွေ ကို ကြိုးစားဖြေကြည့်စေချင်ပါတယ်။ Data Structure ဟာ အဓိက programming ကို စလေ့လာကာစ သူတွေ အနေနဲ့ တွေးတောတတ်အောင် သင်ကြားလေ့ကျင့်ပေး သည့် အရာဆိုလည်း မမှားပါဘူး။

What is a Stack ?

stack ဆိုတာကတော့ အစီအစဉ်ကျ စီထားထားတော့ items collection လို့ ဆိုရပါမယ်။ အသစ်အသစ်တွေက ကျန်နေတဲ့ data ပေါ်မှာ ထပ်ဖြည့်သွားပါတယ်။ ပြန်ထုတ်မယ်ဆိုရင် နောက်ဆုံး ထည့်ထားတဲ့ data ကနေ ပြန်ထုတ်ရပါတယ်။ LIFO (last-in-first-out) လို့ ဆိုပါတယ်။ ဥပမာ။။ ကျွန်တော်တို့ စာအုပ် ပုံနဲ့ တူပါတယ်။ စာအုပ် ပုံမှာ အောက်ကလို ရှိပါတယ်။

• python
• javascript
• css
• html

နောက်ထပ် စာအုပ် တစ်အုပ်ဖြစ်တဲ့ Data Structure ဆိုတဲ့ စာအုပ်ကို စာအုပ်ပုံမှာ ထပ် တင်လိုက်ရင်တော့

• Data Structure
• python
• javascript
• css
• html

ဆိုပြီး ဖြစ်သွားပါမယ်။ စာအုပ်ပုံကနေ စာအုပ်ကို ထုတ်မယ်ဆို အပေါ်ဘက်ကနေ ပြန်ထုတ်မှ ရပါမယ်။ ဥပမာ javascript စာအုပ်ကို လိုချင်ရင် Data Structure နှင့် Python ဆိုတဲ့ စာအုပ် ၂ အုပ်ဖယ်ပြီးမှ Javascript စာအုပ်ကို ဆွဲထုတ်လို့ ရပါလိမ့်မယ်။ အဲဒီ အခါ stack က

• javascript
• css
• html

ဆိုပြီး ဖြစ်သွားပါပြီ။

Javascript စာအုပ်ကို ယူလိုက်ရင် stack က

• css
• html

ဆိုပြီး ဖြစ်သွားပါလိမ့်မယ်။

Python စာအုပ်ကို ထပ်ဖြည့်လိုက်ရင်တော့

• python
• css
• html

ဆိုပြီး stack က ဖြစ်သွားပါလိမ့်မယ်။

First In Last Out သဘောတရားပါ။

အခု ဆိုရင် stack ဆိုတာကို စာသဘော အားဖြင့် နားလည်လောက်ပါပြီ။ ကျွန်တော်တို့ stack ကို python နဲ့ ဖန်တီးကြည့်ရအောင်။

Stack Abstract Data Type

Stack မှာ ပါဝင်မယ့် data type တွေ လုပ်ဆောင်မယ့် အရာတွေ အကို အရင် ဆုံး ကျွန်တော်တို့ စဉ်းစားကြပါမယ်။ stack က LIFO ဖြစ်တဲ့ အတွက် List လိုမျိုး ကြိုက်တဲ့ နေရာကနေ ဆွဲထုတ်လို့ မရပါဘူး။ အပေါ်က data ကို ပဲ ဆွဲထုတ်ခွင့်ရှိပါတယ်။

Stack() Stack ဆိုတဲ့ class ကို ကျွန်တော်တို့ တွေ ဖန်တီးပါမယ်။ constructor တွေ မလိုအပ်ပါဘူး။

push(item) ကတော့ item အသစ်ကို ဖန်တီးထားတဲ့ stack ထဲကို ထည့်ဖို့ အတွက်ပါ။

pop() ကတော့ stack ထဲကနေ အပေါ်ဆုံး item ကို ထုတ်ဖို့ အတွက်ပါ။ ထုတ်လိုက်တဲ့ value ကိုတော့ return မလုပ်ပါဘူး။

peek() ကတော့ stack ထဲက အပေါ်ဆုံး item ကို ထုတ်မယ်။ ပြီးတော့ return ပြန်ပေးပါမယ်။

is_empty() ကတော့ stack က empty ဖြစ်လား မဖြစ်ဘူးလား ဆိုတာကို စစ်ပြီးတော့ boolean value ကို return ပြန်ပေးပါမယ်။

size() ကတော့ stack ထဲမှာ စုစုပေါင်း data ဘယ်လောက် ရှိသလဲ ဆိုတာကို return ပြန်ပေးမယ်။ ပြီးတော့ 4 နဲ့ dog ကို ထည့်တယ်။ peek လုပ်တယ်။ နောက်ဆုံး ထည့်ထားတဲ့ dog ကို ရတယ်။ နောက်ပြီးတော့ True ထည့်တယ်။ အခန်းက ၃ ခု ဖြစ်သွားတာ ဟုတ်မဟုတ် စစ်ကြည့်တယ်။ ပြီးတော့ 8.4 ထည့်ပြီးတော့ pop ၂ ခု လုပ်လိုက်တယ်။ ဒါကြောင့် 4,dog,True,8.4 stack ကနေ pop ၂ ခု လုပ်လိုက်တော့ 4,dog ဆိုတဲ့ stack ဖြစ်သွားပါတယ်။ Size က 2 ပြပါလိမ့်မယ်။

Implementing A Stack

အခု ကျွန်တော်တို့တွေ stack ထဲမှာ ဘာတွေ ပါမယ်ဆိုတာကို သိပြီးပါပြီ။ လက်တွေ့ Stack class တစ်ခုကို တည်ဆောက်ကြည့်ရအောင်။

class Stack:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return self.items == []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[len(self.items) - 1]
    def size(self):
        return len(self.items)

အဲဒီ code ထဲမှာ ပါတဲ့ __init__(self) ဆိုတာကတော့ constructor ပါ။ Object တစ်ခုကို စပြီး တည်ဆောက်တာ နဲ့ ဦးစွာ constructor ကို ခေါ်ပါတယ်။ stack မှာတော့ Object စ ဆောက်တာနဲ့ object ရဲ့ items variable ကို empty ထည့်လိုက်ပါတယ်။

len(self.items) ဆိုတာကတော့ len ဆိုတဲ့ function ဟာ item ရဲ့ array size ကို ဖော်ပြတာပါ။ item ထဲမှာ စုစုပေါင်း array အခန်း ဘယ် ၂ ခုကို ရှိတယ်ဆိုတာကို သိနိုင်ပါတယ်။

အခု ကျွန်တော်တို့ stack ကို စမ်းကြည့်ရအောင်။

#stack.py

class Stack:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return self.items == []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[len(self.items) - 1]
    def size(self):
        return len(self.items)
        
s = Stack()

print(s.is_empty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())

s = Stack()

s ကို Stack class အနေနဲ့ ကြေငြာထားပါတယ်။

print(s.is_empty())

ပထမဆုံး stack က empty ဖြစ်နေလားဆိုတာကို ထုတ်ပြထားတယ်။ ဒါကြောင့် True ဆိုပြီး ပြပါလိမ့်မယ်။

s.push(4)
s.push('dog')

နောက်ပြီးတော့ ကျွန်တော်တို့တွေ 4 , dog စသည်ဖြင့် ထည့်လိုက်ပါတယ်။

print(s.peek())

peek ကတော့ နောက်ဆုံး ထည့်ထားတဲ့ အခန်းကို ဖော်ပြတာပါ။

print(s.size())

s.size() ဆိုတာကတော့ ကျွန်တို့တွေ size ဘယ်လောက်ရှိပြီလဲ ဆိုတာကို ထုတ်ကြည့်တာပါ။

print(s.pop())

pop ဆိုတာကတော့ နောက်ဆုံး ထည့်ထားတဲ့ data တွေကို ထုတ်လိုက်တာပါ။

Simple Balanced Parentheses

ကျွန်တော် တို့ အပေါင်း အနှုတ် အမြောက် အစားတွေ လုပ်တဲ့ အခါမှာ ကွင်းစ ကွင်းပတ်တွေကို အသုံးပြုပါတယ်။

ဥပမာ။။

(5+6)*(7+8)/(4+3)

ကျွန်တော်တို့ဟာ user က ထည့်လိုက်တဲ့ ကွင်းစ ကွင်းပိတ် တွေ မှန် မမှန် စစ်ဖို့ အတွက် stack ကို အသုံးပြုပြီး ရေးပါမယ်။

မှန်ကန်တဲ့ ကွင်းစကွင်းပိတ်တွေဟာ

(()()()())

(((())))

(()((())()))

လိုမျိုး ဖြစ်ပါလိမ့်မယ်။

((((((())

()))

(()()(()

လိုမျိုးတွေကတော့ မှားယွင်းသည်လို့ သတ်မှတ်ရပါမယ်။

# parChecker.py

from stack import Stack

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.is_empty():
                balanced = False
            else:
                s.pop()

        index = index + 1

    if balanced and s.is_empty():
        return True
    else:
        return False

print(parChecker('((()))'))

ဒီ code ကို ကျွန်တော်တို့ လေ့လာကြည့်ရအောင်။

ကျွန်တော်တို့ stack.py ကို parChecker.py နဲ့ file နေရာ အတူတူ ထားဖို့ လိုပါတယ်။

ဥပမာ။။ parChecker.py ဟာ /Users/python/ မှာ ရှိတယ် ဆိုရင် stack.py ဟာလည်း /Users/python/ နေရာမှာ ရှိဖို့ လိုပါတယ်။

ဒါမှသာ

from stack import Stack

က အလုပ်လုပ်ပါမယ်။

Python မှာ external file import format က

from filename import ClassName

ဒါကြောင့် class name က Stack ဖြစ်ပြီး file name က stack.py ဖြစ်သည့် အတွက်ကြောင့်

from stack import Stack

ဆိုပြီး ရေးထားတာပါ။

parChecker function ထဲမှာ စာလုံးရေ ရှိသလောက်ကို ကျွန်တော်တို့တွေ while loop နဲ့ ပတ်လိုက်တယ်။ နောက်ပြီးတော့ balanced က True ဖြစ်နေ သ၍ loop ပတ်ပါတယ်။ balanced က stack empty ဖြစ် မဖြစ် စစ် ဖို့ အတွက်ပါ။ ပြီးတော့ စာလုံးတွေကို တစ်လုံးခြင်း စီ ယူပါတယ်။ ကျွန်တော်တို့ trace လိုက်ကြည့်ရအောင်။

ကျွန်တော်တို့ ထည့်လိုက်တဲ့ String က (() ။

ပထမဆုံး စာလုံးက (

symbol = symbolString[index]
if symbol == "(":
    s.push(symbol)
else:
    if s.is_empty():
        balanced = False
    else:
        s.pop()

index = index + 1

ဒါကြောင့် s.push("(") ဝင်သွားပါတယ်။ တကယ်လို့သာ ပထမဆုံး စာလုံးက ( မဟုတ်ခဲ့ရင် balanced က False ဖြစ်ပြီးတော့ loop ထဲကနေ ထွက်သွားမှာပါ။

ဒုတိယ စာလုံး ( ကို ထပ်ယူတယ်။ push ထပ်လုပ်တယ်။ Array ထဲမှာ အခန်း ၂ ခန်း ဖြစ်သွားပြီ။

တတိယ စာလုံး ) ကို ယူတယ်။ pop လုပ်တယ်။ Array ထဲမှာ အခန်း ၁ ခန်း ကျန်သေးတယ်။

စာလုံးရေ ကုန်သွားသည့် အတွက် loop ထွက်သွားတယ်။

if balanced and s.is_empty():
    return True
else:
    return False

if balanced and s.is_empty(): မှာ ရေးထားသည့် condition ကြောင့် return False ပြန်ပါတယ်။

ကျွန်တော်တို့တွေဟာ () ကို စစ်သည့် အခါမှာ အဖွင့် နှင့် အပိတ် အကြိမ် အရေ အတွက် တူဖို့ လိုတယ်။ ဒါကြောင့် ( ကို stack ထဲမှာ push လုပ်ပြီး ) ကို stack ထဲကနေ ပြန်ထုတ်ပါတယ်။ () အရေအတွက် ညီရင် နောက်ဆုံး stack က empty ဖြစ်သွားပါမယ်။ နောက်ပြီးတော့ balanced ကလည်း True ဖြစ်ပြီးတော့ array ထဲကနေ ထွက်လာပါလိမ့်မယ်။

Balanced Symbol

ကျွန်တော်တို့တွေ ( နှင့် ) အတွက်ကိုတော့ ရေးပြီးပါပြီ။ နောက်တဆင့် အနေနဲ့ {[ နှင့် ]} ကို ထည့်ပြီး ရေးဖို့ လိုပါတယ်။ သင်္ချာ ကွင်းတွေက

{[()]}

ဆိုပြီး ရှိပါတယ်။ ကျွန်တော်တို့ လက်သည်းကွင်း အတွက် ရေးပြီးပါပြီ။ အခြား ကွင်းတွေပါ ပါလာရင် စစ်ဖို့ အတွက် ထပ်ပြီး ပြင်ရပါမယ်။

အဲဒီအတွက် ပြီးခဲ့တဲ့ code အတိုင်း ရေးလို့ မရတော့ပါဘူး။

from stack import Stack

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "([{":
            s.push(symbol)
        else:
            if s.is_empty():
                balanced = False
            else:
                top = s.pop()
                if not matches(top,symbol):
                       balanced = False
        index = index + 1
    if balanced and s.is_empty():
        return True
    else:
        return False

def matches(open,close):
    opens = "([{"
    closers = ")]}"
    return opens.index(open) == closers.index(close)


print(parChecker('{{([][])}()}'))
print(parChecker('[{()]'))

ဒီ code လေးကို တချက်ကြည့်ရအောင်။

ပြီးခဲ့သည့်တုန်းကလိုပဲ ကျွန်တော်တို့ ရေးထားတာပါ။ သို့ပေမယ့် အခု အခါမှာတော့ ( တစ်ခုတည်းက မဟုတ်တော့ပါဘူး။ {[]} ပါ ထပ်ပါလာပါပြီ။ ဒါကြောင့် ကွင်းစတွေဖြစ်သည့် ([{ တွေ သာ ဖြစ်ခဲ့ရင် stack ထဲ ထည့်ပါတယ်။ မဟုတ်ခဲ့ဘူးဆိုရင် stack ထဲကနေ pop လုပ်တာ တစ်ခုတည်း မရတော့ပါဘူး။ နောက်ဆုံးဖြည့်ထားတာက [ ဖြစ်ရင် ကွင်းပြန်ပိတ်တာက ] ဖြစ်ကို ဖြစ်ရပါမယ်။ ဒါကြောင့် အဖွင့် ကွင်း မဟုတ်ခဲ့လို့ အပိတ်ကွင်း သာ ဖြစ်ခဲ့ရင် ရှေ့ဘက်က ဖွင့်ထားတဲ့ ကွင်း နဲ့ တူ မလား စစ်ဖို့ လိုအပ်ပါတယ်။

top = s.pop()
if not matches(top,symbol):
    balanced = False

အဖွင့် ဖြစ်ခဲ့ရင် အပိတ်ဖြစ်သလား စစ်ဖို့ matches ဆိုတဲ့ function ကို ရေးထားပါတယ်။

def matches(open,close):
    opens = "([{"
    closers = ")]}"
    return opens.index(open) == closers.index(close)

အဲဒီမှာ index ဆိုတာ ပါလာပါပြီ။ index ဆိုတာ ထည့်လိုက်တဲ့ စာလုံးက ဘယ်နေရာမှာ ရှာတွေ့ တယ်ဆိုတဲ့ နံပတ် ပြန်လာတာပါ။

opens = "([{"
closers = ")]}"

print(opens.index("("))
print(opens.index("["))
print(closers.index("]"))
print(closers.index("}"))

ဒါကြောင့် အဖွင့် နှင့် အပိတ် index တူသလား နဲ့ လွယ်လင့် တကူ စစ်ထားတာပါ။ သို့မဟုတ်ရင် if condition နှင့် open က [ ဖြစ်ခဲ့ရင် close က ] ဖြစ်ရမယ် ဆိုပြီး စစ်နေဖို့ လိုပါတယ်။ တစ်ခါတစ်လေ programming ရေးသားရာမှာ ဖြတ်လမ်းလေးတွေ သုံးပြီး အများကြီး ရေးမယ့် အစား အခုလို အတိုလေး ရေးလို့ ရနိုင်သည့် နည်းလမ်းလေးတွေ ရှိပါတယ်။

အဖွင့် နဲ့ အပိတ် က သာ မတူခဲ့ရင်တော့ loop က ထွက်ပြီး False ပြန်ပေးလိုက်ရုံပါပဲ။

Decimal To Binary

အခု ကျွန်တော်တို့တွေ Decimal (Base 10) ကနေ Binary (Base 2) value ပြောင်းတာလေး ရေးကြည့်ရအောင်။ Computer သမား တစ်ယောက် ဖြစ်ရင်တော့ binary ဆိုတာ ဘာလဲ သိဖို့ လိုအပ်ပါတယ်။ Computer ဟာ binary value နဲ့ ပဲ အလုပ်လုပ်ပါတယ်။ value က 0 နှင့် 1 ပဲ ရှိပါတယ်။ Decimal value ကတော့ 0-9 ဂဏန်းတွေရှိပါတယ်။ ဥပမာ။ 668 ဆိုတဲ့ decimal value ကို binary ပြောင်းရင် 1010011100 ဆိုတဲ့ binary value ရပါတယ်။ ဘယ်လို ပြောင်းရ သလဲဆိုရင်တော့

668 ကို 2 နဲ့ စားသွားပါတယ်။ နောက်ဆုံး သုည ရသည့် အထိပါ။

668/2 = 334 , Mod : 0
334/2 = 167,  Mod: 0
167/2 = 83,   Mod: 1
83/2 = 41,    Mod: 1
41/2 = 20,    Mod: 1
20/2 = 10,    Mod: 0
10/2 = 5,     Mod: 0
5/2 =  2,     Mod: 1
2/2 = 1,      Mod: 0
1/2 = 0,      Mod: 1

ရလာတဲ့ mod တွေကို ပြောင်းပြန် ယူလိုက်တော့ 1010011100 ထွက်ပါတယ်။ code ဘယ်လို ရေးလို့ ရမလဲ ဆိုတာကို သဘောပေါက်လောက်ပြီ ထင်ပါတယ်။

လွယ်ပါတယ်။ ၂ နဲ့ စားသွားမယ်။ အကြွင်းတွေကို stack ထဲ ထည့်သွားမယ်။ ပြီးရင် pop ပြန်လုပ်လိုက်မယ်။ Stack က first in last out ဖြစ်သည့် အတွက်ကြောင့် ပထမဆုံး အကြွင်း ရလာဒ်က နောက်ဆုံးမှ ထွက်ပါမယ်။ Decimal to Binary ပြောင်းဖို့ အတွက် stack ကို အသုံးပြုနိုင်ပါတယ်။

from stack import Stack

def divideBy2(decNumber):
    remstack = Stack()

    while decNumber > 0:
        rem = decNumber % 2
        remstack.push(rem)
        decNumber = decNumber // 2

    binString = ""
    while not remstack.is_empty():
        binString = binString + str(remstack.pop())

    return binString

print(divideBy2(668))

code လေးကတော့ ရှင်းပါတယ်။ စားလဒ်က သုည မဖြစ်မခြင်း loop ပတ်မယ်။ နောက်ပြီးတော့ အကြွင်းတွေကို stack ထဲမှာ ထည့်ထားမယ်။

ပြီးသွားတဲ့ အခါ stack မကုန် မခြင်း loop ပတ်ပြီးတော့ pop လုပ်ပေးလိုက်ပါတယ်။

အခုလောက်ဆိုရင်တော့ Stack ကို သုံးတတ်လောက်ပြီ ထင်ပါတယ်။

လေ့ကျင့်ခန်း ၄

မေးခွန်း ၁။

Base 8 ကို ပြောင်းသည့် divdeBy8 function ကို ရေးပါ။ 668 (base 10) ၏ base 8 တန်ဖိုးသည် တန်ဖိုးသည် 1234 ဖြစ်သည်။ divideBy8(668) ၏ အဖြေသည် 1234 ထွက်လာရမည်။

class Stack:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return self.items == []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[len(self.items) - 1]
    def size(self):
        return len(self.items)

မေးခွန်း ၂။

Base 16 ကို ပြောင်းသည့် divdeBy16 function ကို ရေးပါ။ 668 (base 10) ၏ base 16 တန်ဖိုးသည် တန်ဖိုးသည် 29C ဖြစ်သည်။ divdeBy16(668) ၏ အဖြေသည် 29C ထွက်လာရမည်။ base 16 သည်

ဖြစ်သည်။ ထို့ကြောင့် အကြွင်း ကို if condition သုံးကာ 10 မှ 15 value များကို ပြောင်းပေးရန် လိုသည်။