주의 사항!
- 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
- 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
- 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.
이제는 다음과 같이 소괄호가 포함되어 있는 중위 표기법의 수식을 후위 표기법의 수식으로 바꾸는 방법에 대해서 생각해 보겠습니다.
4 - ( 1 + 2 * 3 ) / 5
후위 표기법의 수식에서는 먼저 연산이 이뤄져야 하는 연산자가 뒤에 연산이 이뤄지는 연산자보다 앞에 위치해야 합니다. 따라서 위의 수식에서는 '+'연산자와 '*'연산자가 '/'연산자보다 먼저 스택을 빠져나와서 배치되어야 합니다. 이를 위해서 괄호를 어떻게 처리하는지 변환의 과정을 설명하겠습니다. 중위 표기법을 후위 표기법으로 변환하는 과정입니다.
위 과정까지는 이해하셨으리라 생각됩니다. 앞선 시간에 설명했던 후위 표기법으로의 변환 알고리즘으로 변환을 진행했습니다. 이제 '('연산자를 처리해야 합니다. 이 연산자를 스택에 저장하려는데 스택에는 이미 '-'연산자가 저장되어 있어야 합니다. 기존 알고리즘 대로라면 두 연산자의 우선순위를 비교해야 하지만, 괄호를 열고 닫는 연산자의 경우에는 우선순위를 비교하지 않고 스택에 그대로 저장합니다. 이후 계속 변환을 진행하면 다음과 같이 됩니다.
여기까지 진행하는 것도 지난 시간에 한 것과 같습니다. 이제 닫는 괄호 ')'연산자를 처리해야 합니다. 이 연산자를 읽게 되면 스택에 저장하지 않습니다. 그리고 '('연산자가 나올 때까지 스택에 저장된 연산자들을 하나씩 빼서 배치합니다. 이후 '('연산자가 나오면 이 연산자는 배치하지 않고 버립니다. 그럼 다음과 같이 됩니다.
이후 변환을 계속 수행하면 다음과 같이 변환이 끝이 나게 됩니다.
책에서는 위 내용까지만 설명하고 있습니다. 여기에 더해서 저는 중위 표기법을 전위 표기법으로 변환하는 알고리즘에 괄호까지 처리하도록 하는 알고리즘을 생각해 보았습니다.
- 기존 수식의 꼬리부터 데이터를 읽는다.
- 읽어 들인 데이터가 피연산자라면 그대로 배치한다.
- 읽어 들인 데이터가 연산자라면 스택에 저장한다.
- 읽어 들인 연산자가 여는 괄호 '('라면 이를 버리고, 스택에서 닫는 괄호 ')'가 나올 때까지 연산자를 하나씩 빼서 배치한다. 닫는 괄호 ')'가 나오면 이는 배치하지 않고 버린다.
- 연산자 A를 스택에 저장하려는데 연산자 B가 스택에 이미 저장되어 있다면, 두 연산자의 우선순위를 비교한다.
- 만약 연산자 A가 닫는 괄호 ')'이거나 연산자 B가 닫는 괄호 ')'라면 우선순위를 비교하지 않고 연산자 A를 스택에 저장한다.
- 우선순위를 비교하여 연산자 A의 우선순위가 더 높거나 같다면 연산자 A를 그대로 스택에 저장한다.
- 우선순위를 비교하여 연산자 A의 우선순위가 더 낮다면 연산자 B를 스택에서 꺼내 배치하고 연산자 A를 스택에 저장한다.
- 만약 연산자 B를 스택에서 꺼냈는데 다음으로 연산자 C가 스택에 있다면 연산자 C와 연산자 A의 우선순위를 비교한다.
- 더 이상 읽어 들일 데이터가 없다면 스택에 남아 있는 연산자들을 하나씩 꺼내어 모두 배치한다.
- 변환이 완료되면 배치된 데이터를 거꾸로 재배치한다.
위 알고리즘을 바탕으로 변환의 과정을 설명하겠습니다. 변환할 수식은 다음과 같습니다.
4 - ( 1 + 2 * 3 ) / 5
여기까지는 이해하셨을 것입니다. 이제 닫는 괄호를 처리해야 합니다. 닫는 괄호는 연산자의 우선순위를 비교하지 않고 스택에 저장합니다. 이후 알고리즘을 계속 진행하면 다음과 같이 됩니다.
'+'연산자는 '*'연산자보다 우선순위가 낮습니다. 따라서 '*'연산자를 스택에서 빼내어 배치합니다. 그리고 스택의 다음 연산자는 ')'이므로 우선순위를 비교하지 않고 '+'연산자를 스택에 저장합니다. 이후 알고리즘을 진행하면 다음과 같이 됩니다.
이제 여는 괄호 '('를 처리해야 합니다. 알고리즘에 따라 이는 버리고 스택에서 닫는 괄호 ')'가 나올 때까지 연산자를 빼내어 배치합니다. 그리고 ')'가 나오면 이는 버립니다. 그럼 다음과 같이 됩니다.
이제 '-'연산자를 처리해야 합니다. '-'연산자는 '/'연산자보다 우선순위가 낮기 때문에 스택에서 '/'연산자를 빼내어 배치하고 '-'연산자를 스택에 저장합니다. 이후 알고리즘을 진행하면 다음과 같이 변환이 완료됩니다.
이제 위와 같이 변환이 끝난 수식을 거꾸로 재배치합니다. 이로써 변환이 완전히 끝이 납니다.
