[후위표기식] 스택 알고리즘 문제 예시로 알아보기

중위표기식, 후위표기식은 전공강의를 들으면서 개념을 알고 있었는데 이걸 막상 문제로 풀려고 하니 정확한 프로세스를 표현하지 못했다.

자료구조 "스택" 을 활용하여 중위표기식을 후위표기식으로 표현하는 프로그램을 작성하면서 다시 학습하고자 한다.

1. 중위표기식 과 후위표기식 이란

중위표기식은 우리가 흔히 사용하는 표기 방식으로 연산자 가 피연산자 사이에 존재한다. 중간에 있어 "중위" 표기식!
후위표기식은 연산자 가 피연산자 의 뒤에 존재한다. 뒤 후 자로 "후위" 표기식!

1-1) 중위표기식 예시

3+5*2/(7-2)

가 있을때 연산자 우선순위를 고려하여 문제를 풀어나간다.

3+5*2/(7-2)
1) 3+5*2/5
2) 3+10/5
3) 3+2
4) 5

1-2) 후위표기식 예시

352*72-/+

후위표기식은 연산자가 피연산자의 뒤에 있으므로 연산자가 나오면 연산자 앞의 두개의 피연산자와 해당 연산자를 계산해 준다.

352*72-/+
1) 52* 계산 : 5*2 => 3(10)72-/+
2) 72- 계산 : 7-2 => 3(10)5/+
3) (10)5/ 계산 : 10/5 => 32+
4) 32+ 계산 : 3+2 => 5

계산 결과로 알수 있듯 각 예시로 들은 식은 동일한 수식이다.

2. 연산자 우선순위

a) 덧셈, 뺄셈

덧셈과 뺄셈은 연산자 우선순위에서 가장 하위에 위치한다.

b) 곱셈, 나눗셈

곱셈과 나눗셈은 연산자 우선순위에서 덧셈과 뺄셈보다 상위에 위치한다.

c) 괄호

괄호의 종류로는 소괄호, 중괄호, 대괄호가 있는데 일반적으로 괄호는 괄호로 둘러싸인 바깥의 연산자들 보다 상위의 우선순위를 가진다. 또한 괄호의 세 종류 내에서는 소괄호 > 중괄호 > 대괄호 순으로 상위의 우선순위를 가진다.

3. 중위표기식 -> 후위표기식 : 스택 구조 활용

중위표기식을 후위표기식으로 변환하라는 문제는 알고리즘 문제에서 쉽게 볼수 있다. 특히 자료구조 "스택" 을 활용한 문제에서.
자료구조 "스택"을 활용해 변환하는 과정을 말하기 전, 연산자 우선순위에 대한 정확한 이해가 필요하다.

 

스택?
Last In First Out 구조로 나중에 들어간 값이 가장 먼저 반환되는 구조이다. 파이썬에서는 list의 스택 자료 형태에서 내장함수로 append() 와 pop()이 활용된다.

 

먼저 위로 예시를 들었던 중위표기식 3+5*2/(7-2) 을 후위표기식으로 변환해보자.
스택구조를 활용해 후위표기식으로 변환할때 다음과 같은 규칙이 있다.

1. 피연산자가 나올 경우 후위표기식으로 바로 작성한다.
2. 연산자가 나올 경우 연산자 우선순위에 따라 stack에 쌓거나, 후위표기식으로 작성한다.

간단한 규칙이지만 다양하게 존재하는 연산자 우선순위에 따라 따져야할 조건들이 많다.

result = ""  # 변환 완료된 후위표기식
stack = [] # 스택 자료구조
target_list = "3+5*2/(7-2)"  # 후위로 변환하고자 하는 중위표기식

for target in target_list:  # 문자열을 for loop으로 실행 시 문자 한개씩 확인할 수 있다.
    if target.isdecimal():  # 파이썬 내장함수 isdecimal()로 해당 문자열이 숫자로 변환 가능한지 확인 할 수 있다. (boolean)
        result += target
    else:
        # 괄호가 나온 경우 최우선 순위로 stack 에 쌓기
        if row == "(":  
            stack.append(row)
        # 곱셈, 나눗셈이 나온경우 동일한 우선순위를 가진 연산자가 확인될때까지 stack에 쌓여있는 피연산자 꺼내기
        elif row in ["*", "/"]:  
            # 이때, stack에 더이상 연산자가 없는 경우 꺼내는걸 중단한다.
            while stack and (stack[-1] in ["*", "/"]):  
                # stack 에서 꺼낸 연산자는 후위표기식에 작성된다.
                res += stack.pop()  
            # 이후 확인 대상이었던 연산자는 stack에 쌓인다.
            stack.append(row)  
        # 덧셈,뺄셈은 최하위 우선순위이나 소괄호 내의 것은 소괄호 바깥의 연산자들보다 상위순위를 갖는다.
        elif row in ["+", "-"]:  
            # stack에 쌓인 연산자가 여는 소괄호가 아닌경우때 까지 연산자를 꺼낸다.
            while stack and stack[-1] != "(":  
                # stack 에서 꺼낸 연산자는 후위표기식에 작성된다.
                res += stack.pop()  
            # 이후 확인 대상이었던 연산자는 stack에 쌓인다.
            stack.append(row)  
        # 닫는 소괄호가 나온 경우 stack에는 여는 소괄호가 있을 것이다.
        elif row == ")":  
            # 여는 소괄호가 나올때까지 모든 연산자를 우선순위에 맞춰 후위표기식으로 작성한다.
            while stack and stack[-1] != "(":  
                res += stack.pop()
            # 괄호는 후위표기식에 작성되지 않으므로 소괄호는 없애준다.
            stack.pop() 
    while stack:
        res += stack.pop()

각 조건문에 대해 좀더 자세히 살펴보면 다음과 같다.

1. 괄호내의 것은 우선순위로 변환한다. 또한 후위표기식에서 괄호는 표현되지 않으므로 변환에 사용하지 않는다.
2. 덧셈, 뺄셈일 경우 해당 연산자보다 후순위의 연산자가 없으므로 stack에 쌓여있는 모든 연산자들을 처리해 주어야 한다.
   (본인과 동등한 우선순위의 연산자, 상위 순위 연산자 처리해야 하기 때문)
3. 위 2번과 동일한 맥락으로 곱셈, 나눗셈일 경우 본인과 동등한 우선순위 연산자까지는 모두 처리해 주어야 한다.
   • 이 규칙으로 인해 3+5_2 는 352_ 가 되고 +는 그대로 stack에 남아있게 되었다. (이후 처리됨)

스택구조 활용에 이렇게 알찬 예제는 없는듯 하다. 그래서 알고리즘 스택 문제 단골 손님인가 싶다.!