최근에 코딩 문제풀이를 하다가 후위표기법에 관한 내용이 나왔어요. 사실 후위표기법이라는 말도 이때 처음 들어본 것 같네요. 학부 전공생들의 경우 처음 프로그래밍 수업을 들을 때 실습과제로 계산기 구현하기를 해보면서 후위표기법을 연습했다고 하던데, 저는 공대생이 아니었나 봅니다. 저는 이상한 어셈블리어만 공부하고 실습은 SAS를 썼었는데, 지금 와서 생각해보면 참 안타까운 커리큘럼인 것 같네요. 각설하고 그래서 뒤늦게나마 저도 연습해보고자 후위표기법을 공부해봤고 간단한 사칙연산 계산기 코드를 정리해보고자 합니다.
우선 이론적인 내용부터 정리해보겠습니다. 우리가 일반적으로 수식을 표현할 때 쓰는 방식을 중위표기법이라고 합니다. 예컨대 "3 + 4 * 2 = 11" 이라는 수식이 중위표기법으로 나타낸 것으로 볼 수 있습니다. 중위표기법은 우리에게 가장 익숙한 표현식이지만 컴퓨터의 입장에서는 해석하기 다소 까다로울 수 있습니다. 만약 괄호나 여러가지 연산이 뒤엉켜 있다면 어떨까요? 어떤 것을 먼저 연산해야되는지 왔다갔다 해야하기 때문에 컴퓨터도 효율적으로 연산하기 어렵습니다. 그래서 컴퓨터는 후위표기법을 활용해 수식을 표현하는 것이 익숙합니다.
후위표기법은 연산자를 피연산자 뒤에 위치시키는 방식입니다. 이 표기법은 연산자 우선순위와 괄호를 고려하지 않고 수식을 간결하게 표현할 수 있는 장점이 있습니다. 후위표기법에서는 수식의 각 항목을 공백이나 구분자로 구분합니다. 수식을 읽을 때 왼쪽에서 오른쪽으로 피연산자와 연산자를 차례대로 스캔하면서 처리합니다. 예를 들어, 중위표기법으로 표현된 수식 "3 + 4 * 2 / ( 1 - 5 )"을 후위표기법으로 변환하면 "3 4 2 * 1 5 - / +" 이 됩니다. 언뜻 보기에는 암호문 같아 보이죠? 하지만 이러한 표현방식이 컴퓨터 입장에서는 훨씬 더 빠르게 연산할 수 있는 표현방식입니다.
조금 더 구체적으로 후위표기법에 대해 정리해보겠습니다. 후위표기법에서는 스택을 활용합니다. 피연산자는 그대로 출력되고, 연산자는 출력 대신 스택에 저장합니다. 연산자를 스택에 저장할 때는 우선순위를 고려하여 저장합니다. 스택에 이미 있는 연산자보다 우선순위가 높은 연산자가 나오면 스택에 저장하고, 우선순위가 낮은 연산자가 나오면 스택에서 우선순위가 높은 연산자를 모두 꺼내 출력합니다. 이후 현재 연산자를 스택에 저장합니다. 수식을 모두 읽은 후에는 스택에 남은 연산자를 모두 출력합니다. 이때 스택에는 연산자가 우선순위에 따라 정렬되어 있으므로, 스택에서 연산자를 꺼내 출력하면 정확한 후위표기법을 얻을 수 있습니다.
위에 예시로 들었던 수식 "3 + 4 * 2 / ( 1 - 5 )"을 후위표기법으로 변환하는 과정을 자세히 적어보겠습니다.
1. 피연산자는 그대로 출력하므로 "3" 출력
2. "+" 연산자는 스택에 저장
3. "4" 출력
4. "*" 연산자는 스택에 저장
5. "2" 출력
6. "/" 연산자는 스택에 저장
7. "(" 괄호는 스택에 저장
8. "1" 출력
9. "-" 연산자는 우선순위가 높으므로 스택에 저장
10. "5" 출력
11. ")" 괄호가 나오면 스택에서 "(" 괄호까지의 연산자를 모두 꺼내 출력하고, "("는 스택에서 제거
12. "/" 연산자를 스택에 저장
13. "+" 연산자를 스택에 저장
수식을 모두 읽었으므로, 스택에 남은 연산자인 "/"와 "+"를 꺼내 스택에서 꺼내면 최종 후위표기법인 "3 4 2 * 1 5 - / +"을 얻을 수 있습니다. 이 후위표기법을 다시 계산하면 원래의 중위표기법 수식과 동일한 결과를 얻을 수 있습니다.
후위표기법은 수식을 계산하기 위해 스택을 활용하는 계산 알고리즘에서 많이 사용됩니다. 후위표기법은 연산자의 우선순위에 따라 괄호를 사용하지 않고도 수식을 명확하게 표현할 수 있기 때문에 계산기나 컴파일러 등 다양한 응용 분야에서 활용됩니다.
후위표기법의 장점 중 하나는 연산자의 우선순위를 명확하게 지정할 수 있다는 점입니다. 중위표기법에서는 연산자 우선순위를 결정하기 위해 괄호를 사용해야 하지만, 후위표기법에서는 스택을 활용하여 우선순위를 처리할 수 있습니다. 이로써 수식 해석의 모호성을 없앨 수 있습니다. 또한 후위표기법은 스택을 사용하여 연산을 처리하기 때문에 계산 과정이 단순하고 직관적입니다. 피연산자와 연산자를 순차적으로 처리하며 스택을 활용하므로, 복잡한 중위표기법 계산을 간단하게 변환하여 처리할 수 있습니다.
마지막으로, 후위표기법은 수식의 크기에 관계없이 일관된 방식으로 계산할 수 있다는 장점이 있습니다. 중위표기법에서는 괄호의 개수와 위치에 따라 계산 순서가 달라지지만, 후위표기법에서는 스택을 활용하여 항상 일관된 방식으로 계산할 수 있습니다.
후위표기법은 일반적인 수식 표현 방식과는 달라 익숙하지 않을 수 있습니다. 따라서 후위표기법을 사용하려면 중위표기법과 후위표기법 간의 변환 작업이 필요합니다. 이를 위해 스택을 사용하여 변환 알고리즘을 구현해야 합니다.
다음 포스팅에서는 c++ 를 활용해서 사칙연산 계산기 코드를 작성하는 것을 정리해보겠습니다.