[파이썬/실습] infix 수식을 postfix로 변환하기

* class로 Stack을 정의한 후 코드를 작성했다.
* 수식에는 이항연산자만 사용한다고 가정한다.

어설프지만 infix와 postfix 그리고 스택은 아래 링크에 정리해두었다.

순차적 자료구조 & 스택 (stack)

입력
1 + ( 2 + 3 ) / 4

출력
1 2 3 + 4 / +

Stack 클래스 정의

• push(value): 스택에 값을 넣음
• pop(): 스택의 가장 위에 있는 값을 삭제 후 리턴, 스택이 비어있으면 "Stack is empty"를 출력
• top(): 스택의 가장 위에 있는 값을 리턴, pop()과 마찬가지로 스택이 비어있으면 "Stack is empty"를 출력
• __len__(): 스택의 길이 출력
• isEmpty(): 스택이 비어있는지 아닌지 판단

class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            print("Stack is empty")

    def top(self):
        try:
            return self.items[-1]
        except IndexError:
            print("Stack is empty")

    def __len__(self):
        return len(self.items)

    def isEmpty(self):
        return self.__len__() == 0

Postfix 수식 변환 코드 (infix_to_postfix 함수)

1. 공간 만들기

def infix_to_postfix(infix):
    opstack = Stack()
    outstack = []

opstack = 연산자가 오고나가는 스택
outstack = postfix 변환 결과가 저장되는 리스트

2. 문자열 형태로 입력받은 수식을 리스트로 변환하기

	# 수식 토크나이징
    token_list = infix.split()

infix에 문자열로 입력된 수식을 공백을 기준으로 나눠 리스트에 저장한다.

예)
infix = '2 * 3'
token_list = ['2', '*', '3']

3. 연산자의 우선순위 설정

    prec = {}
    prec['('] = 0
    prec['+'] = 1
    prec['-'] = 1
    prec['*'] = 2
    prec['/'] = 2
    prec['^'] = 3

prec 이라는 이름의 딕셔너리를 생성하여 연산자별로 우선순위를 지정한다.
숫자가 높을수록 우선순위가 높은 것이다.

4. 반복문 작성

	for token in token_list:

token_list의 token을 하나씩 살펴보며 postfix 변환 로직을 수행한다.

5. 경우 나누기
5-1. 왼쪽 괄호일 경우

        if token == '(':
            opstack.push(token)

왼쪽 괄호는 우선순위가 가장 낮다. 따라서 바로 스택에 들어가 대기하도록 push해준다.

5-2. 오른쪽 괄호일 경우

        elif token == ')':
            while opstack.top() != '(':
                popped = opstack.pop()
                outstack.append(popped)
            opstack.pop()

opstack의 제일 위에 있는 값이 왼쪽 괄호일 떄까지 계속 pop하면서 pop할 때마다 리턴된 원소를 outstack에 집어넣는다.
왼쪽 괄호 차례에는 반복문이 정지되고 opstack에 아직 왼쪽 괄호가 남아있는 상태이므로 pop을 한 번 더 수행한다.

5-3. 연산자일 경우
가장 까다로웠던 부분이고 여기서 자꾸 생각했던대로 안 돼서 어려웠다.

        elif token in '+-/*^':
            # 스택이 비어있다면 바로 push
            if opstack.isEmpty():
                opstack.push(token)

            # 그렇지 않다면 우선순위 비교하기
            else:
                if prec[token] <= prec[opstack.top()]:
                    while not opstack.isEmpty() and prec[token] <= prec[opstack.top()]:
                        popped = opstack.pop()
                        outstack.append(popped)
                    opstack.push(token)

                else:
                    opstack.push(token)

1) 스택이 텅 빈 상태일 때에는 바로 push한다.

2) 그렇지 않고 스택에 어떤 연산자가 들어있는 상태라면 우선순위를 비교한다.

✔️경우 a. 스택의 가장 위에 있는 연산자가 token보다 우선순위가 높거나 같다.
- 스택의 가장 위에 있는 연산자, 즉 opstack.top()이 token보다 우선순위가 낮아질 때까지 계속 pop하고, pop한 원소를 outstack에 append한다. 그 후 token을 opstack에 push한다.
- 스택이 비어있을 때에는 pop하지 않도록 조건을 넣어준다.

✔️경우 b. 스택의 가장 위에 있는 연산자가 token보다 우선순위가 낮다.
- 바로 opstack에 push한다.

5-4. 피연산자일 경우

        else:  # operand일 때
            outstack.append(token)

피연산자는 바로 outstack에 들어간다.

6. Stack에 남아있는 연산자 처리하기

    # opstack 에 남은 모든 연산자를 pop 후 outstack에 append
    while not opstack.isEmpty():
        popped = opstack.pop()
        outstack.append(popped)

위 과정을 다 수행하고 난 후에도 스택에는 여전히 연산자가 남아있을 수 있다. 따라서 그 연산자를 차례대로 pop하여 outstack에 넣는 코드를 작성해주어야 한다.
스택이 비어있을 때 pop을 수행하면 에러가 발생하므로 스택이 비어있지 않은 상태에만 수행하도록 while 조건문을 작성한다.

6. 리스트를 문자열로 변환하기

    return " ".join(outstack)

.join(list)를 이용하면 리스트를 문자열로 만들 수 있다.
" ".join(outstack)은 문자 사이사이에 공백을 넣어준다.
만약 ":".join(outstack)으로 작성한다면 문자 사이사이에 콜론이 들어가게 된다.

최종 코드

'''
Infix to postfix
'''


class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            print("Stack is empty")

    def top(self):
        try:
            return self.items[-1]
        except IndexError:
            print("Stack is empty")

    def __len__(self):
        return len(self.items)

    def isEmpty(self):
        return self.__len__() == 0

def infix_to_postfix(infix):
	opstack = Stack()
	outstack = []
		
	# 수식 토크나이징
	token_list = infix.split()
		
	# 연산자의 우선순위 설정
	prec = {}
	prec['('] = 0
	prec['+'] = 1
	prec['-'] = 1
	prec['*'] = 2
	prec['/'] = 2
	prec['^'] = 3
	
	for token in token_list:
		if token == '(':
			opstack.push(token)
		
		elif token == ')':
			while opstack.top() != '(':
				popped = opstack.pop()
				outstack.append(popped)
			opstack.pop()
		
		elif token in '+-/*^':
			# 스택이 비어있다면 바로 push
			if opstack.isEmpty():
				opstack.push(token)
				
			# 그렇지 않다면 우선순위 비교하기
			else:
				if prec[token] <= prec[opstack.top()]:
					while not opstack.isEmpty() and prec[token] <= prec[opstack.top()]:
						popped = opstack.pop()
						outstack.append(popped)
					opstack.push(token)
				
				else:
					opstack.push(token)
						
		else: # operand일 때
			outstack.append(token)

    # opstack 에 남은 모든 연산자를 pop 후 outstack에 append
	while not opstack.isEmpty():
		popped = opstack.pop()
		outstack.append(popped)
		# ... ... ...
	return " ".join(outstack)

	
infix_expr = input()
postfix_expr = infix_to_postfix(infix_expr)
print(postfix_expr)