[Algorithm] 백준 - 1918번 후위표기식 (postfix)

문제소개

1918번: 후위 표기식

우리가 주로 사용하는 중위표기식을 후위표기식으로 바꾸는 문제이다.

 

문제 풀이

후위표기식 규칙과 stack을 통해 후위 표기식을 만들 수 있다.

후위표기식 규칙

1. 연산자가 아닌 경우 postfix에 추가한다.
2. 스택이 비어있는 경우 연산자를 스택에 넣어준다.
3. 스택이 비어있지 않은 경우 스택의 마지막 연산자가 "(" 이거나 우선순위가 낮을 때까지 스택의 마지막 요소를 postfix에 추가한다.
4. ")" 가 나왔을 경우 "(" 가 나올 때까지 스택의 마지막요소를 postfix에 추가한다.

import Foundation

var infix = readLine()!
var postfix = ""
var stack = [String]()

for chr in infix {
    switch chr {
    case "-", "+":
        while !stack.isEmpty && stack.last != "(" {
            postfix += stack.removeLast()
        }
        stack.append(String(chr))
    case "/", "*":
        while !stack.isEmpty && stack.last != "(" && stack.last != "+" && stack.last != "-" {
            postfix += stack.removeLast()
        }
        stack.append(String(chr))
    case "(":
        stack.append("(")
    case ")":
        while !stack.isEmpty && stack.last != "(" {
            postfix += stack.removeLast()
        }
        stack.removeLast()
    default:
        postfix += String(chr)
    }
}

while !stack.isEmpty {
    postfix += stack.removeLast()
}

print(postfix)