[자료구조] stack을 활용하여 계산기 코드작성해보기

중위,전위,후위 표현법

• 중위표현법(Infix Expression)
  - 일반적으로 사용하는 연산자가 피연산자 사이에 위치하는 구조
• 전위표현법(Prefix Expression)
  - 연산자가 피연산자 앞에 있는형태
• 후위표현법(Postfix Expression)
  - 연산자가 피연산자 뒤에 있는형태



이후 작성할 코드는 아래 두가에대한 예외처리를 하지않았습니다.

• int type + 연산자 4개를 제외한 다른 input값에 대한 예외처리
• 잘못된 infix수식에대한 예외처리

계산기 코드 작성순서

1. infix 공식을 postfix or prefix로 변환하는 함수를 작성한다.
2. 변환된 공식을 계산하는 함수를 작성한다.

계산기 코드 작성규칙 몇가지

1. 피연산자(operand)와 연산자(oprator)를 의미하는 하나의 단위는 token이라고 칭한다.
2. 모든연산자는 이항 연산자로 취급한다.
3. prefix와 postfix는 괄호가 없기때문에 변환시 괄호는 삭제한다

infix를 postfix로 만들기

연산을 위해 중간에 stack을 하나 사용하나 사용한다.

• 연산 우선순위를 표시 하기위해 괄호를 친다
• 피연산자는 postfix리스트로 바로 추가한다.
• 연산자는 stack으로 들어간다.
  - 이때 stack안에 본인보다 우선순위가 높은 연산자들을 모두 pop한다
• 여는괄호 '(' 는 연산우선순위 최하위로 취급한다.
• 닫는괄호 ')'는 stack안에서 '('를 만나기전까지 모든 연산자를 pop한다
• postfix는 괄호가 존재하지 않기에 괄호는 연산만 하며 postfix리스트에 추가되진 않는다.

def infix_to_postfix(infix):
    for token in infix:
        if '피연산자일 경우':
            'postfix로 push'
        elif '(일 경우':
            'stack으로 push'
        elif ')일 경우':
            'stack에서 (를 만날때까지 stack안의 모든 연산자를 postfix로 push'
        elif token in '+ - * /':
            '자신보다 우선순위가 높은 연산자를 pop()하여 postfix로 넣는다'
            '자신이 stack으로 들어간다'
     'stack에 남은 모든 연산자를 postfix로 보낸다'
     return postfix

실제 돌아가는 코드

def infix_to_postfix(infix: list)-> list:
    operators = ['+', '-', '*', '/']
    level1_operators = ['+', '-']
    level2_operators = ['*', '/']
    stack = Stack()
    postfix = []
    
    for token in infix:
    	# 피연산자일 경우 바로 postfix로 push
        if type(token) in [int, float]:
            postfix.append(token)
            
        # '('일 경우 바로 스택으로
        elif token == '(':
            stack.push(token)
            
        # ')'일 경우 스택에서 '('를 만날때까지 스택의 토큰들을 posfix로 push
        elif token == ')':
            stack_token = stack.pop()
            while stack_token != '(':
                postfix.append(stack_token)
                stack_token = stack.pop()
        
        # 연산자일경우 우선순위를 따져서 수행
        elif token in operators:
            for i in range(len(stack.items)+1):
                if token in level1_operators:
                    if stack.top() in level2_operators:
                        postfix.append(stack.pop())
                    else:
                        stack.push(token)
                        break
                elif token in level2_operators:
                    if stack.top() in level1_operators:
                        postfix.append(stack.pop())
                    else:
                        stack.push(token)
                        break
    # 스택의 남은 연산자들을 모두 posfix로 push
    while len(stack)>0:
        postfix.append(stack.pop())
    return postfix

 

• infix 수식의 괄호는 수동으로 쳐야합니다.
• infix 수식은 list형태로 들어와야하며 숫자는 int타입만 허용합니다.
• 연산자는 모두 이항연산자로 취급하며  + - * / 만 허용합니다.

이제 postfix를 계산하는 코드를 작성해보겠습니다.

postfix 계산하기

이번엔 postfix로 만든 수식을 다시 계산하는 코드를 작성해보겠습니다

방식은 아래와같습니다.

• 피연산자가 들어갈 stack을 만듭니다.
• postfix를 읽어드려 피연산자 일경우 stack으로 push 합니다.
• 연산자일경우 stack의 상위 2개를 pop하여 연산자로 계산후 결과를 다시 stack에 push합니다.
• 계산이 끝난후 stack에 남은 하나를 pop하여 리턴합니다.

def calculator(postfix: list) -> list:
    stack = Stack()
    for token in postfix:
        # 피연산자일경우
        if type(token) in [int, float]:
            # 스택으로 push
            stack.push(token)
        # 연산자일경우
        else:
            # 두수를 연산자로 계산
            first_token = stack.pop()
            second_token = stack.pop()
            if token == '+':
                result = first_token + second_token
            elif token == '-':
                result = first_token - second_token
            elif token == '*':
                result = first_token * second_token
            else:
                result = first_token / second_token
            # 계산결과 스택에 push
            stack.push(result)
    
    # 스택에 남은 수를 return 
    return stack.pop()