스택의 응용 - 후위 표기식

스택의 응용 중 하나인 후위 표기식에 대해서 배워보자.

후위 표기식

 

우리가 자주 사용하는 표기식은 중위 표기식(infix expression)을 따른다.

5 + 3

 

후위 표기식(postfix expression)은 연산자가 피연산자 뒤에 나오는 것을 말한다.

5  3 +

 

후위 표기식 계산법

 

7 4 -3 * 1 5 + / * 

스택 자료구조를 이용해서 계산할 수 있다.

핵심은 두 수를 뽑을 때의 순서가 중요하다.

 

방법은 다음과 같다.

1) 피연산자(즉, 숫자)가 들어오면 무조건 출력

2) 연산자가 들어오면 스택의 최상단에서 두 값을 뽑아 연산자에 맞게 계산하고 다시 스택에 넣어준다.

 

단계별로 확인해보자.

input : 7 4 -3 * 1 5 + / * 

Stack
7
7 4
7 4 -3
7 -12 ( * 연산자가 들어오면 스택의 최상단에서 두 값을 뽑아 계산한다.) 이 때의 순서는 4 * (-3)이 맞는 표현이며, (-3) * 4는 맞지 않는 표현이다.
7 -12 1
7 -12 1 5
7 -12 6 (+ 연산자, 1 + 5 = 6을 스택에 넣어준다.)
7 -2 ( / 연산자, -12 / 6 = -2를 스택에 넣어준다.)
-14 ( * 연산자, 7 * (-2) = -14를 스택에 넣어준다.)

 

중위 표기식을 후위 표기식으로 변환 (괄호가 없는 ver.)

 

조금 더 깊게 들어가 보자.

 

우리가 잘 알고 있는 중위 표기식을 후위 표기식으로 어떻게 변환할까?

=> 스택 자료구조를 사용하여 해결할 수 있다.

 

풀어쓰면 다음과 같다.

1) 중위 표기식을 처음부터 순서대로 읽으면서 피연산자는 즉시 출력한다.

2) 모든 연산자는 일단 스택에 push 한다.

단, 이때 스택 내에 우선순위가 자신보다 더 높은 연산자가 있다면 pop 하여 출력하고

이후 push 한다. 여기서 더 높은 연산자는 정말로 높은 우선순위 연산자일 수도 있고,

혹은 우선순위가 같은 연산자도 먼저 들어온 연산자가 더 높은 우선순위를 가지게 된다.

 

핵심 방법은 다음과 같다.

1) 피연산자는 출력한다.

2) 연산자라면 아래와 같이 고려한다.

2-1) stack.top() < 들어오는 연산자이면, 들어오는 연산자를 스택에 push 한다.

2-2) stack.top() >= 들어오는 연산자이면, 이 조건에 맞는 연산자들은 다 pop 하여

결과에 추가하고, 들어오는 연산자를 스택에 push 한다.

 

단계별로 확인해보자.

input : 2 - 10 / 5 * 6 + 4

Stack	Result
	2
-	2
	2 10
- /	2 10
- /	2 10 5
- *	2 10 5 /
- *	2 10 5 / 6
+	2 10 5 / 6 * -
+	2 10 5 / 6 * - 4
	2 10 5 / 6 * - 4 +

중위 표기식을 후위 표기식으로 변환 (괄호가 있는 ver.)

 

그렇다면 괄호가 있으면 어떻게 처리할까?

 

핵심 방법은 다음과 같다.

1) 여는 괄호가 있으면 무조건 스택에 push 한다.

2) 닫는 괄호가 나오면 스택에서 여는 괄호가 나올 때까지 pop 하여 출력하고,

마지막 여는 괄호도 pop 해준다, 이때 닫는 괄호는 스택에 push 하지 않는다.

 

단계별로 확인해보자.

input : 3 + ( ( 4 * 7 ) / 2 )

Stack	Result
	3
+	3
+ (	3
+ ( (	3
+ ( (	3 4
+ ( ( *	3 4
+ ( ( *	3 4 7
+ (	3 4 7 *
+ ( /	3 4 7 *
+ ( /	3 4 7 * 2
+	3 4 7 * 2 /
	3 4 7 * 2 / +

참고:)

 

YouTube