파이썬3 바이블 - 제18장 연습문제

프리렉 - FREELEC

http://freelec.co.kr/book/catalogue_view.asp?UID=134

이강성저

1.

파이썬 표준 모듈 tokenize의 발생자 generate_tokens()는 라인을 읽는 함수를 인수로 받는다. generate_tokens()는 각 라인에 대해 토큰을 분석하고 5개의 튜플로 구성된 TokenInfo 객체를 넘긴다. TokenInfo 는 (type, string, start, end, line)으로 구성된다.

In [1]:
import tokenize as tk
import io

f = io.StringIO('3 + 5 + (6 + 7)')

for ele in tk.generate_tokens(f.readline):
    print(ele, ele.type, ele.string)
TokenInfo(type=2 (NUMBER), string='3', start=(1, 0), end=(1, 1), line='3 + 5 + (6 + 7)') 2 3
TokenInfo(type=52 (OP), string='+', start=(1, 2), end=(1, 3), line='3 + 5 + (6 + 7)') 52 +
TokenInfo(type=2 (NUMBER), string='5', start=(1, 4), end=(1, 5), line='3 + 5 + (6 + 7)') 2 5
TokenInfo(type=52 (OP), string='+', start=(1, 6), end=(1, 7), line='3 + 5 + (6 + 7)') 52 +
TokenInfo(type=52 (OP), string='(', start=(1, 8), end=(1, 9), line='3 + 5 + (6 + 7)') 52 (
TokenInfo(type=2 (NUMBER), string='6', start=(1, 9), end=(1, 10), line='3 + 5 + (6 + 7)') 2 6
TokenInfo(type=52 (OP), string='+', start=(1, 11), end=(1, 12), line='3 + 5 + (6 + 7)') 52 +
TokenInfo(type=2 (NUMBER), string='7', start=(1, 13), end=(1, 14), line='3 + 5 + (6 + 7)') 2 7
TokenInfo(type=52 (OP), string=')', start=(1, 14), end=(1, 15), line='3 + 5 + (6 + 7)') 52 )
TokenInfo(type=0 (ENDMARKER), string='', start=(2, 0), end=(2, 0), line='') 0 

위의 처리된 결과중 괄호 연산자를 살펴보면 일반 연산자(52, OP)로 분류되어 있다. 이 것을 좀 더 세분화 하기 위하여 다음과 같은 우리의 tokenizer() 생성자를 정의하고 테스트 해본다. '('는 LPAR, ')'는 RPAR로 구분한다. 또한 연산자의 우선 순위 정보를 입력한다.

In [2]:
from collections import namedtuple

Token = namedtuple('Token', ('type', 'string', 'precedence'))

def tokenizer(f):
    for ele in tk.generate_tokens(f):
        type = ele.type
        string = ele.string
        if (type, string) == (tk.OP, '('):
            type = tk.LPAR
            prec = 10
        elif (type, string) == (tk.OP, ')'):
            type = tk.RPAR
            prec = 10
        elif string in ('*', '/'):
            prec = 2
        elif string in ('+', '-'):
            prec = 3
        else:
            prec = 0
        yield Token(type, string, prec)

tokenizer() 발생자를 간단히 테스트 해보자. 토큰이 잘 구해졌는지 살펴보자.

In [3]:
# tokenizer test

f = io.StringIO('3 + 5 + (6 + 7)')
list(tokenizer(f.readline))
Out[3]:
[Token(type=2, string='3', precedence=0),
 Token(type=52, string='+', precedence=3),
 Token(type=2, string='5', precedence=0),
 Token(type=52, string='+', precedence=3),
 Token(type=7, string='(', precedence=10),
 Token(type=2, string='6', precedence=0),
 Token(type=52, string='+', precedence=3),
 Token(type=2, string='7', precedence=0),
 Token(type=8, string=')', precedence=10),
 Token(type=0, string='', precedence=0)]

이렇게 구해진 토큰을 이용하여 인픽스를 포스트픽스로 변환하는 발생자를 다음과 같이 작성한다. 알고리즘은 다음과 같다.

  1. stack을 이용한다
  2. 피연산자(operand)는 그냥 출력한다
  3. 연산자(operator)는
  4. 스택의 연산자가 더 낮은 우선순위일 때까지 연산자를 꺼내어 출력한다.
  5. 그리고 나서 현재의 연산자를 스택에 넣는다
  6. )를 만나면 (를 만날 때까지 출력한다.
  7. (는 스택에서 가장 낮은 우선 순위를 갖는다.
  8. 입력의 마지막을 만나면 스택에서 모든 것을 꺼내온다.
In [4]:
def infix2postfix(tokens):
    stack = []
    for tkn in tokens:
        if tkn.type in (tk.NUMBER, tk.NAME):
            yield tkn
        elif tkn.type == tk.OP:
            while stack and stack[-1].precedence <= tkn.precedence:
                yield stack.pop()
            stack.append(tkn)
        elif tkn.type == tk.LPAR:
            stack.append(tkn)
        elif tkn.type == tk.RPAR:
            while stack[-1].type != tk.LPAR:
                yield stack.pop()
            stack.pop()
        elif tkn.type in (tk.NL, tk.ENDMARKER):
            while stack:
                yield stack.pop()
In [5]:
f = io.StringIO('4 + 5')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
Out[5]:
'4 5 +'
In [6]:
f = io.StringIO('3 + 4 - 5')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
Out[6]:
'3 4 + 5 -'
In [7]:
f = io.StringIO('3 * (4 + 5)')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
Out[7]:
'3 4 5 + *'
In [8]:
f = io.StringIO('3+4*5/6')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
Out[8]:
'3 4 5 * 6 / +'
In [9]:
f = io.StringIO('2 - 3 + 4')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
Out[9]:
'2 3 - 4 +'
In [10]:
f = io.StringIO('2 * 3 + 4')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
Out[10]:
'2 3 * 4 +'
In [11]:
f = io.StringIO('1 + 2 * 3')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
Out[11]:
'1 2 3 * +'
In [12]:
f = io.StringIO('3 + 5 - (7 + 8)')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
Out[12]:
'3 5 + 7 8 + -'
In [13]:
f = io.StringIO('(300+23)*(43-21)/(84+7)')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
Out[13]:
'300 23 + 43 21 - * 84 7 + /'
In [14]:
f = io.StringIO('• (4+8)*(6-5)/((3-2)*(2+2))')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
Out[14]:
'4 8 + 6 5 - * 3 2 - 2 2 + * /'

All together

In [15]:
import tokenize as tk
import io
from collections import namedtuple

from collections import namedtuple

Token = namedtuple('Token', ('type', 'string', 'precedence'))

def tokenizer(f):
    for ele in tk.generate_tokens(f):
        type = ele.type
        string = ele.string
        if (type, string) == (tk.OP, '('):
            type = tk.LPAR
            prec = 10
        elif (type, string) == (tk.OP, ')'):
            type = tk.RPAR
            prec = 10
        elif string in ('*', '/'):
            prec = 2
        elif string in ('+', '-'):
            prec = 3
        else:
            prec = 0
        yield Token(type, string, prec)
        
def infix2postfix(tokens):
    stack = []
    for tkn in tokens:
        if tkn.type in (tk.NUMBER, tk.NAME):
            yield tkn
        elif tkn.type == tk.OP:
            while stack and stack[-1].precedence <= tkn.precedence:
                yield stack.pop()
            stack.append(tkn)
        elif tkn.type == tk.LPAR:
            stack.append(tkn)
        elif tkn.type == tk.RPAR:
            while stack[-1].type != tk.LPAR:
                yield stack.pop()
            stack.pop()
        elif tkn.type in (tk.NL, tk.ENDMARKER):
            while stack:
                yield stack.pop()
In [16]:
f = io.StringIO('3 * (4 + 5)')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
Out[16]:
'3 4 5 + *'