[자료구조] 수식 평가_중위, 후위, 전위 (in python)

Data Structure & Algorithm

[자료구조] 수식 평가_중위, 후위, 전위 (in python)

여뉴누 2023. 6. 18. 21:05

728x90

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님

[목차]

1. 수식 표기 방식

2. 후위 수식 계산

3. 중위 -> 후위 변환

1. 수식 표기 방식

(1) 중위 표기법

연산자를 두 피연산자 사이에 표기
사람이 이해하기 좋은 표현법
우선순위에 따라 연산 순서 결정
괄호에 의해 연산 순서 조정

(2) 후위 표기법

피연산자를 먼저 표시하고 연산자를 나중에 표시
컴퓨터가 이해하기 좋은 표현법
우선순위 상관없음
괄호 없음

(3) 전위 표기법

연산자를 먼저 표시하고 연산에 필요한 피연산자를 나중에 표기

(4) 중위 vs 후위 vs 전위

(5) 연산자 우선순위 (C 기준)

2. 후위 수식 계산

(1) 기본 과정

수식의 왼쪽부터 토큰(문자)을 읽어냄
읽어낸 토큰이 피연산자 -> 스택에 push
읽어낸 토큰이 연산자 -> 스택에 포함되어 있는 가장 최근에 추가된 두 개의 피연산자를 pop
pop한 피연산자 두 개와 읽어낸 연산자로 연산을 수행 후 결과를 스택에 push
모든 연산이 끝나고 나면 스택 내에 연산의 결과인 숫자 하나만 남게 됨

(2) 코드 구현

두 가지 과정으로 분류 가능
- 과정 1) 읽어낸 토큰이 연산자인지 피연산자인지 파악
- 과정 2) 후위 수식 계산

과정 1) 읽어낸 토큰이 연산자인지, 피연산자인지 파악

  def getSymtype(self, sym):
    if sym == '+' : sym_type = 'Sym_PLUS'
    elif sym == '-' : sym_type = 'Sym_MINUS'
    elif sym == '*' : sym_type = 'Sym_TIMES'
    elif sym == '/' : sym_type = 'Sym_DIVIDE'
    elif sym == '%' : sym_type = 'Sym_MOD'
    else: sym_type = 'Sym_OPERAND'
    return sym_type

과정 2) 후위 수식 계산

  def eval_postfix(self):
    for sym in self.expr:
      print(sym, end = ' ')
      sym_type = self.getSymtype(sym) 
      	# 과정 1)의 함수를 사용하여 연산자의 종류 또는 여부를 파악
      if sym_type == 'Sym_OPERAND': 
      	# 숫자이면
        self.push(int(sym)) 
        	# int형으로 변환 후 스택에 바로 추가
      else:
        op2 = self.pop() 
        	# op1 (연산자) op2 순으로 연산을 진행하기 위해
        op1 = self.pop() 
        	# op2는 가장 끝의 원소, op1은 그 전 원소를 추출
        # 각 연산자의 종류에 맞게 연산 후 연산 결과를 다시 스택에 넣어줌 
        if sym_type == 'Sym_PLUS': 
          self.push(op1 + op2)
        elif sym_type == 'Sym_MINUS':
          self.push(op1 - op2)
        elif sym_type == 'Sym_TIMES':
          self.push(op1 * op2)
        elif sym_type == 'Sym_DIVIDE':
          self.push(op1 // op2)
        elif sym_type == 'Sym_MOD':
          self.push(op1 % op2)
    return self.pop() 
    	# 모든 원소에 대해 연산이 이루어지고 나면 연산의 결과인 수 하나밖에 스택에 남지 않음 
        -> 그걸 반환해주면 그게 바로 결과

결과)

e = Expression('57*9+34/-')
e.eval_postfix()

(3) 전체 코드

class Expression:
  def __init__(self, expr):
    self.stack = []
    self.size = 100
    self.expr = expr # 연산식을 문자열로 받아 self.expr에 저장
    self.top = -1
  
  # 스택 구현
  def isEmpty(self):
    return len(self.stack) == 0
  
  def isFull(self):
    return self.size == len(self.stack)
  
  def push(self,item):
    if not self.isFull():
      self.top += 1
      self.stack.append(item)
      self.view()
    else: print("stack is full")

  def pop(self):
    if not self.isEmpty():
      self.top -= 1
      return self.stack.pop()
    else: print('stack is empty')
  
  def view(self):
    print(self.stack)
  
  # 후위 수식 계산
  def eval_postfix(self):
    for sym in self.expr:
      print(sym, end = ' ')
      sym_type = self.getSymtype(sym) 
      if sym_type == 'Sym_OPERAND': 
        self.push(int(sym)) 
      else:
        op2 = self.pop() 
        op1 = self.pop() 
        if sym_type == 'Sym_PLUS': 
          self.push(op1 + op2)
        elif sym_type == 'Sym_MINUS':
          self.push(op1 - op2)
        elif sym_type == 'Sym_TIMES':
          self.push(op1 * op2)
        elif sym_type == 'Sym_DIVIDE':
          self.push(op1 // op2)
        elif sym_type == 'Sym_MOD':
          self.push(op1 % op2)
    return self.pop() 
  
  # 각 연산자 파악
  def getSymtype(self, sym):
    if sym == '+' : sym_type = 'Sym_PLUS'
    elif sym == '-' : sym_type = 'Sym_MINUS'
    elif sym == '*' : sym_type = 'Sym_TIMES'
    elif sym == '/' : sym_type = 'Sym_DIVIDE'
    elif sym == '%' : sym_type = 'Sym_MOD'
    else: sym_type = 'Sym_OPERAND'
    return sym_type

3. 중위 -> 후위 변환

(1) 기본 과정 (컴퓨터에서)

수식을 왼쪽부터 읽어 가면서
읽은 피연산자는 읽는 대로 출력
읽은 연산자는 스택의 top 연산자와 우선순위 비교 후 처리
- case 1) top 연산자의 우선순위 >= 읽은 연산자 우선순위
  : top 연산자를 pop -> 읽은 연산자는 스택에 push
- case 2) top 연산자의 우선순위 < 읽은 연산자의 우선순위
  : 읽은 연산자를 스택에 push
- case 3) 더이상 읽어지는 것이 없음 (== eos)
  : 스택에 남은 연산자를 모두 pop
만약에 중위 수식에 괄호가 포함되어 있다 ?
- '(' 는 읽히면 바로 스택에 push
- '(' 이후 연산자들에 대해서는 위의 case1, 2, 3의 과정을 따름
- ')' 이 읽히면 '(' 이후로 스택에 push되어 있는 모든 연산자를 pop

(+) 식 변환 방식에 대한 나의 이해
후위 연산자를 컴퓨터에서 받아들이고 연산을 실행할 때 앞에 나와있는 연산자부터 실행한다. 따라서 먼저 실행되어야 하는 연산자들이 앞에 위치해야 한다. 그럼 먼저 실행되어야 하는 연산자란 무엇일까 ? 우선순위가 높은 연산자이거나 우선순위가 동일함에도 먼저 식에 등장한 연산자가 바로 먼저 실행되어야 하는 연산자이다. 따라서 top 연산자와 비교했을 때 top 연산자의 우선순위가 높거나 같으면(식에 먼저 등장했다는 의미) 먼저 top 연산자를 식으로 빼줘 식에서 앞쪽에 위치하게 해준 뒤, 이번에 입력받은 연산자는 스택에 넣어주는 것이다.

(2) 코드 구현

두 가지 과정으로 분류 가능
- 과정 1) 연산자 우선순위 배정
- 과정 2) 중위 수식의 후위 수식으로의 변환

과정 1) 연산자 우선순위 배정

  def precedence(self, op): # 연산자 우선순위 배정 함수
    if op == '(': return 0
    elif op in ['+', '-']: return 1
    elif op in ['*', '/', '%']: return 2

과정 2) 중위 수식의 후위 수식으로의 변환

  def infix_postfix(self): 
    for token in self.expr:
    	# 수식을 문자열로 받아 문자열의 문자를 token이라는 변수에 하나씩 받아옴
      print(f"{self.i}번째 연산자")
      print("token: ", token)
      if token.isalnum(): 
      	# token이 만약에 숫자이거나 알파벳이면
        self.output += token
         	# 후위수식결과가 될 문자열에 token을 추가
      elif token == '(': 
      	# 괄호의 시작이 들어오면
        self.push(token)     
        	# 바로 스택에 push하고
      elif token == ')':
      	# 괄호가 끝났다면
        sym = self.pop()
          # 괄호가 끝나기 바로 이전에 추가된 연산자를 sym 변수에 넣고
        while sym != '(' and sym != None : 
          # 스택에서 읽어낸 연산자가 '('이거나 더이상 읽어낼 것이 없을 때 stop
          self.output += sym 
          	# 후위수식결과가 될 문자열에 sym을 추가
          sym = self.pop() 
          	# '(' 이후에 추가된 연산자들을 계속 반복적으로 삭제하고 가져옴
      else: 
      	# 알파벳, 숫자, 괄호 모두 다 아니면 = 연산자이면
        while not self.isEmpty() and self.precedence(self.stack[-1]) >= self.precedence(token):
          # 스택이 비어있지 않고 top의 우선순위가 현재 삽입하려는 연산자보다 높거나 같을 동안
          sym = self.pop() 
          	# top 연산자를 삭제 + 가져와서 sym에 넣어주고
          self.output += sym
          	# 후위수식에 추가시켜줌
        self.push(token)
          # while문이 종료되었으면 현재 읽어낸 연산자를 push
      # 아래 세 줄은 결과를 보기 위해 임의로 추가
      #print("output: ", self.output)
      #print() 
      #self.i += 1
    while not self.isEmpty():
    	# 스택이 빌 때까지
      self.output += self.pop()
      	# 스택에 남아있는 모든 연산자를 pop해서 후위수식에 추가

결과)

e = Expression('5*7+1')
e.infix_postfix()
print("최종 결과: ", e.output)

(3) 전체 코드

class Expression:
  def __init__(self, expr):
    self.stack = []
    self.size = 100
    self.expr = expr # 연산식을 문자열로 받아 self.expr에 저장
    self.top = -1
    self.output = '' # 후위 연산식으로 변환한 결과를 저장할 str형식의 공백 문자열
    self.i = 1
  
  # 스택 생성 (self.stack)
  def isEmpty(self):
    return len(self.stack) == 0
  
  def isFull(self):
    return self.size == len(self.stack)
  
  def push(self,item):
    if not self.isFull():
      self.top += 1
      self.stack.append(item)
      self.view()
    else: print("stack is full")

  def pop(self):
    if not self.isEmpty():
      self.top -= 1
      return self.stack.pop()
    else: print('stack is empty')
  
  def view(self):
    print("stack: ",self.stack)
  
  def precedence(self, op): # 연산자 우선순위 배정 함수
    if op == '(': return 0
    elif op in ['+', '-']: return 1
    elif op in ['*', '/', '%']: return 2
  
  def infix_postfix(self): # 중위 -> 후위 변환 함수
    for token in self.expr:
      print(f"{self.i}번째 연산자")
      print("token: ", token)
      if token.isalnum():
        self.output += token
      elif token == '(':
        self.push(token)      
      elif token == ')':
        sym = self.pop()
        while sym != '(' and sym != None :
          self.output += sym
          sym = self.pop()
      else:
        while not self.isEmpty() and self.precedence(self.stack[-1]) >= self.precedence(token):
          sym = self.pop()
          self.output += sym
        self.push(token)
      # 아래 세 줄은 결과를 보기 위해 임의로 추가
      #print("output: ", self.output)
      #print() 
      #self.i += 1
    while not self.isEmpty():
      self.output += self.pop()

728x90