[스택 2일차] 수식계산(후위표기식) - 5문제

수식을 표현하는 방법

-  보통 일반적인 식은 숫자나 문자로 이루어진 피연산자(Operand)와 +, -, x, / 와 같은 연산자(operator) 그리고 괄호로 구성되어 있다. 이들로 이루어진 식을 표기하는 방법은 다음과 같다.

1. 중위(infix) 표기법 : 피연산자 사잉에 연산자를 쓴다.    ex) 1 + 2,  3 x 4
2. 후위(postifix) 표기법 : 피연산자 뒤에 연산자를 쓴다.   ex) 1 2 + ,  3 4 x
3. 전위(prefix) 표기법 : 피연산자 앞에 연산자를 쓴다.     ex) + 1 2,  x 3 4

 

후위표기법의 장점

1. 괄호가 필요없다.
2. 연산자 우선순위를 고려할 필요가 없다.
3. 앞에서부터 차례대로 계산하면 되기 때문에 계산이 편리하다.

 

중위표기식을 후위표기식으로 변환하기

- 계산하는 순서대로 따라가면서 연산자의 위치를 피연산자 뒤로 옮겨준다.

[ 예를 들어 ]

1. 4 x 5를 먼저 계산하므로 이를 4 5 x 로 바꾸어준다.
2. 그럼 이젠 3 + ' 4 5 x '가 되므로 +를 두 피연산자 뒤로 옮겨주면 3 4 5 x + 가 된다.
3. 따라서 중위표기식 3 + 4 x 5를 후기표기법으로 표현한 식을 3 4 5 x + 가 된다.

 

[ 문제1 ] 다음 중위표기식을 후위표기식으로 바꾸시오.

① A + B - C

② A - B x C + D

③ (A - B) x (C + D)

④ A x (B + C) x D

⑤ (A + B) x (C - D) + E / F

⑥ A + ( ( (B - C) x (D - E) - G / H)

 

후기표기식을 계산하는 방법

- 후기 표기식 3 4 5 x + 는 다음과 같이 계산합니다.

★ 스택을 이용하여 해결할 수 있습니다.

1. 피연산자가 나오는 경우 스택에 push 한다.
2. 연산자가 나오는 경우 스택에서 2개의 피연산자를 꺼내 계산한 뒤 그 결과를 다시 스택에 집어넣는다.

 

[ 문제2 ] 다음 주어진 후위표기식을 계산하세요.

① 6 2 3 + -

② 3 2 1 3 + x 5 4 - + x

 

중위표기식을 후위표기식을 바꾸는 알고리즘(스택)

1.  수식을 앞에서부터 차례대로 살펴간다.
2. 피연산자가 나오면 그대로 결과 문자열(또는 배열)에 차례대롤 저장한다.
3. 연산자가 나오는 경우 나온 연산자보다 우선순위가 같거나 높은 연산자가 stack의 top에 있을 경우 pop시켜 결과 문자열에 저장한다. 더 이상은 자신보다 우선순위가 같거나 높은 연산자가 stack의 top에 없을 때까지 이 작업을 반복한 후 나온 연산자를 push 한다.
4. 여는 괄호가 '('가 나오는 경우 스택에 그냥 push 한다.
5. 닫는 괄호가 ')'가 나오는 경우 '('가 나올 때까지 stack에서 연산자를 pop시켜 결과 문자열로 저장한다.
6. 수식을 다 살펴 보았다면 스택에 담긴 연산자들을 모두 pop시켜 결과 문자열 뒤에 저장한다.
7. 이와 같은 작업을 반복하면 후위표기식을 얻을 수 있다.

 

◆ 이 방법으로 A x (B - C) + D를 계산해 보면

c언어 수식계산(후위 표기식)

 

[ 문제3 ] 위 알고리즘을 사용하여 다음 중위표기식을 후위표기식으로 바꾸시오.

① A - ( B + C ) x D

② (A + B) x (C - D) + E / F

③ A + ((B - C) x (D - E) + F)

④ (A + B) - (C x D) + F

⑤  ( A * B + C ) *D + F                    후위표기식 : A B x C + D x F +

 

C언어 수식계산(스택) - 후위 표기식

www.acmicpc.net/problem/1918

1918번: 후위 표기식

[ 백준 1918 후위 표기식 예제 ]

      입력 : ( A * B + C ) *D + F   

      후위표기식 결과 : A B x C + D x F +

 

C언어 수식계산(스택) - 할 수 있다

www.acmicpc.net/problem/1287

1287번: 할 수 있다

 

C언어 수식계산(스택) - 계산기 프로그램

www.acmicpc.net/problem/5613

5613번: 계산기 프로그램

 

C언어 수식계산(스택) - 사칙연산

www.acmicpc.net/problem/13420

13420번: 사칙연산

 

C언어 수식계산(스택) - 계산문제

www.acmicpc.net/problem/2054

2054번: 계산 문제