swift 스택 자료구조 활용, 1935 후위표기식2 문제풀이

 

 

 

---

백준 1935번, 후위표기식2 문제설명

오늘은 백준 1935번, 후위표기식 2 문제를 풀어보겠습니다. post order라고도 하는 후위표기식은 rightChild -> leftChild -> parent node 순으로 순회를 하는 방식으로 pre-order, in-order 방식에 이은 세번째 노드 순회방식인데요. 문제 설명을 이어서 보겠습니다. 

 

 

 

 

이번 문제는 후위 표기식이 이미 만들어진채 주어집니다. 후위표기식을 통해서 역순으로 연산을 해서 출력하는 문제입니다. 피연산자는 A ~ 순으로 영 대문자로 주어지며, 각각의 알파벳은 피연산자로 이후 주어질 입력값 리스트의 인덱스와 대응됩니다. 예를들면, A는 0, B는 1번째 대응되는 값이 되는 식이지요.

 

후위표기식 문제를 풀 때는 스택을 활용하면 쉽게 풀 수 있습니다. 입출력 예시도 보도록 하겠습니다.

 

 

 

 

입출력 예시입니다. 첫번째 문제의 값, "ABC*+DE/-"의 도출과정을 보겠습니다. 

스택을 활용해서 푸는 요령은 이렇습니다.

1. 알파벳의 경우 알파벳에 대응되는 노드를 스택에 추가한다. 

2. 연산 기호가 나오면, 스택의 값을 두번 pop해서 역순으로 연산을 수행하고, 다시 스택에 push한다. 

 

이렇게 두가지 방식을 대입하면 후위표기식 연산결과를 쉽게 구해낼 수 있습니다. 

첫번째 문제의 경우, "ABC*+DE/-"이죠. 연산 과정을 보자면, 아래와 같습니다. 

1) stack : [1, 2, 3]

2) stack : [1] + [2 * 3] -> [1, 6]

3) stack : [] + [1 + 6] -> [7]

4) stack : [7, 4, 5]

5) stack : [7] + [4 / 5] -> [7, 0.8]

6) stack : [] + [7 - 0.8] -> [6.2] 

이며, 최종 값은 두자리수로 출력해야하므로 답이 6.20이 됩니다. 이와 같은 방식으로 바로 swift언어 + 스택을 활용해서 문제 풀어보겠습니다. 

 

 

---

후위표기식2 swift 스택활용, 백준 1935번 알고리즘 문제풀이

 

1행) 먼저 Foundation을 import해줍니다. 마지막에 소수점 두자리수까지만 출력할때 String 생성자의 format: 인자를 활용하기 위해서 import했습니다. 

3 ~ 4행) ip, ip2 클로져 상수는 각각 입력받아 정수변환, [Character] 배열 변환을 해서 반환해주는 클로져를 저장합니다. 중복된 입력을 수행할 때 이와 같이 상수를 정의해두면 보다 짧은 코드로 입력을 처리할 수 있어서 이렇게 사용해봤습니다. 

 

 

 

 

6 ~ 7행) 먼저 N, 후위표기식을 각각 정수형, [Character]타입 배열로 입력 받습니다. 

8행) G는 이후에 주어지는 피연산자에 대응되는 값들을 받을 배열입니다. 예제 입력 1로 치자면, [1, 2, 3, 4, 5]가 들어갈 것입니다.

 

 

 

 

정수를 받아서 Double타입으로 변환 후 피연산 값들이 들어갈 G배열에 추가하고 있습니다. ip 클로져 내부에서 Double형을 변환해서 반환해도 괜찮을 것 같은데, 이건 취향대로 하시면 될 것 같습니다. 

 

 

 

 

Character 타입의 extension 구현부입니다. extension Character에 정의되어있는 변수들의 역할을 설명하자면, ascii는 Character 문자의 아스키코드 값을 반환하는 변수, isAlphabet은 대문자 알파벳인지 여부를 반환하는 변수입니다. 

 

 

 

 

연산자에 맞게 연산한 결과를 계산해서 반환하는 메서드도 구현해 두었습니다. 코드 내용이 어렵지 않으니 자세한 설명은 생략하겠습니다. 나머지연산에서 뒤에 0이 들어갈 일은 없기에 별도 예외처리는 필요가 없습니다. 

 

 

 

 

후위연산식 연산 알고리즘 swift 언어 구현코드

37행) Double형 값을 담을 스택을 선언했습니다.

39 ~ 43행) 이제 후위표기식(arr)의 문자를 하나하나 순회합니다. 만약 알파벳이면 알파벳에 대응되는 G[인덱스] 값을 스택에 추가해줍니다. 

44 ~ 49행) 만약 순회하는 문자가 대문자 알파벳이 아닌 연산기호일 경우, 스택의 두개의 값을 뽑아서 역순으로 연산 후 그 결과를 스택에 추가해줍니다. 

 

위 연산들의 시간복잡도는 결과적으로 O(N)입니다. 

 

 

 

 

그렇게 구한 최종 값은 stack에 단 한개 남게 됩니다. stack.first!나 stack.last!, stack[0] 등으로 최종 결과값을 출력하는데 그 포맷은 소수점 2자리까지로 설정해서 출력해줍니다.

 

이렇게 오늘은 백준 1935번 후위표기식 2 문제를 swift언어로 풀어보았습니다. 제출결과는 아래와 같습니다.  🤗