후위표기식 변환

안녕하세요 :)
오늘은 사람들이 일반적으로 사용하는 중위표기식(infix)을 후위표기식(postfix)으로 변환하는 방법에 대해 알아보겠습니다.

후위표기식?

먼저 중위표기식과 후위표기식에 대해 알아볼까요?
사람들이 계산할 때 사용하는 수식을 중위표기식이라고 하는데,
3*5와 같이 피연산자 사이에 연산자를 두는 방법이에요.
이와달리 연산자를 피연산자 뒤에 놓는 방법을 후위표기식이라고 합니다.
위의 중위표기식을 후위표기식 35* 로 바꿀 수 있어요.
후위표기식을 사용하면 연산자 우선순위에 따라 사람이 머리 속에서 왔다갔다 하는 계산 대신 왼쪽부터 순서대로 계산할 수 있어서 컴퓨터에게 시킬 수식으로 적합하다고 합니다.

연산자는 기본적으로 사용하는 사칙연산(+, -, /, *)을 포함해 괄호, %, == 등 말 그대로 연산에 필요한 기호들을 의미합니다.
피연산자는 연산자 이외의 연산이 되는 대상을 의미합니다.

후위표기식 변환 방법

이제 구체적으로 후위표기식으로 변환시키는 방법을 알아보겠습니다.
원론적인 방법은 중위표기식을 연산자 순서에 따라 괄호로 묶고, 괄호안의 연산자를 괄호 뒤에 붙여주면 됩니다.
예를 들어, 중위표기식 A+B*C-D/E 를 괄호로 묶어보면, 다음과 같이 할 수 있습니다.

출처: https://www.acmicpc.net/problem/1918

그럼 머리로는 알겠는데 이렇게 프로그래밍 하려면 어떻게 해아할까요? 방법은 생각보다 간단합니다.
먼저 연산자를 담을 스택이 하나 필요한데 스택을 활용해서 다음과 같은 과정을 거쳐 변환할 수 있습니다.
1. 피연산자는 그대로 출력합니다.
2. 연산자는 스택이 비어있으면 자신을 바로 추가합니다.
3. stack의 top이 자신보다 우선순위가 낮은 연산자를 만날 때까지 pop 하고 자신을 담습니다.
4. 단, 여는 괄호는 닫는 괄호가 아니면 pop하지 않습니다.
4. 닫는 괄호가 나오면 여는 괄호가 나올 때까지 꺼내서 출력합니다.
5. 마지막에 도착하면 스택에서 차례로 꺼내서 출력합니다.

A+B/C*D*(E+F)

A는 피연산자이므로 그대로 출력합니다.
연산자 스택

출력: A

A+B/C*D*(E+F)

연산자 스택이 비어있으므로 +를 바로 추가합니다.
연산자스택

+

출력: A

A+B/C*D*(E+F)

B는 피연산자이므로 그대로 출력합니다.
연산자 스택

+

출력: AB

A+B/C*D*(E+F)

/는 +보다 연산자 우선순위가 높으므로 스택에 담습니다.
연산자 스택

+

/

출력: AB

A+B/C*D*(E+F)

C는 피연산자이므로 출력합니다.
연산자 스택

+

/

출력: ABC

A+B/C*D*(E+F)

*는 /와 연산자 우선순위가 같으므로 / 를 꺼내서 출력합니다.
그리고 *는 +보다 연산자 우선순위가 높으므로 자신을 스택에 담습니다.
연산자 스택

+

/

*

출력: ABC/

A+B/C*D*(E+F)

D는 피연산자이므로 출력합니다.
연산자 스택

+

*

출력: ABC/D

A+B/C*D*(E+F)

*는 *와 연산자 우선순위가 같으므로 *를 출력합니다.
*는 +보다 연산자 우선순위가 높으므로 *을 스택에 담습니다.
연산자 스택

+

*

*

출력: ABC/D*

A+B/C*D*(E+F)

( 는 *보다 연산자 우선순위가 높으므로 스택에 담습니다.
연산자 스택

+

*

(

출력: ABC/D*

A+B/C*D*(E+F)

E는 피연산자이므로 출력합니다.
연산자 스택

+

*

(

출력: ABC/D*E

A+B/C*D*(E+F)

top이 ( 이므로 +를 스택에 담아줍니다.
연산자 스택

+

*

(

+

출력: ABC/D*E

A+B/C*D*(E+F)

F는 피연산자이므로 출력합니다.
연산자 스택

+

*

(

+

출력: ABC/D*EF

A+B/C*D*(E+F)

) 이므로 (가 나올 때까지 pop해서 출력합니다.
연산자 스택

+

*

(

+

출력: ABC/D*EF+

마지막에 도착했으므로 스택에서 모두 꺼내 출력합니다.
출력: ABC/D*EF+*+

구현

이를 swift 코드로 구현하면 다음과 같습니다.
(바로 출력 대신 result 변수에 담아주는 것으로 처리했습니다.)

var str = readLine()!
var result = ""
var oper = ""

for char in str {
    if char == "(" {
        oper.append("(")
    } else if char == ")" {
        while let opr = oper.popLast() {
            guard opr != "(" else { break }
            result.append(opr)
        }
    } else if char == "*" || char == "/" {
        guard !oper.isEmpty else { oper.append(char); continue }
        
        while let opr = oper.last, (opr == "*" || opr == "/") {
            result.append(oper.popLast()!)
        }
        oper.append(char)
    } else if char == "+" || char == "-" {
        guard !oper.isEmpty else { oper.append(char); continue }
        while let opr = oper.popLast() {
            guard opr != "(" else { oper.append(opr); break }
            result.append(opr)
        }
        oper.append(char)
    } else {
        result.append(char)
    }
}

print(result + oper.reversed())

이해가 되셨다면 아래 문제를 풀어보면서 연습해보세요 :)
www.acmicpc.net/problem/1918

감사합니다.