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

 

문제 링크

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

1918번: 후위 표기식

 

후위 표기식, 나에겐 낯설었지만, 정형화된 풀이방법이 있다고 한다. 후위표기식과 비슷한 모든문제는 대부분 stack을 이용해서 푼다고한다. 잘 익혀두자.

 

내가 푼 풀이

우선 후위표기식에 대한 알고리즘을 풀어본 적이 없었기에 인터넷을 참고하여 풀이했다. 그래서 코드가 거의 비슷하다 (허허.. 언제쯤 나도 잘할 수 있을까)

입력받는 표기식을 line, 답안으로 출력할 배열을 answer, 연산자를 저장해두고 우선순위를 고려해줄 배열을 stack으로 설정하고, 이 세개의 변수를 활용하여 문제를 풀었다.

• line의 맨 앞부터 순서대로 한 character씩 파악해볼 것이다.
• 피연산자 (알파벳)은 모두 answer로 push해준다.
• 피연산자가 아니라면, 우선순위를 고려하기 위해 코드를 작성한다.
  • ( 라면, stack에 넣어준다.
  • ) 라면, 한번의 계산이 끝난다는 뜻이기 때문에, )를 만난다면 stack에 들어있는 모든 연산자를 pop하여 answer로 push해준다.
  • 연산자를 만난다면, 우선순위를 고려해야한다.
    1. 현재 만난 연산자의 우선순위가 stack에 있는 우선순위보다 높다면, 그대로 stack에 넣어준다. (stack은 나중에 넣으면 먼저 출력되기 때문에)
    2. 현재 만난 연산자의 우선순위가, stack 마지막에 있는 연산자 우선순위보다 낮다면, stack을 비워주고 나서 stack에 push해준다. stack을 비워준다는 것은, stack에 있는 연산자를 answer로 push 해준다는 의미이다.

이  풀이방법을 그대로 코드로 구현하면 아래와 같다.

var line = Array(readLine()!)
var answer: [Character] = []
var stack: [Character] = []

func getPriority(op: Character) -> Int{
    switch op {
    case "+":
        return 1
    case "-":
        return 1
    case "*":
        return 2
    case "/":
        return 2
    case "(":
        return 0
    default:
        break
    }
    return 0
}

for op in line {
    if op.isLetter { // op가 ABC..(피연산자)이면 answer로 push
        answer.append(op)
    } else {
        if op == "(" { // ( 이면 stack으로 push
        stack.append(op)
        } else if op == ")" { // ) 이면 우선순위가 끝났다는 뜻이므로, stack에 있는 연산자를 pop하여 answer로 push
            while true { // 다 꺼내야하므로 반복문 활용
                let data = stack.removeLast()
                if data == "(" { break } // (가 나타나면 answer에 넣지 않으려고 break
                answer.append(data!)
            }
        } else if stack.isEmpty || getPriority(op: op) > getPriority(op: stack.last!) {
            // stack이 비었거나, 현재 op의우선순위가 더 높으면 stack에 push
            stack.append(op)
        } else {
            // stack에 이미 연산자들이 존재하면서 현재 op의 우선순위가 낮을경우 (+,- 인경우)
            // stack에 있는 모든 연산자를 answer로 push한 후 stack으로 push 해야함
            while !stack.isEmpty {
                let temp = stack.last!
                if getPriority(op: temp) >= getPriority(op: op) {
                    let data = stack.removeLast()
                    answer.append(data)
                } else {
                    break
                }
            }
            stack.append(op)
        }
    }
}

// 위 단계가 모두 끝나면 stack에 쌓여있는 연산자를 하나씩 answer로 push
while !stack.isEmpty {
    answer.append(stack.removeLast())
}

print(String(answer))

 

나도 코딩테스트 잘하고싶다. 아직 꾸준히 공부한지 한달 도 채 되지 않았기 때문에 모든 문제의 유형이 신선한 거겟지? 차차 내 실력이 나아지길 바란다 ㅠㅠ 꾹참고 공부하면 언젠간 나아지겟지...