[자료구조] 중위표기식과 후위표기식 간 변환방법 완벽하게 부수기 +_+ | stack의 응용

여러분 안녕하세요:) "C로 배우는 쉬운 자료구조" 책을 공부하며, 컴퓨터가 사용하는 연산 방법인 후위 표기법에 대해 공부한 개념, 방법에 알게된 개념들을 정리하려고 합니다.

 

1.  컴퓨터는 어떻게 산술처리를 할까요?

우리는 수식을 한번에 눈으로 훑은 후에, 무엇을 우선적으로 해야하는지 쉽게 알 수 있습니다. 근데 컴퓨터는 수식에서 연산자의 우선순위 파악을 어려워합니다. 또한 순차적으로 처리하기 때문에, 컴퓨터는 괄호, 연산자의 우선순위를 따로 처리하지 않습니다. 그 대신, 왼쪽에서 오른쪽으로 표기된 순서대로 처리를 하면 결과가 올바르게 나오는 후위 표기법을 사용합니다. 

 

중위 표기법 : 연산자를 피연산자의 가운데에 표기하는 방법입니다.

우리가 일반적으로 사용하는 일반적인 식입니다. 원래 연산자는 반드시 양 옆에 피연산자가 두 개 있어야 합니다.

ex) A+B 

 

후위 표기법 : 연산자를 피연산자 뒤에 표기하는 방법

순차적으로 왼쪽에서 오른쪽으로 식을 읽어갈 때, 피 연산자는 출력하고, 연산자는 stack에 따로 push 합니다. 이후 오른쪽 괄호가 나오면 top의 영역에 위치한 element를 pop합니다.

ex) AB+

2. 후위 표기법 algorithm

기존에 프로그램에 수식을 입력할 때, 중위표기법으로 입력을 합니다. 프로그래머들 대부분이 "A + B" 수식을 쉽게 이해하지 "AB+"를 쉽게 사용하지 않기 때문입니다.

 

컴퓨터가 중위표기법을 계산하기 위해선, 후위 표기법으로 바꿔야 합니다. 이런 방식은 후위 표기법 알고리즘이라고 합니다.

 

1. 중위 표기식에서 연산자, 피연산자 간 연산의 우선순위를 괄호로 묶습니다. (예를들어, 우선순위는 덧셈보다 곱셈이 우선순위가 높습니다.) 이를 괄호로 묶는 형태가 가장 중요합니다.
2. 수식에서 후위표기법으로 변환을 시작하는데, 수식의 맨 왼쪽 부터 차례대로 연산자 or 피연산자를 읽어갑니다. 이때 왼쪽 괄호 '('를 만나면 무시하고 다음 피연산자를 읽습니다.
3. 연산자를 만나면 스택에 push합니다. ( 후위 표기법으로 표시하기 위해 생략해선 안될 중요한 과정입니다.)
4. 오른쪽 괄호 "), }, ]"를 만나면 스택의 top element를 pop해서 출력합니다. 
5. 수식을 왼쪽에서 오른쪽까지 전부 읽어들이면, 끝나면 스택이 공백이 될 때까지 pop해서 출력합니다.

3. 후위 표기식 예시 문제 1번과 풀이과정

Case1. 다음 중위 표기식을 후위 표기식으로 변환하시오.

 

let 중위표기식 = (9-(4/2+1))*(5*2-2)

 

1. 우선순위 연산을 추가적인 괄호로 묶습니다!!!!! 저는 파란색으로 표시했습니다. ( 중요. )

 

 

 

2. 왼쪽 괄호를 만나면 무시하고 다음 피연산자를 출력한다! ( 출력을 해야 피연산자가 만들어 집니다.)

 

( 9 - ( (4 / 2....  에서 첫번째 문자(괄호)인 ' ( '  는 무시하고 두 번째 문자(피연산자) 9를 출력합니다. //출력 상태 : 9
세번째 문자(연산자) ' - '를 만나면, 스택에 push합니다. stack[0] = '-'

이어서 왼쪽 괄호 ( ( 는 무시하고, 4를 만나면 출력합니다. // 출력 상태 : 9 4 

다음 문자(연산자) 는 stack에 추가합니다. // stack[1] = ' / '

다음 문자(피연산자)는 출력합니다. // 출력상태 : 9 4 2

 

3. 이렇게 연산자를 만나면 스택에 push, 피연산자를 만나면 출력을 하다가, 오른쪽 괄호를 만나면 스택에 있던 top 원소 한개를 pop 하여 출력한다!! ( 오른쪽 괄호루 두 개 만나면 두번 pop)

 

 

후반부 입니다.

 

중위-> 후위 표기식 결과 = 942/1+-52*2-*

 

그렇다면 반대로 이번에는 반대로 하는 방법도 알면 좋겠죠?

4. 후위 표기식을 중위 표기식으로 변환하는 algorithm

1. 피연산자는 스택에 push
2. 연산자를 만나면 연산자의 연산에 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산 결과를 다시 스택에 push 합니다. 저는 이때 연산 결과를 치환해서 스택에 push합니다. 참고로, 덧셈 연산자가 결과를 갖기 위해서는 두개의 피연산자가 필요합니다. ex) 1 + 3 .  ex) 4 + //연산자1, 피연산자1 수식은 계산 불가입니다.
3. 수식이 끝나면(수식의 모든 문자를 훑으면, 마지막 스택을 pop해서 출력합니다.

5. 후위 표기식 문제 2번 + 풀이과정

Case1. 다음 후위 표기식을 중위 표기식으로 변환하시오.

 

let 후위 표기식 = 942/1+-52*2-*

 

오히려 쉽습니다..

단 치환 후, 대입할 때 괄호 주의해주셔야 합니다!!

6. 중위 -> 후위. 후위 -> 중위 표기법 중간 요약 정리

중위 표기식에서 후위 표기식으로 변환할 경우

피연산자를 마주하면 출력합니다. 연산자는 stack에 push합니다. 그러다 오른쪽 괄호를 마주하면 pop해서 top element를 출력합니다.

 

후위 표기식에서 중위 표기식으로 변환할 경우

 

피연산자는 스택에 push합니다. 연산자를 마주하면 필요한 만큼(거의,, 연산에 필요한 두 개의 피연산자) 피 연산자를 pop해서 계산하고, 다시 스택에 push합니다. ( 반복 )

 

 

어떤 수식이 주어졌을 경우 그것을 후위로, 후위로 표기한 것을 중위로, 이렇게 자유자재로 연습하다 보면 Feel이 탁 옵니다!

 

하지만 제 그림처럼 매번 스택을 그리는 것은 번거롭습니다. 따라서 제가 한 노하우를 약간 알려드리자면, stack에서 pop된 오소들은 쉽게 알 수 있게 삭제 표시를 하는 것입니다. (그 위치만 삭제 표시를 해도 아래에 원소는 남아있는 느낌?) 이렇게한다면 정말 간편합니다.

7. 햇갈리는 문제들

case 2. 후위 표기식을 중위 표기식으로 변환하시오.

 

3542/-*62*+

 

 

case 3. 중위 표기식을 후위 표기식으로 변환하시오. ( 햇갈리기 쉬운 문제 )

이 문제 풀면서 알게 됐습니다.

대입 연산자 '=' 또한 한 개의 연산자로 포함되어야 한다는 것을..

 

 

case 4. n번 째 순서 문제

 

여러 가지 문제가 있지만,

가장 중요한 것은 한 문제를 갖고 3~4번 반복하다 보면

쉽게 터득할 수 있습니다.

 

모두 파이팅!!