초보몽키의 개발공부로그

강의노트 21. 자료구조 - stack을 이용한 후위표기법 계산기 만들기

18 Apr 2017 |

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

후위표기법(postfix notation)

  • 수업자료
  • 연산자를 피연산자의 뒤에 놓는 방법 (사람이 사용하는 수식의 표기 방법 - 중위(infix) 표기법)
  • 괄호가 없어도 계산 순서가 일정하다.
  • 컴퓨터에서의 수식의 계산은 (1) 수식을 후위표기식으로 바꾸고 (2) 후위표기식을 계산하는 두 과정으로 이루어진다.
views
출처 : https://github.com/ythwork

후위표기법 만들기

  • 상세 내용은 상기 수업 자료를 참고한다.

준비물

  1. listExp : 최종 후위 수식을 담을 리스트
  2. stack : LIFO 방식의 자료구조, 연산자를 가중치에 따라서 담을 스택 리스트

연산자 우선순위

  1. *, / : 제일 크다
  2. +, - : 두번째
  3. ( :가장 작다

규칙

  • 중위표기법 : (2 + 5) * 3 * (2 + 1) ==> 후위표기법: 25 + 3 * 21 + *
  • 숫자가 오면 listExp 에 담는다.
  • 숫자가 아닌 연산자는 stack에 쌓는다.
  • stack 의 맨 위 연산자의 가중치가 새로 추가되는 연산자의 가중치 보다 높거나 같다면 listExp로 옮긴다.
  • ( 는 가중치에 상관 없이 무조건 stack에 쌓는다.
  • )를 만나는 순간 ( 위에 있는 모든 연산자를 listExp에 pop 으로 넣고 ( 는 없앤다.

stack을 이용한 후위표기법 계산기 만들기

ADT 인터페이스

Data

org_exp # 중위표기법 (유저에게 입력 받으며 공백을 삭제하여 저장한다)
postfix_exp # 후위표기법 (유저에게 입력 받은 중위 표기법을 후위 표기법으로 변경하여 저장한다.)

Opertion

.get_weight(self, oprt)
# 인자로 받은 연산자의 가중치를 리턴한다.
# 가중치 순서 : *, / > +, - > (

.convert_to_postfix(self)
# 인스턴스 변수 org_exp를 후위표기법으로 변경하여 postfix_exp 변수에 저장한다.
# 가중치에 따라서 연산자를 담을 스택과, 최종 후위 수식을 담을 리스트를 활용한다.

.get_postfix_exp(self)
# postfix_exp 변수에 담긴 값을 리턴한다. 없다면 convert_to_postfix()을 실행한다.

.calc_two_oprd(self, 피연산자1, 피연산자2, 연산자)
# 연산자의 종류에 따라서 연산을 진행한 결과를 리턴한다.

.calculate(self)
# postfix_exp 변수에 담긴 후위수식 값을 연산한 결과를 리턴한다.

구현코드

from stack import Stack

class Calculator:
    def __init__(self, org_exp):
        self.org_exp = org_exp.replace(' ', '')
        self.postfix_exp = None

    def get_weight(self, oprt):
        if oprt == '*' or oprt == '/':
            return 9
        elif oprt == '+' or oprt == '-':
            return 7
        elif oprt == '(':
            return 5
        else:
            return -1

    def convert_to_postfix(self):
        exp_list = []
        oprt_stack = Stack()

        for ch in self.org_exp:
            if ch.isdigit():
                exp_list.append(ch)
            #연산자라면
            else:
                #'(' or 연산자 스택이 비었다면
                if ch == '(' or oprt_stack.is_empty():
                    oprt_stack.push(ch)
                #')'
                elif ch == ')':
                    op = oprt_stack.pop()
                    while op != '(':
                        exp_list.append(op)
                        op = oprt_stack.pop()
                #'+', '-', '*', '/' : 가중치가 높을 때
                elif self.get_weight(ch) > \
                    self.get_weight(oprt_stack.peek()):
                    oprt_stack.push(ch)
                #'+', '-', '*', '/' : 가중치가 낮거나 같을 때
                else:
                    while oprt_stack and self.get_weight(ch) <=\
                          self.get_weight(oprt_stack.peek()):
                        exp_list.append(oprt_stack.pop())
                    oprt_stack.push(ch)
        while oprt_stack:
            exp_list.append(oprt_stack.pop())
        self.postfix_exp = ''.join(exp_list)

    def get_postfix_exp(self):
        if not self.postfix_exp:
            self.convert_to_postfix()

        return self.postfix_exp

    def calc_two_oprd(self, oprd1, oprd2, oprt):
        if oprt == '+':
            return oprd1 + oprd2
        elif oprt == '-':
            return oprd1 - oprd2
        elif oprt == '*':
            return oprd1 * oprd2
        elif oprt == '/':
            return oprd1 // oprd2

    def calculate(self):
        oprd_stack = Stack()

        for ch in self.postfix_exp:
            if ch.isdigit():
                oprd_stack.push(int(ch))
            #연산자라면
            else:
                oprd2 = oprd_stack.pop()
                oprd1 = oprd_stack.pop()
                oprd_stack.push(self.calc_two_oprd(
                    oprd1, oprd2, ch))
        return oprd_stack.pop()

if __name__ == "__main__":
    a = input("수식을 입력하세요 : ")
    calc = Calculator(a)
    print(calc.get_postfix_exp())
    print("{exp} = {result}".format(
        exp = calc.org_exp, result = calc.calculate()))

Related Posts