4.2) 복합 연산 식의 분석
여기서는 복합 연산에 대해 다룬다. 혹시 위의 사칙 연산 문제를 해결하면서 복합 연산식도 간단히 해결할 수 있다고 생각했는가? 그렇다면 직접 프로그램을 만들어보고 다음의 입력에 대해 결과를 잘 출력하는지 확인해보는 것이 좋다.
|
입력 |
출력 |
|
4 1+2+3 1+2*3+4 3*(2+3) (1+2)*(3+4)+5/6 |
6 11 15 21 |
첫 번째 식에 대해서는, 고민하다보면 그저 이전에 연산한 결과를 기록하고 연산자와 피연산자를 찾아 새롭게 연산한 값을 저장하는 행위를 반복하면 된다는 사실을 알 수 있다. 그러면 두 번째 식을 보자. 식의 결과가 13이라고 생각했는가? 그렇다면 계산 과정에서 연산자의 우선순위가 고려되지 않았을 것이다. 사칙연산에선 곱셈과 나눗셈이 덧셈과 뺄셈보다 우선순위가 높으며, 따라서 우리는 2*3을 먼저 계산한 후에 1을 더하고 4를 더해야 한다. 왜 이 경우는 순서가 중요한가? 바로 우선순위가 다른 연산자가 섞여있기 때문이다. 따라서 우리는 식을 분석하는 과정에서 이전에 획득한 연산자의 우선순위와 분석 도중에 새롭게 획득한 연산자의 우선순위를 서로 비교하여, 우선순위가 상대적으로 높은 연산자가 발견된다면 이전의 연산자를 이용한 연산을 일단 뒤로 미룬 다음, 우선순위가 높은 연산자의 연산을 먼저 수행한 다음 처리하지 않았던 연산을 수행해야 한다.
이 과정에서 스택을 이용할 수 있다. 잘 알려진 알고리즘은 다음과 같다.
1. 입력 받은 중위 표기식(infix expression)을 후위 표기식(postfix expression)으로 변환한 후, 변환한 후위 표기식을 해석한다.
2. 중위 표기식을 수식 트리 자료구조로 표현한 후, 수식 트리를 해석한다.
3. 함수의 호출과 반환이 스택과 같으므로, 함수 호출만으로 해석한다.
일반적인 컴파일러는 2번 방법, 즉 수식 트리를 이용하여 식을 표현하고 해석한다. 재귀적 사고에 능숙하다면 3번도 재미있는 해결책이다. 이 문서에서는 1번 방법을 이용하여 먼저 계산기를 구현할 것인데, 그 이유는 이해하기 쉽고 스택 자료구조를 연습하는 데 도움이 되기 때문이다. 하지만 그 전에 알아두어야 하는 개념이 몇 가지 있는데 이를 이해하고 넘어가자.
