정보처리기사 자료구조 핵심: 중위→후위 표기법 변환 15분 완전 정복

정보처리기사 필기 자료구조 파트에서 중위 표기법(Infix)을 후위 표기법(Postfix)으로 변환하는 문제는 거의 매 회차 출제되는 핵심 유형입니다. 공식만 외워서는 실전에서 자주 틀리고, 스택이 실제로 어떻게 움직이는지 손으로 직접 따라가 봐야 완전히 내 것이 됩니다. 이 글에서는 변환 알고리즘의 원리부터 스택·출력 큐 상태를 한 스텝씩 표로 보여주는 두 가지 예제, 그리고 후위표기식을 실제로 계산하는 방법까지 시험에 나오는 형태 그대로 정리했습니다.

전위·중위·후위 표기법이란?

연산자를 피연산자(숫자·문자) 기준으로 어디에 쓰느냐에 따라 세 가지로 나뉩니다. A+B라는 간단한 식으로 비교하면 다음과 같습니다.

컴퓨터가 후위표기법을 좋아하는 이유는 간단합니다. 연산자 우선순위를 계산기 안에서 미리 판단할 필요 없이, 왼쪽부터 읽으면서 스택에 쌓았다 꺼내는 것만으로 정확한 계산 순서가 저절로 결정되기 때문입니다.

이 강의에서 배우는 것

단 하나의 차시(약 15분)에 후위표기식 변환의 핵심을 모두 담았습니다.

중위→후위 변환 알고리즘 원리 (스택 기반)

중위 표기식을 왼쪽부터 한 토큰씩 읽으면서 아래 4가지 규칙만 그대로 적용하면 후위 표기식이 완성됩니다.

• 피연산자(A, B, C…)를 만나면 스택에 넣지 않고 곧바로 출력 큐에 추가합니다.
• 여는 괄호 '('는 우선순위를 따지지 않고 무조건 스택에 push합니다.
• 닫는 괄호 ')'를 만나면 스택 top에서 여는 괄호 '('가 나올 때까지 연산자를 계속 pop하여 출력에 추가하고, '(' 자신은 출력하지 않고 버립니다.
• 연산자(+, -, *, /)를 만나면 스택 top이 '(' 가 아니면서 top 연산자의 우선순위가 현재 연산자보다 크거나 같은 동안 계속 pop하여 출력에 추가한 뒤, 현재 연산자를 push합니다. (우선순위가 같아도 pop하는 이유는 +, -, *, / 모두 왼쪽에서 오른쪽으로 계산하는 좌결합 연산자이기 때문입니다.)

모든 입력을 다 읽은 후에는 스택에 남아있는 연산자를 top부터 순서대로 모두 pop하여 출력 큐 뒤에 붙이면 변환이 끝납니다.

연산자 우선순위

예제 1: A + B * C 스텝별 풀이

먼저 괄호 없이 우선순위만 다른 가장 기본적인 식으로 연습합니다.

최종 결과는 ABC*+ 입니다. *가 +보다 먼저 출력된 이유는 곱셈의 우선순위가 더 높아 스택에 나중까지 남아 있다가 마지막에 먼저 빠져나왔기 때문입니다.

예제 2: (A + B) * C - D 스텝별 풀이

이번에는 괄호와, 우선순위가 같은 연산자(*와 -가 아니라 뒤에서 비교되는 상황)가 섞인 실제 기출과 가장 비슷한 형태로 검증합니다.

최종 결과는 AB+C*D- 입니다. 괄호 안의 A+B가 가장 먼저 출력되고, 그다음 우선순위가 높은 *가, 마지막으로 -가 출력되는 순서를 표에서 그대로 확인할 수 있습니다.

검산(다른 방식으로 재확인): 완전 괄호화로 접근하면 (A+B)*C-D → (((A+B)*C)-D). 안쪽부터 후위로 바꾸면 (A+B)→AB+, 그다음 (AB+ 와 C)→AB+C*, 마지막으로 (AB+C* 와 D)→AB+C*D- 가 되어 스택 시뮬레이션 결과와 정확히 일치합니다.

보너스: 후위표기식 계산법 (스택으로 값 구하기)

후위표기식은 반대로 값을 계산할 때도 스택 하나로 끝납니다. 규칙은 두 가지뿐입니다.

• 숫자(피연산자)를 만나면 그대로 스택에 push합니다.
• 연산자를 만나면 스택에서 두 번 pop합니다. 먼저 pop한 값이 오른쪽 피연산자, 나중에 pop한 값이 왼쪽 피연산자입니다. "나중pop 연산자 먼저pop" 순서로 계산한 뒤 결과를 다시 push합니다.

예를 들어 3 4 * 5 + (중위로는 (3*4)+5)를 계산해보겠습니다.

최종적으로 스택에 남은 값 17이 계산 결과입니다. (3*4)+5 = 12+5 = 17로 손계산 결과와 정확히 일치합니다.

주의: -, / 처럼 순서가 중요한 연산자는 pop 순서를 반드시 지켜야 합니다. 예를 들어 스택에 [12, 5]가 쌓인 상태에서 연산자가 '-' 라면, 먼저 pop한 5가 아니라 나중에 pop한 12에서 먼저 pop한 5를 빼야(12-5=7) 정답입니다. 반대로 계산하면(5-12=-7) 오답 처리됩니다.

시험에서 자주 나오는 함정 패턴

• 우선순위가 같은 연산자를 만났을 때 push만 하고 pop을 안 하는 실수 — +와 -, 또는 *와 /처럼 우선순위가 같은 연산자가 연달아 나오면 스택 top을 먼저 pop한 뒤 push해야 합니다. (좌결합 규칙)
• 괄호를 무시하고 우선순위만으로 판단하는 실수 — 스택 top이 '(' 라면 뒤에 오는 연산자의 우선순위와 상관없이 절대 pop하지 않고 무조건 push합니다.
• 후위식 계산 시 뺄셈·나눗셈의 피연산자 순서를 바꾸는 실수 — 스택에서 pop한 순서(나중에 나온 값이 왼쪽, 먼저 나온 값이 오른쪽)를 헷갈리면 부호가 반대인 오답이 나옵니다.
• 닫는 괄호 ')' 를 출력 큐에 그대로 옮기는 실수 — 괄호 기호는 여는 것과 닫는 것 모두 최종 후위표기식에는 절대 등장하지 않습니다.

이런 분께 추천합니다

• 정보처리기사 필기 자료구조 파트에서 후위표기식에서 막히는 분
• 개념은 알겠는데 문제를 풀면 자꾸 틀리는 분
• 시험을 앞두고 짧은 시간에 핵심만 빠르게 정리하고 싶은 분
• 자료구조 과목을 처음 시작하는 비전공자

수강 정보

• 수강료: 무료
• 차시 수: 1차시
• 강사: 누구나패스
• 카테고리: 자격증

자주 묻는 질문 (FAQ)

Q. 후위표기법이 정보처리기사 시험에서 얼마나 자주 나오나요?
A. 거의 매 회차 자료구조 파트에서 출제되는 단골 유형입니다. 스택의 push/pop 규칙만 정확히 익혀두면 점수를 안정적으로 확보할 수 있습니다.

Q. 비전공자도 이해할 수 있나요?
A. 네. 이 강의는 비전공자를 기준으로, 문자를 하나씩 읽을 때마다 스택과 출력 큐가 어떻게 바뀌는지 표로 직접 보여주기 때문에 사전 지식 없이도 따라올 수 있습니다.

Q. 스택에서 pop하는 순서가 왜 그렇게 중요한가요?
A. 덧셈·곱셈은 순서를 바꿔도 결과가 같지만, 뺄셈·나눗셈은 피연산자 순서가 바뀌면 답이 완전히 달라집니다. 후위표기식을 계산할 때 먼저 pop한 값이 오른쪽, 나중에 pop한 값이 왼쪽이라는 규칙을 지켜야 정답이 나옵니다.

Q. 15분짜리 강의인데 충분한가요?
A. 후위표기식 변환 문제는 패턴이 정해져 있어 핵심 원리와 예제 2개만 손으로 따라가 보면 대부분의 기출 유형을 풀 수 있습니다. 시험 전 빠른 복습용으로도 적합합니다.

강의 자세히 보기 →