[Swift 알고리즘] 백준 BOJ - 1918 후위연산자

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 1918 후위연산자" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

1918번: 후위 표기식

 

---

풀이

오늘은 스택 문제를 풀었습니다.

 

1. 연산자 우선순위 정하기

연산자의 우선순위를 저장한 딕셔너리로 선언해 줍니다.

+, -는 1을 value로 설정하고 *, /는 2를 value로 설정합니다.

(, )는 딕셔너리가 아닌 조건문을 이용해 처리했습니다.

 

2. Stack 조건

Stack에 push, pop 하는 조건을 생각해 봅시다.

이 문제는 괄호가 있기 때문에 단순한 사칙 연산 우선순위로만 해결할 수 없습니다.

 

먼저 여는 괄호는 연산이 이루어지지 않습니다. 따라서 stack에 무조건 push 합니다.

닫는 괄호가 나오면 하나의 연산이 생성된 것이므로 괄호 안의 연산자를 모두 밖으로 뺍니다.

즉, stack에서 여는 괄호가 나올 때까지 pop 합니다.

 

사칙연산은 stack의 top이 자신의 우선순위보다 큰 연산자라면 pop 하고 자신을 push 합니다.

만약 *가 top이고 +가 들어온다면 *를 pop 하고 +를 push 합니다.

만약 +가 top이고 *가 들어온다면 +만 push 합니다.

 

3. 결과 출력하기

stack에 남은 연산자가 있다면 result 배열에 역순으로 추가합니다.

역순으로 추가하는 이유는 stack이기 때문입니다..!

stack의 top부터 result 배열에 하나씩 넣는다는 개념인데 반복문을 이용해 하나씩 pop을 하면 O(n)이 걸리지만 reversed()를 이용하면 O(1)로 모든 잔여 원소를 append할 수 있습니다.

 

---

전체 코드

let operations: [String: Int] = ["+": 1, "-": 1, "*": 2, "/": 2]
var stack: [String] = []
for char in input {
    if char == "(" {
        stack.append(char)
    } else if char == ")" {
        while let top = stack.last, top != "(" {
            result.append(top)
            stack.removeLast()
        }
        stack.popLast()
    } else {
        if let priority = operations[char] { //연산자
            while let top = stack.last, top != "(" {
                guard let topPriority = operations[top], topPriority >= priority else { break }
                result.append(stack.popLast()!)
            }
            stack.append(char)
        } else { //알파벳
            result.append(char)
        }
    }
}

if !stack.isEmpty {
    result.append(contentsOf: stack.reversed())
}
result = result.filter { $0 != "(" && $0 != ")" }

print(result.joined())

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.