스택 - 후위표기식

 

---

계산기

문자열로 된 계산식이 주어질 때, 스택을 이용하여 계산식의 값을 계산할 수 있다

1. 중위 표기법의 수식을 스택을 이용하여 후위 표기법으로 바꾼다
2. 후위 표기법의 수식을 스택을 이용하여 계산한다

 

중위 표기법의 수식을 후위 표기법으로 변환하는 방법

1. 수식을 하나씩 읽는다
2. 수식이 피연산자이면 출력한다
3. 수식이 연산자이면 스택에 push한다
4. 연산자의 우선순위를 따진다
5. 더이상 읽을 수식이 없으면 스택에 있는 연산자를 모두 pop한다

 

변환 방법의 예

1. 덧셈과 뺄셈의 경우

• 연산자는 스택에 push, 피연산자는 출력하기
• 스택에 사칙연산 우선순위가 동등한 연산이 있을 경우 해당 연산을 pop한 후 push하기

 

중위 표기식이 3+4+5 인 경우의 예

3은 피연산자이므로 출력한다

 

+는 연산자이므로 push한다

 

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

 

-는 연산자이므로 push를 하는데, 이미 스택에 자신과 사칙연산 우선순위가 동등한 +가 있으므로 +를 pop하고 -를 push한다

 

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

 

더이상 읽어들일 문자열이 없으므로 스택에 있는 연산자들을 pop한다

중위 표기식이 3+4+5를 후위 표기식으로 변환한 결과는 34+5- 이다

 

2. 곱셈과 나눗셈의 경우

• 스택에 사칙연산 우선순위가 동등한 연산이나 높은 연산이 있을 경우 해당 연산을 pop한 후 push하기

 

중위 표기식이 3+4*5-6 인 경우의 예

 

*연산이 나올때까지 과정을 스킵하면 다음과 같이 된다

 

*연산은 스택에 있는 +보다 사칙연산 우선순위가 높으므로 그냥 push를 한다

 

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

 

이미 스택에 있는 *는 -보다 사칙연산 우선순위가 높으므로 pop하고 다음에 있는 +는 사칙연산 우선순위가 동등하므로 마찬가지로 pop한 후 -를 push한다

 

최종 결과

중위 표기식이 3+45-6를 후위 표기식으로 변환한 결과는 345*+6- 이다

 

3. 괄호의 경우

• 괄호는 연산자로 취급한다
• 열린 괄호’(’는 스택에 들어가기전 우선순위(in-coming priority)가 가장 높지만, 스택에 들어가고 나면 우선순위(in-stack priority)가 가장 낮다
• 닫힌 괄호’)’는 열린 괄호가 나올 때 까지 스택에 있는 연산자를 모조리 pop시킨다

 

중위 표기식이 3*(4+5)-6 인 경우의 예

 

괄호가 나오기 전까지의 과정을 스킵하면 다음과 같다

 

열린 괄호는 스택에 들어가기 전 우선순위가 가장 높으므로 그냥 push한다

 

4는 피연산자이므로 출력하고

열린 괄호가 스택에 들어가면 우선순위가 가장 낮아지므로 +는 자신 보다 우선순위가 낮은 열린 괄호 위에 push한다

 

닫힌 괄호가 나오면 스택에서 열린 괄호가 나올 때까지 스택에 있는 연산자들을 모조리 pop한다

 

최종 결과

중위 표기식이 3*(4+5)-6를 후위 표기식으로 변환한 결과는 345+*6- 이다

 

후위 표기식 계산하기

1. 피연산자를 스택에 push한다
2. 연산자가 나오면 스택에서 피연산자를 두개 pop해서 연산한다
3. 연산한 결과를 다시 스택에 push한다
4. 더 이상 읽어들일 식이 없으면 결과를 pop한다

 

후의 표기식 계산의 예

후위 표기식이 652-* 인 경우

 

피연산자를 만나면 스택에 push한다

6 5 2를 차례대로 push하였다

 

다음으로 연산자를 만나면 스택에서 피연산자를 두 개 pop한다

두 개의 피연산자를 가지고 연산을 한다

이 때, 연산의 순서에 주의한다

두번째로 꺼낸 피연사자에서 처음 꺼낸 피연산자를 연산해야 한다

즉, 2-5가 되면 안되고 5-2가 되어야 한다

 

연산한 결과를 스택에 push한다

 

다음 수식이 연산자 이므로 스택에서 피연산자 두 개를 pop한다

연산한 결과를 스택에 push한다

 

더 이상 읽어들일 수식이 없으면 pop한다

마지막 pop한 요소가 결과가 된다

 

관련 문제: swea1224 계산기3

---