[백준] 1918 후위 표기식 - Swift

인생 첫 골드 문제,,,

이틀 걸려 고민하면서 풀었다. 내 코드가 다른 분들에게 참고가 되기를,,,

 

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

1918번: 후위 표기식

문제 풀면서 고려했던 점은
연산자로는 +, -, *, /, (, )와 알파벳들이 입력으로 주어진다.

1. ( 열린 괄호가 들어왔을 때에는 일단 stack에 추가

2. ) 닫힌 괄호가 들어왔을 경우네는 ( 열린 괄호를 만나기 전까지 stack의 값을 빼면서 result 배열에 삽입한다

2-a while문에 ( 열린 괄호가 아닐 때까지 돌아가기 때문에, while문을 빠져나오면 한번 더 stack의 값을 빼준다

3. *나 /일 경우 스택이 비어 있지 않은지 먼저 확인 후, 똑같이 * 나 /일 경우 stack에서 값을 빼준다. 왜냐하면 *나 /가 연속으로 올 경우, 연산자 우선순위로인해 무조건 왼쪽에서부터 차례대로 계산이 되어야 하기 때문에, 순서를 신경 써 주어야 한다.

나는 3번 고려를 제대로 생각 못해 줘서 이틀 동안 문제를 못 풀었다... ㅠ

4. +나 -일 경우 우선순위가 가장 높으며, stack의 마지막 값이 연산자일 때 계속해서 stack에서의 값을 빼준다. 다르게 말하자면 열린 괄호를 만나기 전까지 stack의 값을 빼준다고 말할 수 있다.

5. for문은 모두 돌았지만, stack에 값이 남아 있을 수 있다. 그런 경우는 while문을 통해 stack에 들어 있는 값들을 모두 빼주는 과정이 필요하다.

 

< 3번 조건의 예시 >

G*(A-B*(C/D+E)/F)
이러한 예제가 있다고 가정했을 때

괄호는 빨간색, stack에 빠져나온 연산자는 파란색으로 표기해 두었고,

현재 위 예제에서 E 다음 닫힌 괄호까지 접근한 상태이다.

여기서 / 인덱스에 접근하고, 그것이 바로 stack에 담기면 앞에 있는 *보다 /를 먼저 연산하게 되어서

연산자 우선순위에 벗어나게 된다.

그렇기 때문에 * 혹은 /이 stack에 담기기 전에 이전에 * 혹은 /가 있는지 확인해 주는 작업이 필요하다.

*를 먼저 빼 주고 /를 stack에 담은 결과이다.

그 다음 인덱스는 닫힌 괄호이기 때문에 열린 괄호 이전의 연산자들을 모두 빼주면 된다.

그럼 이런 모습이 되고, 인덱스는 모두 돌았지만 stack 안에 값이 남아 있기 때문에, stack의 값들을 모두 빼 주면

예시의 답인 GABCD/E+*F/-*가 나온게 된다.

 

< 4번 조건의 예시 >

 

A+B*C-D/E

이러한 예제가 있다고 가정했을 때, +는 처음에 등장한 연산자이므로 제외하고, for문의 인덱스가 - 연산자에 접근했을 때,
계산이 나누어져야 하기 때문에, 앞에 연산자들을 전부 다 stack에서 빼고 - 연산자를 stack에 넣어야 한다.
그래서 위 예제의 답은 ABC*+DE-/이다.

let input = readLine()!.map{String($0)}
var stack = [String]()
var result = [String]()

for i in input.indices {
    // 열린 괄호일 때
    if input[i] == "(" {
        stack.append(input[i])
    // 닫힌 괄호일 때
    } else if input[i] == ")" {
        while !stack.isEmpty && stack.last != "(" {
            result.append(stack.removeLast())
        }
        // 열린 괄호 빼기 )
        stack.removeLast()
    } else if input[i] == "*" || input[i] == "/" {
        // +나 /일 때, 스택의 마지막 값이 *나 /일 경우 먼저 계산해 주어야 해서 스택에서 빼야 한다.
        while !stack.isEmpty && (stack.last == "*" || stack.last == "/") {
            result.append(stack.removeLast())
        }
        stack.append(input[i])
    } else if input[i] == "+" || input[i] == "-" {
        // +나 -일 때 우선순위가 제일 높고, stack의 마지막 값이 연산자일 경우 stack.removeLast() 반복
        while !stack.isEmpty && stack.last != "(" {
            result.append(stack.removeLast())
        }
        stack.append(input[i])
        // 알파벳일 경우 바로 result에 삽입
    } else {
        result.append(input[i])
    }
 }

// stack에 연산자가 남아 있을 경우
while !stack.isEmpty {
    result.append(stack.removeLast())
}

print(result.map{String($0)}.joined(separator: ""))

// 메모리 : 69100 KB, 시간 : 8 ms

구현 문제 연습이 더 많이 필요한 것 같다.