# Data Structure - Stack in Python
###### tags: `DataStructure` `Python`

> Written by @Chihung0522
> [Reference](https://www.youtube.com/watch?v=lVFnq4zbs-g&list=PL5tcWHG-UPH112e7AN7C-fwDVPVrt0wpV)
> > [time=Sun, Mar 29, 2020 9:06 PM]

The basic structure of stack in python object.

class Stack():
    def __init__(self):
        self.items=[]

    def push(self,item):
        self.items.append(item)

    def pop(self):
        index = len(self.items)-1
        return self.items.pop(),index

    def is_empty(self):
        return self.items == []

    def get_stack(self):
        return self.items

    def stack_look(self):
        if not self.is_empty():
            for index in range(1,len(self.items)+1):
                print( "|" + self.items[-index] + "|" )
            print(" - ")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            return None
    

## Ex1 : Check for balanced parenthesis using stack

**Input a strin of parenthesis and check wheather all the parenthesis match up properly.**

||||
| :--------: | :--------: |:------:|
| Input | A string of parenthesis |"[ { ( ) { } } ]" |
|Output | Balanced or not |True or False|

---

### Terminology

> [ ] : square bracket :
> { } : curly brackets,curly braces
> ( ) : Round brackets
> < > : Angle brackets

### Example
- balanced example : { ( ) }
- Non-Balanced example : { ( } , (()

### Step
- [ ] Loop through the string from the beginning,and analyze the character.
- [ ] If encounter a open parenthesis, push it to the Stack .
- [ ] If encounter a close parenthesis, pop the very top element of stack and check wheather it matched each other.
- [ ] If matched properly, pop up the previous parenthesis in the stack.
- [ ] If finally the stack is empty then the result is balanced.

### Code
Use the obj built previously.

from stack import Stack

def is_paren_balanced(paren_string:str):
    s = Stack()
    is_balanced = True
    index = 0 

    while index<len(paren_string) and is_balanced:
        check_paren = paren_string[index]
        if check_paren in '[{(':
            s.push(check_paren)
        else:
            if s.is_empty():
                is_balanced=False
            else:
                stack_top = s.pop()
                if not is_matched(stack_top,check_paren):
                    is_balanced=False
        index +=1
    return s.is_empty() and is_balanced
    
# check if it is matched 
def is_matched(p1,p2):
    if p1=='(' and p2==')':
        return True
    elif p1=='[' and p2==']':
        return True
    elif p1=='{' and p2=='}':
        return True
    else:
        return False

## Ex2 : Use stock structure to convert a integer values to binary

### Terminology
>Quotient : 商
>Reminder : 餘數

### Step
- [ ] Divide the integer by 2 until quotient is 0
- [ ] Put the reminder into a stack after every iteration
- [ ] If the loop is finished, pop up all the element in the stack

### Code

from stack import Stack

def  IntToBinary(num:int):
    s = Stack()
    bin_str=''
    if num > 0:
        while num >0 :
            reminder = num % 2 
            s.push(reminder)
            num = num // 2 
        
        while not s.is_empty():
            bin_str += str(s.pop())
        return bin_str
    else:
        return 0

---
## LeetCode practice 1 : [happy number](https://leetcode.com/problems/happy-number/)

### Code
Use the stack instance to solve it :

class Solution:
    def isHappy(self, n: int) -> bool:
        s = Stack()
        global new_n 

        endless_val = set()
        while not n in endless_val:
            print(n)
            endless_val.add(n)
            
            new_n = 0
            for digit in str(n):
                new_n += int(digit)**2

            for num in str(new_n):
                s.push(num)

            while not s.is_empty():
                happy = True
                pop_num,index = s.pop()

                if index == 0 and pop_num =='1':
                    return happy
                elif index == 0:
                    s.items=[]
                    n = new_n

                if index != 0 and pop_num!='0':
                    s.items=[]
                    n = new_n
        return False

But after solve it on my own,I found a very clean code that doing the same thing without redundant if-else statement.

def _isHappy( n):
    stack=[]
    n=str(n)
    while n not in stack:
        #print(n)
        num=0
        stack.append(n)
        for string in n:
            num+=int(string)**2
        n=str(num)
        if n=='1':
            return True
    return False

## LeetCode practice 2 : [Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)

### Code

def minCostClimbingStairs(self, cost: List[int]) -> int:
    prev, step = cost[:2]     
    for c in cost[2:]:
        prev, step = step, c + min(prev, step)
    return min(prev, step)