자료구조 및 실습 - [6] 스택 실습문제 (파이썬으로 심볼균형, 후위수식 구현하기) (2)

심볼균형

 

스택 ADT를 연결리스트로 구현하여 심볼들의 균형을 검사하는 프로그램을 작성하라

심볼 균형이란 (),[] 등과 같이 괄호의 짝이 맞는지 판단하는 것을 뜻한다. 입력 예시와 출력 예시를 살펴보자.

>>> (3+40*(2+(30-7)*2133)
Wrong_5 # 심볼 균형이 이루어 지지 않았으며, 문장안의 괄호의 개수가 5개이다.

>>> 3*{4+(2-792)/1} + [3*{4-2* (100 -7)}]
OK_10 # 심볼 균형이 이루어 졌으며, 문장안의 괄호의 개수가 10개이다.

>>> 301*{4+(2101-7)/1} + 9*{4-2* (10108-7)}}
Wrong_9 # 심볼 균형이 이루어 지지 않았으며, 문장안의 괄호의 개수가 9개이다.

>>> (3*{4001+(2-7)/1} + [3*{4-2* (1-7)}])
OK_12 # 심볼 균형이 이루어 졌으며, 문장안의 괄호의 개수가 12개이다.

 

단순히 심볼균형만 판단하는 것이 아니라 괄호의 총 갯수까지 출력해주어야 한다. 괄호 갯수가 홀수인것으로도 심볼균형을 확인할 수도 있겠다. 하지만 짝수라고 모든 심볼균형이 맞는것은 아니기 때문에 주의해야 한다.

 

 

먼저 파이썬의 Class를 활용해 단일연결리스트로 스택ADT를 구현하자.

#단일연결리스트에 기초한 스택
class Node:
  def __init__(self,data,next=None):
    self.data = data
    self.next = next

class stack:
  def __init__(self,N):
    self.top = None
    self.full = N
    self.stacksize=0

  def push(self,data):
    newnode = Node(data,self.top)
    self.top = newnode
    self.stacksize +=1

  def isEmpty(self):
    if self.top == None:
      return True
    else:
      return False
  
  def pop(self):
    if self.isEmpty():
      print("Stack Empty")
    elem = self.top.data
    p = self.top
    self.top = self.top.next
    del(p)
    self.stacksize -=1
    # print("pop :",elem) #pop한 원소를 출력
    return elem
  
  def printstack(self):
    target = self.top
    if self.isEmpty():
      print("None")
    else:
      while (target.next != None):
        print(target.data,end = ",")
        target = target.next
      print(target.data)
  
  def peek(self):
    if self.top == None:
      print("Stack Empty")
    else:
      print(self.top.data)
  
  def duplicate(self):
    new = self.pop()
    if self.stacksize ==self.full:
      print("Stack Full")
    else:
      self.push(new)
    if self.stacksize ==self.full:
      print("Stack Full")
    else:
     self.push(new)

이번에는 괄호의 짝을 확인하는 함수를 구성해보자.

심볼균형의 의사코드

의사코드를 보면 코드 진행방식은 다음과 같다.

1. 빈 스택을 하나 생성한다.
2. 입력을 끝까지 확인하는 반복문을 돌린다.
3. 첫번째 입력을 확인한다.
4. 만약 열린 괄호모양 ("(", "{", "[") 이면 생성했던 스택에 push한다.
5. 만약 닫힌 괄호모양 (")", "}", "]") 인데, 
5-1. 만약 스택이 비어있다면 -> 심볼 균형이 맞지 않으므로 False를 return한다.
5-2. 변수 top에 스택의 원소를 pop한 후, 심볼의 짝이 맞는지 확인한다.
5-3. 짝이 맞지 않으면 False를 return 한다.
6. 최종적으로 스택이 비어있으면 True, 스택에 원소가 남아있으면 False를 return한다.

 

이를 그대로 파이썬으로 구현해보자.

def symbol_check(string):
  st = stack(1000)
  open_symbol = ["(","{","["] #열린 괄호 모음을 리스트에 저장
  close_symbol = [")","}","]"] # 닫힌 괄호 모음을 리스트에 저장
  cnt=0 # 괄호 갯수 카운트
  F=0 # 중간에 심볼균형이 맞지 않았을 때 F에 값을 추가하여 F가 0 초과면 Wrong 출력
  for i in range(len(string)):
    s = string[i]
    if s in open_symbol:
      st.push(s)
      cnt+=1
    elif s in close_symbol:
      cnt+=1
      if st.isEmpty():
        F+=1
      else:
        t = st.pop()
        if not ((s==close_symbol[0] and t ==open_symbol[0]) or (s==close_symbol[1] and t ==open_symbol[1]) or (s==close_symbol[2] and t ==open_symbol[2]) ):
          F+=1
  if not st.isEmpty():
    return print(f"Wrong_{cnt}")
  elif F>0:
    return print(f"Wrong_{cnt}")
  else:
    return print(f"OK_{cnt}")

코드를 구성하며 돌아가는 순서를 잘 생각하여 들여쓰기를 하자!  맨 처음에 구현했을 때 되면서... 안되면서... 하길래 계속해서 과정을 출력했는데, 결국은 조건에 맞게 들여쓰기를 잘못해서 그런 것이었다. 현재는 잘 실행된다.

 

---

후위수식

후위수식 문제는 스택을 공부하면서 꼭 나오는 문제인 것 같다. 후위수식이란 연산 표기법 중 하나이며, 우리는 흔히 '중위수식'을 사용하여 '후위수식' 표기법을 보면 다소 이상하게 느껴질 수 있다. 후위수식의 예시는 다음과 같다.

#1 
중위 수식 : 5*3+2+(6+3)*2
후위 수식 : 53*2+63+2*+

#2
중위 수식 : 2+3*4
후위 수식 : 234*+

#3
중위 수식 : 7/2-3+4*2-2*1
후위 수식 : 72/3-42*+21*-

#4
중위 수식 : 9+(2*3+1)*2
후위 수식 : 923*1+2*+

 

후위수식에는 두가지 메서드가 있다.

convert() : 중위 수식을 후위수식으로 전환

evaluate() : 후위 수식을 평가

 

convert 메서드의 의사코드를 살펴보자.

convert 메서드의 의사코드

의사코드에 의한 순서는 다음과 같다.

1. 먼저 연산자의 우선순위정보가 담긴 P를 정의해야 한다. 
2. 빈 스택을 하나 생성한다.
3. 수식을 하나하나 확인하는 반복문을 돈다.
4-1. 만약 현재 해당하는 수식이 숫자이면 출력한다.
4-2. 만약 "("면 스택에 push한다.
4-3. 만약 ")"일때 스택의 top이 "("이 아닐때까지 pop하면서 출력 하고 반복문 탈출후 pop을 한번 더한다.
4-4. 만약 연산자면 스택이 비어있지 않으면서 스택의 top에 있는 연산자의 우선순위가 현재 연산자의 우선순위보다 높은 경우 반복문을 계속 돌면서 pop하면서 출력한다. 이후 반복문 탈출하면 현재 연산자를 push한다.
5. 스택이 빌때까지 pop하면서 출력한다.

 

사실 Python의 리스트에서 pop과 append로 스택을 흉내낼 수 있기 때문에, 이번에는 이를 활용하여 코드를 구성했다.

def convert(string):
  p = {"(":0,"+":1,"-":1,"*":2,"/":2}
  num = ["0","1","2","3","4","5","6","7","8","9"]
  stack = []
  lastcnt =0
  kkk=''
  while lastcnt != len(string):
    s = string[lastcnt]
    if s in num:
      print(s,end="")
      kkk=kkk+s
    elif s == '(':
      stack.append(s)
    elif s== ')':
      while stack[-1] != '(':
        print(stack.pop(),end="")
        kkk=kkk+s
      stack.pop()
    else:
      while len(stack)!=0 and (p[s]<=p[stack[-1]]):
        print(stack.pop(),end ="")
        kkk=kkk+s
      stack.append(s)

    lastcnt+=1
  while len(stack)!=0:
    print(stack.pop(),end = "")
    kkk=kkk+s
  return kkk

 

evaluate 메서드의 의사코드를 살펴보자.

evaluate 메서드의 의사코드

의사코드에 의한 순서는 다음과 같다.

1. 빈스택 생성한다.
2. 수식을 끝까지 도는 반복문 실행한다.
3. 만약 숫자면 스택에 push한다.
4. 만약 연산자라면 a와b에 pop해서 저장 후 계산한 값을 스택에 push한다.
5. 반복문 탈출 후 스택에 있는 원소를 pop한다

def doOperator(op,x,y):
  if op =='+':
    v = int(x)+int(y)
  elif op == '-':
    v = int(x)-int(y)
  elif op == '*':
    v = int(x)*int(y)
  elif op == '/':
    v = int(x)/int(y)
  return v

def evaluate(string):
  stack = []
  num = ["0","1","2","3","4","5","6","7","8","9"]
  for i in range(len(string)):
    s = string[i]
    if s in num:
      stack.append(s)
    else:
      a = stack.pop()
      b = stack.pop()
      stack.append(doOperator(s,b,a))
  print(stack.pop())