정보처리기사 후위 표기법, 10분이면 끝 — 중위 ↔ 후위 변환 완전 정복

중위 표기법을 후위 표기법으로 바꾸는 변환 알고리즘 자체는 이미 저희 커뮤니티의 「정보처리기사 자료구조 핵심: 중위→후위 표기법 변환 15분 완전 정복」에서 스택·출력 큐를 한 스텝씩 표로 검증하며 완전히 다뤘습니다. 이 글은 그 내용을 반복하지 않고, 실제 시험과 실무에서 더 자주 놓치는 세 가지—① 후위식으로 값을 실제로 계산하는 법, ② 후위식을 다시 중위식으로 복원하는 법, ③ 전위·중위·후위 3자 비교—에만 집중합니다.

변환 원리, 30초 복습

피연산자는 만나는 즉시 출력하고, 연산자는 스택에 쌓되 스택 top의 우선순위가 더 높거나 같으면 먼저 꺼내 출력한 뒤 넣습니다. 괄호는 우선순위 계산에서 예외로, '('는 무조건 push, ')'는 '('를 만날 때까지 pop입니다. 이 규칙을 예제로 손에 익히고 싶다면 위 링크의 자매글을 먼저 보시길 권합니다. 여기서는 이 규칙을 이미 안다는 전제로 다음 단계로 넘어갑니다.

후위식 계산법 — 스택 두 번 pop이 전부다

후위 표기법의 진짜 쓸모는 변환 자체가 아니라 괄호도 우선순위 판단도 없이 왼쪽부터 한 번만 훑어서 값을 구할 수 있다는 데 있습니다. 규칙은 단 두 가지입니다.

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

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

단계	읽은 토큰	처리	스택(바닥→top)
1	3	피연산자 → push	3
2	4	피연산자 → push	3, 4
3	+	2번 pop (4, 3 순서) → 3 + 4 = 7 계산 후 push	7
4	2	피연산자 → push	7, 2
5	*	2번 pop (2, 7 순서) → 7 * 2 = 14 계산 후 push	14
6	(입력 종료)	스택에 남은 값이 최종 결과	14

검산: 원래 중위식 (3+4)*2 = 7*2 = 14. 손계산과 스택 시뮬레이션 결과가 정확히 일치합니다. 만약 이 식을 3 4 2 * +로 잘못 순서를 바꿔 읽으면 4*2=8을 먼저 계산하고 3+8=11이 나와 완전히 다른 값이 되므로, 토큰이 등장하는 순서 자체가 연산 순서를 결정한다는 점이 후위표기법의 핵심입니다.

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

후위식 → 중위식 복원 (역변환)

시험에서는 변환뿐 아니라 이미 만들어진 후위식을 보고 원래 중위식을 유추하는 문제도 나옵니다. 이때도 스택 하나로 끝납니다. 규칙은 다음과 같습니다.

• 피연산자를 만나면 그 자체를 문자열로 스택에 push한다.
• 연산자를 만나면 스택에서 두 번 pop한다. 먼저 나온 것이 오른쪽 항, 나중에 나온 것이 왼쪽 항이다. (왼쪽항 연산자 오른쪽항) 형태로 괄호를 씌워 하나의 새 문자열로 만들고, 이를 다시 push한다.

모든 토큰을 다 읽으면 스택에는 완전히 괄호가 채워진 중위식 하나만 남습니다. 예제로 A B + C D - *를 복원해 보겠습니다.

단계	읽은 토큰	처리	스택(바닥→top)
1	A	피연산자 → push	A
2	B	피연산자 → push	A, B
3	+	2번 pop (B, A 순서) → (A+B) 조립 후 push	(A+B)
4	C	피연산자 → push	(A+B), C
5	D	피연산자 → push	(A+B), C, D
6	-	2번 pop (D, C 순서) → (C-D) 조립 후 push	(A+B), (C-D)
7	*	2번 pop ((C-D), (A+B) 순서) → ((A+B)*(C-D)) 조립 후 push	((A+B)*(C-D))

스택에 최종적으로 남는 값은 ((A+B)*(C-D))이며, 가장 바깥쪽 괄호는 식 전체를 감싸는 것이라 관례상 생략하고 (A+B)*(C-D)로 표기합니다. 괄호가 스택에 쌓이는 순서 그대로 바깥쪽에 덧씌워지기 때문에, 복원된 식은 항상 완전 괄호화(fully parenthesized)된 형태로 나온다는 점이 시험 채점 기준과도 맞아떨어집니다. 검산은 반대로 이 중위식 (A+B)*(C-D)를 다시 후위 변환 알고리즘에 넣어 A B + C D - *가 나오는지 확인하면 됩니다 — 자매글에서 다룬 변환 규칙을 그대로 적용하면 동일한 결과가 나옵니다.

전위·중위·후위, 한 식으로 3자 비교

세 표기법의 차이를 가장 분명하게 보여주는 방법은 같은 식을 세 가지로 나란히 적어보는 것입니다. A - B / C(나눗셈이 뺄셈보다 우선순위가 높은 식)로 비교해 보겠습니다.

표기법	표기 결과	읽는 법
중위(Infix)	A - B / C	사람이 평소 쓰는 방식. 괄호·우선순위 규칙이 있어야 정확히 해석된다.
전위(Prefix)	- A / B C	연산자가 피연산자보다 항상 앞에 온다. 맨 앞 연산자가 최상위(가장 나중에 계산되는) 연산이다.
후위(Postfix)	A B C / -	연산자가 피연산자보다 항상 뒤에 온다. 맨 뒤 연산자가 최상위 연산이다.

세 식 모두 "B/C를 먼저 계산하고 A에서 그 결과를 뺀다"는 동일한 연산 순서를 표현합니다. 전위식은 앞에서부터 "빼기(A, 나누기(B, C))"처럼 함수 호출 구조로 읽으면 이해가 쉽고, 후위식은 뒤에서부터 같은 방식으로 읽으면 됩니다. 참고로 전위식은 후위식과 정반대로, 연산자를 만나면 오른쪽·왼쪽 순서로 두 번 pop해 "연산자 왼쪽항 오른쪽항" 형태로 붙여나가는 방식(토큰을 뒤에서부터 읽는다는 차이만 빼면 후위 복원과 대칭)으로 유도할 수 있습니다.

컴퓨터는 왜 후위 표기법을 선호할까

사람은 괄호와 연산자 우선순위를 눈으로 보며 "여기부터 먼저 계산해야지"라고 판단할 수 있지만, 컴퓨터 입장에서 중위식을 그대로 계산하려면 매번 괄호 짝을 찾고 우선순위를 비교하는 별도의 판단 로직이 필요합니다. 반면 후위식은 토큰을 왼쪽에서 오른쪽으로 딱 한 번만 훑으면서, 숫자는 쌓고 연산자를 만나면 스택 top 두 개를 그 자리에서 바로 계산하는 것만으로 끝납니다. 괄호도, 우선순위 비교도, 되돌아가는 동작(backtracking)도 전혀 필요 없습니다. 이 때문에 컴파일러가 산술식을 처리할 때, 그리고 계산기(특히 역폴란드 표기법 계산기)나 스택 기반 가상머신이 실제 연산을 수행할 때 내부적으로 후위 표기법을 사용합니다.

시험 실전 팁

• 계산 문제는 반드시 손으로 스택을 그려가며 풀 것 — 암산으로 하면 pop 순서(왼쪽/오른쪽 항)를 헷갈리기 쉽습니다.
• 뺄셈·나눗셈이 나오면 무조건 검산 — "나중에 pop한 값이 왼쪽"이라는 규칙만 정확히 지키면 부호 실수를 막을 수 있습니다.
• 복원 문제는 괄호가 항상 완전 괄호화 형태로 나온다는 점을 기억하면, 선택지 중 괄호가 빠지거나 과도한 오답을 바로 걸러낼 수 있습니다.
• 변환 알고리즘 자체가 아직 헷갈린다면 자매글의 스텝별 변환 예제부터 먼저 익히는 것을 추천합니다.

자주 묻는 질문 (FAQ)

Q. 후위식 계산과 후위식 변환, 시험에 둘 다 나오나요?

네. 중위→후위 변환 문제가 더 자주 나오지만, "다음 후위식을 계산하면?" 유형이나 "다음 후위식을 중위식으로 바꾸면?" 유형도 종종 출제됩니다. 세 유형 모두 스택의 push/pop 규칙 하나로 풀리므로, 이 글과 자매글을 함께 보면 세 유형을 모두 대비할 수 있습니다.

Q. 전위 표기법도 시험에 자주 나오나요?

후위 표기법만큼 출제 빈도가 높지는 않지만, 세 표기법을 비교하는 문제나 전위식 하나를 주고 후위식으로 바꾸라는 응용 문제로 나올 수 있습니다. 전위식은 후위식과 read 방향만 반대라는 점을 기억해두면 충분합니다.

Q. 후위식 계산에서 자꾸 값을 반대로 계산하는 실수를 하는데, 왜 그런가요?

대부분 "먼저 pop한 값이 왼쪽 항"이라고 착각하기 때문입니다. 스택은 나중에 넣은 것이 먼저 나오는 구조이므로, 연산자 앞에 먼저 등장한 피연산자가 스택에는 더 먼저(아래에) 쌓여 있습니다. 따라서 연산자를 만났을 때 먼저 pop되는 값이 오른쪽 항, 나중에 pop되는 값이 왼쪽 항이라는 순서를 규칙으로 외워두는 것이 가장 확실합니다.

지금 바로 확인해 보세요

변환 원리를 아직 손에 익히지 못했다면 「중위→후위 표기법 변환 15분 완전 정복」으로 기본기를 먼저 다지고, 계산과 역변환까지 이 글로 마무리하면 후위 표기법 관련 문제 유형을 빠짐없이 대비할 수 있습니다.

강의 자세히 보기 →