프리렉 - FREELEC
http://freelec.co.kr/book/catalogue_view.asp?UID=134
이강성저
파이썬 표준 모듈 tokenize의 발생자 generate_tokens()는 라인을 읽는 함수를 인수로 받는다. generate_tokens()는 각 라인에 대해 토큰을 분석하고 5개의 튜플로 구성된 TokenInfo 객체를 넘긴다. TokenInfo 는 (type, string, start, end, line)으로 구성된다.
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)
위의 처리된 결과중 괄호 연산자를 살펴보면 일반 연산자(52, OP)로 분류되어 있다. 이 것을 좀 더 세분화 하기 위하여 다음과 같은 우리의 tokenizer() 생성자를 정의하고 테스트 해본다. '('는 LPAR, ')'는 RPAR로 구분한다. 또한 연산자의 우선 순위 정보를 입력한다.
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() 발생자를 간단히 테스트 해보자. 토큰이 잘 구해졌는지 살펴보자.
# tokenizer test
f = io.StringIO('3 + 5 + (6 + 7)')
list(tokenizer(f.readline))
이렇게 구해진 토큰을 이용하여 인픽스를 포스트픽스로 변환하는 발생자를 다음과 같이 작성한다. 알고리즘은 다음과 같다.
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()
f = io.StringIO('4 + 5')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
f = io.StringIO('3 + 4 - 5')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
f = io.StringIO('3 * (4 + 5)')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
f = io.StringIO('3+4*5/6')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
f = io.StringIO('2 - 3 + 4')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
f = io.StringIO('2 * 3 + 4')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
f = io.StringIO('1 + 2 * 3')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
f = io.StringIO('3 + 5 - (7 + 8)')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
f = io.StringIO('(300+23)*(43-21)/(84+7)')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
f = io.StringIO('• (4+8)*(6-5)/((3-2)*(2+2))')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))
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()
f = io.StringIO('3 * (4 + 5)')
post = infix2postfix( tokenizer(f.readline) )
' '.join((e.string for e in post))