[자료구조] 스택(Stack)의 응용 후위표기식 - python을 통한 실습 (3)

후위 표기식(postfix expression)

- 일반적으로 사용하는 수식의 표기법은 중위 표기식(infix expression)

   ㄴ 연산자(+, - *, /)가 피연산자의 사이에 들어감

- 후위 표기식(postfix expression) 

   ㄴ 연산자가 피연산자 뒤에 나옴

- 괄호가 필요없음

후위 표기식을 스택으로 구현 (입력 : 후위 표기식,  출력 : 계산 값)

1. 피연산자를 stack에 넣는다

2. 연산자가 나오면 stack에서 pop()을 두번하여 연산자를 꺼낸 후 적용

   ㄴ Tip. 먼저 꺼낸 값이 오른쪽 피연산자가 되고, 나중에 꺼낸 값이 왼쪽 피연산자가 된다!

3. 결과값을 다시 stack에 push()

4. 반복 후 stack에는 하나의 값만 남아 있어야하며 그 값이 계산 결과가 된다.

 

# 피연산자는 양의 정수로 가정, 피연산자 사이에는 하나의 공백이 있다고 가정
# 입력 : 공백으로 구분된 후위표기식
# 기대 출력 : 계산값

operator = '+-*/' # 지원하는 연산자를 하나의 string에 모아둠
stack = [] # 피연사자를 저장할 스택

def eval_op(ch):
    right = stack.pop()
    left = stack.pop()
    if (ch == '+'):
        return left + right
    elif (ch == '-'):
        return left - right
    elif (ch == '*'):
        return left * right
    elif (ch == '/'):
        return int(left / right)
    else:
        return False

def eval(expr):
    tmp = expr.split(' ') # 공백을 토크나이징 한 후 tmp에 저장
    index = 0
    while (index < len(tmp)):
        if (tmp[index][0] >= '0' and tmp[index][0] <= '9'): # 가장 앞자리가 0에서 9 일 경우 정수
            stack.append(int(tmp[index]))
        elif (tmp[index] in operator and (len(stack) >= 2)):
            stack.append(eval_op(tmp[index]))
        else:
            return ('수식이 올바르지 않습니다.')
        index += 1
    if (len(stack) == 1):
            return stack[0]
    else:        
        return ('수식이 올바르지 않습니다.')
        
print(eval(input()))