---
# System prepended metadata

title: Data Structure - Stack in Python
tags: [Python, DataStructure]

---

# 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.
```python=1
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.
```python=1
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 
```python=1
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 :
```python=1
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.


```python=1
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 
```python=
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)
```