12. 스택과 후위 표기법, 파이썬

우리가 흔히 사용하는 방식은 중위 표기법(infix notation)인데, 
연산 기호를 중간에 넣습니다. 
ex) 1 + 2

 

연산기호가 앞에 오는 전위 표기법(prefix notation)도 있고..
ex) + 1 2 

 

연산기호가 뒤에 오는 후위 표기법(postfix notation)도 있습니다..
ex) 1 2 +

 

전위 표기법은 폴란드식 표기법(PN, Polish Notation),
후위 표기법은 역 폴란드식 표기법(RPN, Reverse-Polish Notation)이라고도 하는데요.
이런 표기법들은 괄호를 쓸 필요가 없고,
또 스택으로 구현할 수 있습니다. 

 

자세한 건 글 마지막 링크들을 참고하시고요. 
간단하게 느낌만 살펴보도록 하겠습니다.

후위표기법 :
5 6 + 7 * 2 /

중위표기법 :
((5 + 6) * 7) / 2

5 3 2 * +
5 + 3 * 2

 

간단한 구현을 위해 조건을 설정하겠습니다. 

한 자리의 정수와 사칙 연산 기호로만 구성된 후위 표기식을 계산하는 함수를 작성하시오. (띄어 쓰지 않습니다.)
예) 56+7*2/

 

[힌트]

하나씩 스택에 저장하다가 연산 기호를 만나면 두 번 팝, 한 번 푸쉬하면 됩니다.

팝할 때 순서에 주의하시고요. 

 

def postfix(expression):
    stack = []
    for element in expression:
        if element == '+':
            op2 = stack.pop()
            op1 = stack.pop()
            stack.append(op1 + op2)
        elif element == '-':
            op2 = stack.pop()
            op1 = stack.pop()
            stack.append(op1 - op2)
        elif element == '*':
            op2 = stack.pop()
            op1 = stack.pop()
            stack.append(op1 * op2)
        elif element == '/':
            op2 = stack.pop()
            op1 = stack.pop()
            stack.append(op1 / op2)
        else:
            stack.append(int(element))
    return stack.pop()


print(postfix('82/3-3*'))  # 3.0

operand : 피연산자

 

프로그래머는 겹치는 부분이 있는 걸 싫어하니까
이렇게 코딩할 수도 있겠죠.. 

(두 번 팝한다는 의미로 pop_pop이라고 함수명을 지었습니다.)

def postfix(expression):
    stack = []
    for element in expression:
        if element == '+':
            op2, op1 = pop_pop(stack)
            stack.append(op1 + op2)
        elif element == '-':
            op2, op1 = pop_pop(stack)
            stack.append(op1 - op2)
        elif element == '*':
            op2, op1 = pop_pop(stack)
            stack.append(op1 * op2)
        elif element == '/':
            op2, op1 = pop_pop(stack)
            stack.append(op1 / op2)
        else:
            stack.append(int(element))
    return stack.pop()


def pop_pop(stack):
    op2 = stack.pop()
    op1 = stack.pop()
    return op2, op1


print(postfix('82/3-3*'))  # 3.0

 

 

실제로 사용할 정도가 되려면, 
숫자의 제한이 없어져야 하고,
띄어쓰기로 항목들을 나눌 수 있어야 합니다. 
실수형도 쓸 건지 고려해야 겠구요.
아무래도 실수형을 못 쓴다면 계산기라고 하긴 어렵겠죠?

 

더 공부하고 싶으신 분들은 도전해 보시길..

 

위키들...

폴란드 표기법
https://ko.wikipedia.org/wiki/%ED%8F%B4%EB%9E%80%EB%93%9C_%ED%91%9C%EA%B8%B0%EB%B2%95

 

수식 트리를 이용한 혼합 계산
https://namu.wiki/w/%ED%98%BC%ED%95%A9%20%EA%B3%84%EC%82%B0#s-3.2

 

프로그래밍 언어 - 포스

스택과 후위 표기법으로 무장한 포쓰~라는 프로그래밍 언어도 있었습니다. 

https://forth-standard.org/

https://namu.wiki/w/Forth

https://ko.wikipedia.org/wiki/%ED%8F%AC%EC%8A%A4_(%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D_%EC%96%B8%EC%96%B4)

포스는 어셈블러에 비해 프로그램을 비교적 쉽게 작성할 수 있는 좋은 타협이며 놀랄 만큼 작은 메모리를 사용하고 놀랄만큼 빠르다. 내장된 컴파일러와 인터프리터를 가지고 동시적인 스레드를 갖는 애플리케이션 코드까지 만드는데 몇 킬로 바이트의 메모리와 어셈블러의 1/2 속도를 내는 시스템을 만든 적이 있다. 

출처: https://toyfab.tistory.com/entry/What-is-Forth-포스란-무엇이냐 [토이팹]

https://www.notion.so/Forth-3d1c8ab80b0841a0b3415da9716ee1ba

https://www.notion.so/4-2-cb84c57dd7d642fcb64d6a08d5768539