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.0operand : 피연산자
프로그래머는 겹치는 부분이 있는 걸 싫어하니까
이렇게 코딩할 수도 있겠죠..
(두 번 팝한다는 의미로 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
프로그래밍 언어 - 포스
스택과 후위 표기법으로 무장한 포쓰~라는 프로그래밍 언어도 있었습니다.
포스는 어셈블러에 비해 프로그램을 비교적 쉽게 작성할 수 있는 좋은 타협이며 놀랄 만큼 작은 메모리를 사용하고 놀랄만큼 빠르다. 내장된 컴파일러와 인터프리터를 가지고 동시적인 스레드를 갖는 애플리케이션 코드까지 만드는데 몇 킬로 바이트의 메모리와 어셈블러의 1/2 속도를 내는 시스템을 만든 적이 있다.
출처: https://toyfab.tistory.com/entry/What-is-Forth-포스란-무엇이냐 [토이팹]
https://www.notion.so/Forth-3d1c8ab80b0841a0b3415da9716ee1ba