파이썬과 함께하는 자료구조의 이해 챕터3 연습문제

챕터3은 스택, 큐, 데크 구조를 설명한 챕터이다.

스택은 뒤로만 값이 들어오고 뒤로 나가며

큐는 앞으로 나가고 뒤로 들어오고

데크는 앞뒤 전부 다 되고..

문제는 보통 스택에서 많이 나왔다.

자바 컴파일러가 syntax에러를 찾는 원리 역시 스택이고

후위표기법 역시 스택이고... 

3.6 부터 3.11 까지는 모두 스택 경우의 수를 따지는 문제이다.

수기로 일일히 찾아해보는 것이 좋다.

3.17 괄호 짝맞추기 프로그램 작성

이는 기본 스택의 원리 + 컴파일러 문법에러 찾기 문제인데

이번엔 중괄호, 소괄호 두개를 구분해야 하는게 붙었다.

def test(lst):

 # { = 123 , } = 125, (  = 40, ) = 41

 # 따라서 짝이 맞다면 두 값의 차는 

 numlst = []

 for i in lst:

  num = ord(i);

  if num == 123 or num == 40:

   numlst.append(num)

  else:

   chnum = numlst.pop();

   k = chnum - num 

   if k != -2 or k != -1  :

    return 'false lst';

    

 if len(numlst) != 0:

  return 'no lst';

  

 return 'ok lst'

문자열로 바로 확인하는 방법이 아닌 아스키 코드값으로 확인하고 짝맞추는 경우엔 두 값의 차로 계산을 해봤다. 하지만 이 경우 ) } 이런식으로 바로 닫히는 괄호가 나오면 찾지를 못했다..

3.18 회문을 검사하는 프로그램 작성

회문이란 abba 이런식으로 문자가 짝지어지는 것을 뜻한다. 데칼코마니처럼

위에 괄호 맞추는 것과 같은 원리로 하면 된다.

def checkstr(str):

 lst = list(str)

 chenum = len(lst) / 2;

 elst = []

 for i in lst:

  if len(elst) == 0:

   elst.append(i)

   k = elst[-1];

  elif k == i:

   elst.pop();

   if len(elst) == 0:

    continue;

   else:

    k = elst[-1];

  elif k != i:

   elst.append(i)

   k = elst[-1];

 

 if len(elst) != 0 :

  return 'false str'

 

 return 'ok str'   

17, 18번 원리는 다음과 같다

일단 빈 스택 리스트에 값을 하나한 집어 넣다가 같은 문자가 왔을 경우 (또는 닫히는 같은 종류의 괄호가 올경우) pop으로 스택 리스트에서 제거 해준다.

이런식으로 끝까지 반복했다면 제일 마지막에는 빈 스택리스트가 나와야한다.

만약 무언가가 남아있다면 이는 짝이 없다는 것.

3.20 후위표기법의 식을 계산하는 프로그램 작성

우리가 보통 사용하는 식은 중위표기법이다

1 + 2 + 3 이렇게.. 보기도 좋다.

후위표기법이란 12+3+ 이렇게 표현한다

이러한 식을 계산 하는 것도

결국 빈 스택 리스트에 값을 넣되 만약 사칙연산이 들어오면 그 앞서 있던 두개의 값들을 계산 해주면 된다.(식은 기본적으로 2개의 숫자와 1개의 연산자로 구성되므로 가장 짧은 후위표기식도 최소 2개의 숫자가 저장되어야한다)

1 2 + 일 경우엔  (1+2 계산 한 값)을 다시 스택에 집어 넣는다.

이런식...

def reverse_(for_lst):

 lst = []

 for i in for_lst:

  if isinstance(i, int):

   lst.append(i);

  elif i == '+':

   k = lst.pop() + lst.pop();

   lst.append(k)

   continue;

  elif i == '-':

   k = lst.pop() - lst.pop();

   lst.append(k);

   continue;

  elif i == '*':

   k = lst.pop() * lst.pop();

   lst.append(k);

   continue;

  elif i == '/':

   k = lst.pop() // lst.pop();

   lst.append(k);

   continue;

   

 return lst

괄호인 경우 까지 생각 못했다...

3.23 오늘 생각했던 문제중 가장 뿌듯했기도 하면서 어려웠던 문제..

이거때문에 아래는 생각도 못했다. 얘도 역시 괄호 버젼은 풀지도 못했다.

문제는 중위표기법을 후위표기법으로 바꾸는 코드를 짜시오 이다.

1 + 2 + 3 을 12+3+ 이렇게 바꿔야한다.

크게 스택 리스트를 두개 만들어서 하나는 숫자, 하나는 연산자만 담게 한다.

여기서 연산자 리스트에 조건이 3개가 갈린다.

위의 1+2+3의 예시는 간단하지만

만약 1 + 2 * 3 이라면? 사칙연산 때문에 123*+ 가 된다.

즉 * , / 때문에 고민을 한번 더 해야한다.

그렇기에 만든 조건은 다음과 같다(feat 승완군..

0. +,- 와 *, / 를 서로 다른 가중치를 두어 구분한다.

나의 경우 +,- 는 1로, * , / 는 2로 구분지었다.

0. 항상 연산자 리스트에 있는 요소가 무엇인지 확인한다.

그리고 새로 들어오는 값을 비교한다

1. + 가 있을 경우에 +와 같은 가중치 값이 연산자 리스트로 들어온다면 

기존에 있던 +를 숫자 리스트로 보내버린 후 새 값을 연산자 리스트에 넣는다.

즉 1 + 2 - 3 의 경우

숫자 리스트 : 1,2

연산자 리스트 + 인 상황에서 -가 들어올때 1의 조건에 걸리므로

숫자: 1,2,+

연산자 : -

이렇게 저장이 된다.

2. +가 있을 경우에 + 보다 가중치 값이 큰 연산자가 들어온다면 연산자 리스트에 그대로 쌓는다.

즉 1 + 2 * 3 의 경우

숫자 : 1 2

연산자: + 인 상황에서 *가 들어와야 한다.

2의 조건에 걸리므로

숫자 : 1,2

연산자 : +, * 가 된다.

3. 만약 가중치가 작은 값이 새로 들어온다면? 즉 *, /가 있는 상황에서+, -가 들어온다면 기존에 있던 애들을 모두 숫자로 보낸 후 새로 들어오는 값을 연산자에 넣어준다.

즉 1+ 2 * 3 -4 인 경우

숫자: 12

연산자: +* 인 상황에서 - 가 들어와야 한다.

3의 조건에 걸리므로

숫자: 12*+(+,*를 pop()으로 뽑아서 *,+ 로 들어왔다)

연산자 - 가 된다

그리고 모두 다 돌아가면 연산자 리스트에 있는 애들을 전부 숫자로 옮겨주면 된다.

def make_for2(lst):

 chlst = {'+' : 1, '-': 1,'*':2, '/':2}

 str_lst = []

 op_lst = []

 for i in lst:

  if isinstance(i, int):

   str_lst.append(i)

   if i == lst[-1]: # 모두 다 돌아갔을때, 즉 마지막 값이 숫자일 경우를 뜻한다.

    num = len(op_lst)

    for n in range(num):

     str_lst.append(op_lst.pop())

   continue;

  else:

   if len(op_lst) == 0:

    op_lst.append(i);

   elif chlst[i] == chlst[op_lst[-1]]: # 키 값이 같으면

    str_lst.append(op_lst.pop())

    op_lst.append(i)

    continue;

   elif chlst[i] > chlst[op_lst[-1]]: # 새로 들어오는게 기존보다 크면

    op_lst.append(i) # 연산자 스택에 쌓는다

    continue;

   elif chlst[i] < chlst[op_lst[-1]]: # 새로 들어오는게 나보다 작으면

    # 새로 들어오는 것을 산술 스택에 쌓고 그 이전에 있던 애도 산술 스택에 쌓는다

    num = len(op_lst)

    for n in range(num):

     str_lst.append(op_lst.pop())

    op_lst.append(i);

 return str_lst;

 

물론 위 경우는 아직 괄호를 고려하지 않은 경우이다.

괄호 경우도 구상은 해놨는데 아직 코드화를 못했다.

스택 문제를 다 푼것은 아니지만 스택의 꽃은 후위표기법이라 생각한다.

생각보다 재밌다.