[파이썬 자료구조] 회문 검사

회문 검사

회문(Palindrome): 앞으로부터 읽으나 뒤로부터 읽으나 동일한 스트링

1. 전반부의 문자들을 스택에 push한 후, 후반부의 각 문자를 차례로 pop한 문자와 비교

2. 회문 검사하기는 주어진 스트링의 앞부분 반을 차례대로 읽어 스택에 push한 후

• 문자열의 길이가 짝수이면 뒷부분의 문자 1 개를 읽을 때마다 pop하여 읽어 들인 문자와 pop된 문자를 비교하는 과정을 반복 수행

•문자열의 길이가 홀수인 경우, 주어진 스트링의 앞부분 반을 차례로 읽어 스택에 push한 후, 중간 문자를 읽고 버린다.

3. 이후 짝수 경우와 동일하게 비교 수행

4. 만약 마지막 비교까지 두 문자가 동일하고 스택이 empty가 되면, 입력 문자열은 회문

파이썬 코드

def check_palindrome(expr):
    S = Stack() #구현한 스택을 사용합니다
    half = len(expr)//2 
    for e in expr[:half]: #글자의 절반을 푸시
        S.push(e)
    if len(expr)%2: #글자가 홀수일때
        start = half + 1
    else:
        start = half
    for e in expr[start:]:
        if e != S.pop():
            return False
 
    return S.is_empty()