스택과 계산기

복합 연산 식의 분석

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번 방법을 이용하여 먼저 계산기를 구현할 것인데그 이유는 이해하기 쉽고 스택 자료구조를 연습하는 데 도움이 되기 때문이다하지만 그 전에 알아두어야 하는 개념이 몇 가지 있는데 이를 이해하고 넘어가자.

댓글

댓글 본문