신촌우왕 소개

수학자, 작곡가, 요가수행자

파이썬 계산기 프로젝트(4)

-POSTFIX NOTATION

사용자가

s = "2+3*5"와 같은 수식문자열을 (중위표기식으로) 입력하면

["2", "+", "3", "*", "5"]처럼 토큰으로 분리한 후

위 토큰리스트를

["2", "3", "5", "*", "+"]와 같은 후위표기식 리스트로 전환해야 한다.

후위표기식으로 전환하기 위해

아래와 같은 두 개의 저장소를 마련한다.

좌측은 우선순위 비교대상들(괄호, 단항연산자, 이항연산자, 함수 등)이 임시로 저장되는 곳이고

우측은 최종적으로 후위표기식이 저장될 곳이다.

전환 방법

1. 토큰리스트에서 원소를 하나씩 하나씩 꺼내기 시작한다.

2. 토큰리스트에서 꺼낸 원소가 숫자라면 우측에 넣는다.

(단, 괄호는 우측에 넣지 않는다.)

3. 토큰리스트에서 꺼낸 원소가 여는 괄호 '(' 라면 무조건 왼쪽에 넣는다.

4. 토큰리스트에서 꺼낸 원소가 닫는 괄호 ')'라면 왼쪽 저장소에서 여는 괄호 '('를 만날 때까지 꺼내어 우측에 넣는다.

(여는 괄호, 닫는 괄호를 우측에 넣는 않는다.)

5. 왼쪽 위에 여는 괄호 '('가 있을 경우, 토큰리스트에서 꺼낸 원소가 연산자 우선순위 비교대상 원소라면 왼쪽에 넣는다.

6. 토큰리스트에서 꺼낸 원소가 왼쪽 맨 위 원소보다 연산자 우선순위가 높다면 왼쪽에 넣는다.

7. 토큰리스트에서 꺼낸 원소가 왼쪽 맨 위 원소보다 연산자 우선순위가 높지 않다면 높아질 때까지 좌측에서 우측으로 옮긴 후, 토큰리스트에서 꺼낸 원소를 좌측에 넣는다.

8. 토큰리스트에서 꺼내는 작업이 끝났다면 왼쪽에 있는 것을 모두 꺼내어 우측으로 넣는다.

실전

입력 수식: "2+3*5"

토큰 리스트: ["2", "+", "3", "*", "5"]

"2"는 숫자이므로 우측에 넣는다. 좌측: [] 우측: ["2"]

"+"는 우선순위 비교대상이고, 좌측이 비어있으므로 좌측에 넣는다. 좌측: ["+"] 우측: ["2"]

"3"은 숫자이므로 우측에 넣는다. 좌측: ["+"] 우측: ["2", "3"]

"*"는 "+"보다 우선순위가 높으므로 왼쪽에 넣는다. 좌측: ["+", "*"] 우측: ["2", "3"]

"5"는 숫자이므로 우측에 넣는다. 좌측: ["+", "*"] 우측: ["2", "3", "5"]

토큰 리스트에서 꺼내는 작업이 끝났다.

이제 좌측에 있는 것을 모두 꺼내어 우측에 넣으면 된다.

(나중에 넣은 것을 먼저 꺼내어 우측에 추가하면 된다)

좌측에서 "*"를 꺼내어 우측에 추가한다. 좌측: ["+"] 우측: ["2", "3", "5", "*"]

좌측에서 "+"를 꺼내어 우측에 추가한다. 좌측: [] 우측: ["2", "3", "5", "*", "+"]

좌측에서 꺼내는 작업 또한 모두 끝났다.

우측에 들어있는 것이 후위표기식이다.

후위표기식: ["2", "3", "5", "*", "+"]