중위 표기식과 후위 표기식은 수학적 표현과 프로그래밍에서 연산 순서를 명확히 나타내기 위해 사용됩니다. 중위 표기식은 일반적인 수학 표기법으로, 연산자가 피연산자 사이에 위치합니다. 반면, 후위 표기식은 연산자를 피연산자 뒤에 배치하여 괄호 없이도 연산 순서를 쉽게 이해할 수 있습니다. 본 기사에서는 중위 표기식을 후위 표기식으로 변환하는 과정을 통해, 데이터 구조와 알고리즘에 대한 이해를 심화합니다.
중위 표기식과 후위 표기식의 개념
중위 표기식
중위 표기식은 우리가 일상적으로 사용하는 수학적 표현 방식으로, 연산자가 피연산자 사이에 위치합니다. 예를 들어, 식 A + B * C는 중위 표기식으로, 괄호를 사용해 연산 우선순위를 명시할 수 있습니다.
후위 표기식
후위 표기식(Postfix Notation)은 연산자가 피연산자 뒤에 위치하는 방식입니다. 예를 들어, 중위 표기식 A + B * C는 후위 표기식으로 A B C * +로 변환됩니다. 이 표기법은 괄호 없이도 연산 순서를 명확히 이해할 수 있어, 컴퓨터 연산에 적합합니다.
사용 사례
- 중위 표기식: 수학에서의 일반적인 연산식 표현.
- 후위 표기식: 스택 기반 연산(예: 계산기, 컴파일러)에서 연산 순서를 명확히 하기 위해 사용.
두 표기식의 차이를 이해하면 변환 과정의 필요성과 알고리즘 설계에 대한 직관을 얻을 수 있습니다.
변환 알고리즘 개요
알고리즘의 목적
중위 표기식을 후위 표기식으로 변환하는 알고리즘은 괄호와 연산자 우선순위를 고려하여, 연산 순서가 명확한 후위 표기식으로 재구성하는 것을 목표로 합니다. 이 과정은 스택 자료 구조를 활용하여 구현됩니다.
변환 과정의 주요 단계
- 입력 식 읽기
중위 표기식의 각 문자를 왼쪽에서 오른쪽으로 읽습니다. - 피연산자 처리
피연산자는 즉시 출력(결과 리스트에 추가)합니다. - 연산자 처리
- 연산자는 스택에 저장합니다.
- 스택에 이미 저장된 연산자와 비교하여, 우선순위가 낮거나 같으면 스택의 연산자를 출력하고 새 연산자를 스택에 저장합니다.
- 괄호 처리
- 여는 괄호
(는 스택에 저장합니다. - 닫는 괄호
)가 나오면, 여는 괄호(를 만날 때까지 스택의 연산자를 출력합니다.
- 남은 연산자 출력
입력 식 처리가 끝난 후, 스택에 남아 있는 모든 연산자를 출력합니다.
변환 알고리즘의 장점
- 연산 우선순위와 괄호를 자동으로 처리하므로 결과가 명확합니다.
- 컴퓨터 연산에 적합한 후위 표기식을 생성합니다.
이 알고리즘은 명료성과 효율성을 갖춘 대표적인 예로, 데이터 구조와 알고리즘을 배우는 데 중요한 실습 주제입니다.
스택 자료 구조의 역할
스택의 기본 개념
스택은 후입선출(LIFO, Last In First Out) 원칙을 따르는 자료 구조로, 데이터가 쌓인 순서와 반대 순서로 처리됩니다. 이는 중위 표기식을 후위 표기식으로 변환할 때 연산자와 괄호를 관리하기에 적합합니다.
스택의 주요 역할
- 연산자 저장
- 입력을 읽는 동안 연산자는 스택에 저장됩니다.
- 연산 우선순위에 따라 스택에서 꺼내거나 새로운 연산자를 추가합니다.
- 괄호 관리
- 여는 괄호
(는 단순히 스택에 저장됩니다. - 닫는 괄호
)가 나오면, 여는 괄호를 만날 때까지 스택에서 연산자를 꺼내 출력합니다.
- 우선순위 처리
- 연산자의 우선순위가 스택에 이미 저장된 연산자보다 높으면 스택에 추가합니다.
- 우선순위가 낮거나 같으면 스택에서 연산자를 꺼내 출력하고, 새 연산자를 추가합니다.
스택이 필수적인 이유
- 연산 순서 유지: 스택은 연산자 우선순위와 괄호를 통해 연산 순서를 자동으로 유지합니다.
- 효율적인 처리: 스택의 간단한 동작(push와 pop)은 알고리즘의 구현을 간소화합니다.
- 일관성 보장: 알고리즘 전체에서 연산자와 괄호의 일관된 처리를 가능하게 합니다.
스택 자료 구조를 올바르게 이해하고 활용하면 중위 표기식을 후위 표기식으로 변환하는 과정을 효율적으로 구현할 수 있습니다.
연산자 우선순위와 괄호 처리
연산자 우선순위의 정의
연산자 우선순위는 연산이 수행되는 순서를 결정합니다. 변환 과정에서는 아래와 같은 우선순위를 사용합니다:
- 괄호
(,) - 곱셈(
*), 나눗셈(/), 나머지(%) - 덧셈(
+), 뺄셈(-)
연산자 우선순위 처리 방법
- 현재 연산자가 스택의 최상단 연산자보다 높은 우선순위를 가지면, 스택에 push합니다.
- 현재 연산자가 스택의 최상단 연산자보다 낮거나 같은 우선순위를 가지면, 스택에서 연산자를 pop하여 출력합니다. 그런 다음 현재 연산자를 push합니다.
괄호 처리
- 여는 괄호
(는 무조건 스택에 push합니다. - 닫는 괄호
)가 나오면:
- 여는 괄호
(를 만날 때까지 스택에서 연산자를 pop하여 출력합니다. - 여는 괄호
(는 단순히 제거하고 출력하지 않습니다.
예제: 중위 표기식 변환
중위 표기식: A + B * (C - D)
변환 과정:
A: 피연산자 → 출력:A+: 연산자 → 스택에 pushB: 피연산자 → 출력:A B*: 연산자 → 우선순위가 높으므로 스택에 push(: 여는 괄호 → 스택에 pushC: 피연산자 → 출력:A B C-: 연산자 → 스택에 pushD: 피연산자 → 출력:A B C D): 닫는 괄호 →-를 pop하여 출력, 여는 괄호 제거- 나머지 연산자를 pop하여 출력:
* +
후위 표기식: A B C D - * +
요약
연산자 우선순위와 괄호 처리는 변환 알고리즘의 핵심입니다. 이를 통해 연산 순서가 명확한 후위 표기식을 생성할 수 있습니다.
C 코드 구현
아래는 중위 표기식을 후위 표기식으로 변환하는 C 언어 코드입니다. 이 구현에서는 스택 자료 구조를 사용하여 연산자와 괄호를 처리합니다.
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MAX 100
// 스택 구조 정의
typedef struct {
char data[MAX];
int top;
} Stack;
// 스택 초기화
void initStack(Stack *s) {
s->top = -1;
}
// 스택 비어있는지 확인
int isEmpty(Stack *s) {
return s->top == -1;
}
// 스택 가득 찼는지 확인
int isFull(Stack *s) {
return s->top == MAX - 1;
}
// 스택에 push
void push(Stack *s, char c) {
if (!isFull(s)) {
s->data[++(s->top)] = c;
} else {
printf("Stack Overflow\n");
}
}
// 스택에서 pop
char pop(Stack *s) {
if (!isEmpty(s)) {
return s->data[(s->top)--];
} else {
printf("Stack Underflow\n");
return '\0';
}
}
// 스택의 최상단 값 반환
char peek(Stack *s) {
return s->data[s->top];
}
// 연산자 우선순위 반환
int precedence(char op) {
switch (op) {
case '+': case '-': return 1;
case '*': case '/': return 2;
case '(': return 0;
default: return -1;
}
}
// 중위 표기식 -> 후위 표기식 변환 함수
void infixToPostfix(char *infix, char *postfix) {
Stack s;
initStack(&s);
int i, k = 0;
for (i = 0; infix[i] != '\0'; i++) {
char c = infix[i];
// 피연산자는 결과 문자열에 추가
if (isalnum(c)) {
postfix[k++] = c;
}
// 여는 괄호는 스택에 push
else if (c == '(') {
push(&s, c);
}
// 닫는 괄호는 괄호 내부의 연산자를 pop
else if (c == ')') {
while (!isEmpty(&s) && peek(&s) != '(') {
postfix[k++] = pop(&s);
}
pop(&s); // 여는 괄호 제거
}
// 연산자는 우선순위에 따라 스택에 push/pop
else {
while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(c)) {
postfix[k++] = pop(&s);
}
push(&s, c);
}
}
// 남은 연산자를 결과 문자열에 추가
while (!isEmpty(&s)) {
postfix[k++] = pop(&s);
}
postfix[k] = '\0'; // 결과 문자열 종료
}
int main() {
char infix[MAX], postfix[MAX];
printf("Enter an infix expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
return 0;
}코드 설명
- 스택 구현: 연산자와 괄호를 관리하기 위해 스택을 사용합니다.
- 피연산자 처리: 알파벳이나 숫자는 즉시 결과 배열에 추가됩니다.
- 괄호 처리: 여는 괄호는 push, 닫는 괄호는 괄호 내부의 연산자를 pop합니다.
- 연산자 처리: 우선순위를 비교하여 적절히 스택에 push하거나 pop합니다.
- 결과 출력: 변환된 후위 표기식을 출력합니다.
이 코드는 중위 표기식을 후위 표기식으로 변환하는 데 필요한 모든 기능을 포함하고 있습니다.
예제와 코드 실행 결과
예제 입력
중위 표기식:
A+B*(C-D)변환 과정
- 입력 문자
A: 피연산자 → 출력:A - 입력 문자
+: 연산자 → 스택에 push - 입력 문자
B: 피연산자 → 출력:A B - 입력 문자
*: 연산자, 우선순위가+보다 높음 → 스택에 push - 입력 문자
(: 여는 괄호 → 스택에 push - 입력 문자
C: 피연산자 → 출력:A B C - 입력 문자
-: 연산자 → 스택에 push - 입력 문자
D: 피연산자 → 출력:A B C D - 입력 문자
): 닫는 괄호 →-를 pop하여 출력, 괄호 제거 - 남은 스택 연산자 pop:
*와+를 차례로 출력
결과 후위 표기식:
A B C D - * +코드 실행 결과
프로그램 실행 후 입력된 중위 표기식에 따라 후위 표기식이 출력됩니다.
입력:
Enter an infix expression: A+B*(C-D)출력:
Postfix expression: ABCD-*+다른 예제
- 중위 표기식:
(A+B)*C-D
후위 표기식:AB+C*D- - 중위 표기식:
A*B+C/D
후위 표기식:AB*CD/+
코드 실행의 의미
이 예제와 실행 결과를 통해 변환 알고리즘의 정확성을 검증할 수 있습니다. 다양한 입력 데이터를 사용해 변환 과정을 연습하면 후위 표기식 생성 과정을 명확히 이해할 수 있습니다.
자주 발생하는 오류와 디버깅 팁
오류 1: 우선순위 처리의 실수
- 문제: 연산자의 우선순위를 잘못 처리해 잘못된 후위 표기식이 생성될 수 있습니다.
- 해결 방법:
- 우선순위 테이블(예:
+와-는 1,*와/는 2)을 정확히 정의합니다. - 스택에서 pop하는 조건을
스택의 최상단 연산자 우선순위 >= 현재 연산자로 정확히 설정합니다.
디버깅 예제
중위 표기식: A+B*C
- 잘못된 후위 표기식:
A+B*C+ - 올바른 후위 표기식:
A B C * +
오류 2: 괄호 처리 누락
- 문제: 여는 괄호
(를 스택에 push하지 않거나, 닫는 괄호)처리 시 스택에서 모든 연산자를 pop하지 않는 경우. - 해결 방법:
- 여는 괄호는 무조건 push합니다.
- 닫는 괄호를 만나면 여는 괄호를 만날 때까지 모든 연산자를 pop하고 출력합니다.
디버깅 예제
중위 표기식: A*(B+C)
- 잘못된 후위 표기식:
A B C + - 올바른 후위 표기식:
A B C + *
오류 3: 스택 오버플로우 및 언더플로우
- 문제: 스택이 가득 찼을 때 push를 시도하거나, 빈 스택에서 pop을 시도하면 프로그램이 예외를 발생시킬 수 있습니다.
- 해결 방법:
- 스택 연산 전에
isFull()또는isEmpty()를 확인합니다. - 충분한 크기의 스택을 정의하고 테스트 데이터 크기를 제한합니다.
디버깅 예제
중위 표기식: A+B*C-D/E+F (너무 많은 연산자)
- 수정 전: 스택 오버플로우 발생
- 수정 후: 스택 크기를 늘리고 예외 처리를 추가
오류 4: 결과 문자열 누락
- 문제: 스택에 남아 있는 연산자를 pop하지 않고 변환을 종료하면 후위 표기식이 불완전하게 생성됩니다.
- 해결 방법:
변환이 끝난 후, 스택에 남아 있는 연산자를 모두 pop하고 결과 문자열에 추가합니다.
디버깅 예제
중위 표기식: A+B*C
- 잘못된 후위 표기식:
A B C - 올바른 후위 표기식:
A B C * +
오류 5: 잘못된 입력 처리
- 문제: 예상하지 못한 입력(예: 잘못된 연산자, 연속된 피연산자 등)을 처리하지 못하는 경우.
- 해결 방법:
- 입력을 읽기 전에 유효성 검사를 수행합니다.
- 예상하지 못한 문자가 들어오면 에러 메시지를 출력하거나 무시합니다.
디버깅 팁 요약
- 작은 테스트 케이스부터 시작하여 알고리즘이 올바르게 작동하는지 확인합니다.
- 디버깅 로그를 추가하여 스택 상태와 결과 문자열을 단계별로 출력합니다.
- 다양한 유형의 입력(연산자, 괄호, 잘못된 문자 등)을 사용해 알고리즘의 안정성을 검증합니다.
정확하고 안정적인 변환 알고리즘을 구현하려면, 위와 같은 일반적인 오류를 사전에 대비하고 디버깅 팁을 적극 활용하세요.
연습 문제와 추가 과제
연습 문제
- 중위 표기식을 후위 표기식으로 변환하기
다음 중위 표기식을 후위 표기식으로 변환하세요. A+B*C(A+B)*(C-D)A*B+C/D-E((A+B)*C-(D-E))*(F+G)- 코드 실행 결과 예상하기
아래 중위 표기식을 코드에 입력했을 때 출력될 후위 표기식을 예상해보세요.
A+(B*C-(D/E^F)*G)*H- 우선순위 변경 실험
연산자의 우선순위를 변경하여 아래의 중위 표기식 결과가 달라지도록 실험해 보세요.
A+B*C-D추가 과제
- 코드 확장하기
- 추가 연산자(
^연산 등)를 처리하도록 변환 알고리즘을 확장하세요. - 연산 우선순위와 결합법칙(Associativity)을 고려한 구현을 추가하세요.
- 후위 표기식 계산기 구현
변환된 후위 표기식을 입력으로 받아 계산 결과를 출력하는 프로그램을 작성하세요. 예를 들어, 후위 표기식6 2 + 5 * 8 4 / -를 입력하면 결과38을 출력하도록 구현합니다. - 잘못된 입력 검증
- 변환 알고리즘에 잘못된 입력 처리 기능을 추가하세요.
- 예: 괄호가 일치하지 않거나, 연산자와 피연산자 순서가 잘못된 경우.
- 속도 및 효율성 분석
- 다양한 크기의 입력 데이터에 대해 알고리즘의 실행 속도를 측정하세요.
- 알고리즘의 시간 복잡도와 공간 복잡도를 분석하고, 최적화 방안을 제안하세요.
심화 실습
- 후위 표기식뿐만 아니라 전위 표기식(Prefix Notation)으로도 변환해 보세요.
- C++이나 Python으로 변환 프로그램을 재구현하여 언어 간 차이를 비교해 보세요.
위 연습 문제와 과제를 통해 중위 표기식 변환 알고리즘의 작동 원리와 구현 능력을 심화할 수 있습니다.
요약
중위 표기식을 후위 표기식으로 변환하는 과정은 스택 자료 구조와 연산자 우선순위, 괄호 처리를 활용하여 연산 순서를 명확히 만드는 알고리즘입니다. 본 기사에서는 중위 표기식과 후위 표기식의 개념, 변환 알고리즘, C 코드 구현, 예제와 디버깅 팁까지 다루었습니다. 이를 통해 변환 원리를 이해하고, 실제 프로그램을 작성하며 실습할 수 있는 기초를 제공했습니다. 추가 연습 문제와 과제를 통해 이 주제에 대한 응용력을 키울 수 있습니다.