[Stack]사칙연산 계산기 구현(1) - 후위 표기법

 

사칙연산 계산기 구현 - 후위 표기법

 

사칙연산 프로그램을 만들 때 사용하는 수식의 표현법이다.

 

보통 우리가 사용하는 수식은 중위 표기법으로 표현된다.

중위 표기법은 연산자가 피연산자들의 사이에 위치하는 것이고

후위 표기법은 연산자가 피연산자들 뒤에 위치하는 것이다.

 

 

이 후위 표기법을 사용하게 되면 사칙연산 프로그램을 만들 때 알고리즘을 편리하게 설계할 수 있다.

 

중위 표기식을 후위 표기법으로 표현하기

 

먼저 후위 표기식을 만들기 위해 자료구조 스택이 사용된다.

 

스택에 대한 지식이 필요하다면

 

간단한 후위 표기법의 알고리즘은 다음으로 설계할 수 있다. 정말 간단하다.

 

1. 피연산자는 스택에 넣지 않고 그냥 출력한다.

 

2. 연산자는 스택이 비었으면 스택에 push한다. 

 

3. 연산자는 스택이 비어있지 않으면 스택에 있는 연산자와의 우선순위를 비교해 스택에 있는 연산자의 우선순위가 같거나 크다면 스택에 있는 연산자를 pop을 한 후 출력하고 현재 연산자는 스택에 push한다.

 

4. 만약 3번에서 우선순위가 현재 연산자가 더 크면 현재 연산자를 push한다.(스택에서 pop하지 않음)

 

5. 수식이 끝나면 스택이 빌 때 까지 pop을 한 후 출력한다.

참고로 우선순위가 크다는 것은 높다는 것과 동일하다.

 

중위 표기식 A + B * C 를 후위 표기법을 사용해 다시 수식을 써보면 A B + C * 가 된다. 

사진을 보며 풀이해보자.

 

 

1. A는 피연산자이므로 (Result에)출력한다.

 

2. + 는 연산자인데, 현재 스택이 비었으므로 push한다.

 

3. B는 피연산자이므로 출력한다.

 

4. * 와 + 의 우선순위를 비교했을 때, *가 더 크므로 스택에 push한다. 

 

5. C는 피연산자이므로 출력한다.

 

6. 수식이 끝났으므로 스택에 있는 연산자들을 모두 pop하고 출력한다.

 

7. 식 완성! Result = ABC*+

 

이 과정을 이해했다면 이제 간단한 수식은 후위 표현식으로 나타낼 수 있을 것이다.

 

연습문제를 풀어보자! (답은 댓글에)

 

1번 문제 A * B + C 

 

 

자 이제 괄호(소괄호만 다룬다)가 들어간 수식을 후위 표기법으로 표현하는 법을 알아보자.

아까 설계한 후위 표기법 알고리즘에 조금만 추가하면 된다.

 

1. 괄호가 여는 괄호이면 무조건 push한다.

 

2. 괄호가 닫는 괄호이면 stack에서 여는 괄호가 나올 때 까지 pop을 한 후 출력한다. 

 

3. 여는 괄호가 스택에 push된 후 닫는 괄호가 나올 때 까지 여는 괄호가 pop이 되면 안되므로 여는 괄호의 우선순위는 제일 작다. (위의 간단한 후위 표기법 알고리즘 3번 조건)   

 

4. 괄호는 출력하지 않는다.

 

나머지는 위와 동일.

 

중위 표기식 ( A + B ) * ( C + D ) 를 후위 표기법을 사용해 다시 수식을 써보면 A B + C D + * 가 된다. 

1. 여는 괄호는 무조건 스택에 push한다.

 

2. A는 피연산자이므로 출력한다.

 

3. 연산자 우선순위를 비교했을 때 여는 괄호의 우선순위가 작으므로 +는 push 된다.

 

4. B는 피연산자이므로 출력한다.

 

5. 닫는 괄호가 나왔으므로 여는 괄호가 나올 때 까지 pop을 하고 출력한다. (괄호 제외) 

 

6. 스택이 비었으므로 연산자를 push한다.

7. 여는 괄호는 무조건 push.

8. C는 피연산자이므로 출력한다.

 

9. 연산자 우선순위를 비교했을 때 여는 괄호의 우선순위가 작으므로 +는 push 된다.

 

10. D는 피연산자이므로 출력한다.

 

11. 닫는 괄호가 나왔으므로 여는 괄호가 나올 때 까지 pop을 하고 출력한다.

 

12.  수식이 끝났으므로 스택에 있는 연산자들을 모두 pop하고 출력한다. 

 

 

이해가 된다면 연습문제를 손으로 풀어보자.

 

2번 문제  A * ( B + C )

 

3번 문제 ( A * ( B + C )) - D

 

 

문제도 풀었다면 이제 어느 정도 후위 표기법에 대해 감을 잡았을 것이다.

 

다음 게시글에는 후위 표기법을 사용해 후위 표기 수식 계산을 하는 법을 알아볼 것이다.