[자료구조 활용][스택, 큐, 해쉬, 힙] - 후위 표기식 만들기(스택)

s = input()
stack = []
res = ""

for i in s:
    if i.isdecimal():
        res+= i
    else: #숫자가 아닌 경우
        if i == "(":
            stack.append(i)
        elif i =="*" or i =="/":
            while stack and (stack[-1] == "*" or stack[-1]=="/"):
                res += stack.pop()
            stack.append(i)
        elif i == "+" or i == "-":
            while stack and stack[-1] != "(":
                res += stack.pop()
            stack.append(i)
        elif i ==")":
            while stack and stack[-1] != "(":
                res += stack.pop()
            stack.pop() #여는 괄호를 빼주어야 다음 작업에 영향 X
while stack:
    res += stack.pop()

print(res)

1

1. 현재 stack내에 값이 없기에 +는 바로 append되게 된다 (i == "+"이지만 while문의 조건인 stack이 있어야 하는 것을 만족하지 못해 바로 append 됐다.)

 

2. 해당 스택에 * 연산자가 제일 우선순위가 높기 때문에 +를 출력하지 않고 append처리 해준 것이다.

 

3. "/"의 경우엔 "*"와 우선 순위가 같아 해당 문자를 빼내 출력해준뒤 자기 자신 "/"는 append 해준다.

4. "(" 는 조건 없이 바로 stack에 넣어준다.

5. 숫자 역시 바로 출력해준다.

6. "-"나 "+"의 경우엔 "*" "/" "+" "-" 모두를 출력하지만 바로 앞에 "(" 이 오는 경우라 stack에 append 해준다.

7. ")" 닫는 괄호를 마주했을 땐 여는 괄호 전까지 모든 연산자를 빼준다. 이때 (는 출력되면 안 되기 때문에 따로 stack을 확인하는 while문이 끝났을 때 꺼내준다.

8. 마지막 작업으로는 stack에 연산자가 남아있다면 이를 비워주기 위한 작업을 진행해주면 된다.

 

중위 표현식을 후위 표현식으로 만들어 사용하는 것은 컴퓨터 입장에서 더 쉽게 계산을 돕는다고 한다.