스택(Stack)은 선형 자료구조의 한 종류로, 데이터를 한쪽 끝(top)에서만 삽입하고 삭제할 수 있는 구조입니다. 이러한 특성 덕분에 스택은 LIFO(Last In First Out, 후입선출) 방식으로 동작하며, 수식의 변환과 평가에 매우 유용하게 활용됩니다.
스택 기본 연산 알고리즘
Push( ) – 데이터 삽입
먼저 스택 오버플로우(stack overflow) 발생 여부를 확인합니다.
if (top == n-1)
printf("stack over flow");
오버플로우가 아니라면 요소를 스택에 삽입합니다.
top++; a[top] = item;
Pop( ) – 데이터 삭제
먼저 스택 언더플로우(stack underflow) 발생 여부를 확인합니다.
if (top == -1)
printf("stack under flow");
언더플로우가 아니라면 스택에서 요소를 삭제합니다.
item = a[top]; top--;
Display( ) – 전체 출력
스택이 비어 있는지 먼저 확인합니다.
if (top == -1)
printf("stack is empty");
비어 있지 않다면 아래와 같이 모든 요소를 출력합니다.
for (i = 0; i <= top; i++)
printf("%d", a[i]);
스택의 활용: 표현식(Expression) 변환
표현식(Expression)이란 피연산자(operand)와 연산자(operator)가 문법적으로 올바르게 결합된 형태를 의미합니다.
표현식의 세 가지 유형
C 언어에서는 다음 세 가지 표기법의 표현식에 대해 변환과 평가를 수행할 수 있습니다.
- 중위 표기법(Infix) – 연산자가 피연산자 사이에 위치합니다. 예: A+B
- 전위 표기법(Prefix) – 연산자가 피연산자 앞에 위치합니다. 예: +AB
- 후위 표기법(Postfix) – 연산자가 피연산자 뒤에 위치합니다. 예: AB+
중위 → 후위 / 중위 → 전위 변환 예시
중위 → 후위 중위 → 전위 A + B*C A + B*C A + BC* A + *BC ABC*+ +A*BC
복합 수식 변환 예제
수식 A+B*C / D-E+F를 후위 표기법과 전위 표기법으로 각각 변환해 보겠습니다.
중위 → 전위 중위 → 후위 A +B*C / D-E+F A +B*C / D-E+F A +*BC / D-E+F A +BC* / D-E+F A +/*BCD -E+F A +BC*D /-E+F +A /*BCD -E +F ABC*D /+ -E+F -+A/*BCDE +F ABC*D/ +E- +F +-+A/*BCDEF ABC*D/+E-F+
중위 → 후위 변환 알고리즘
입력 문자열을 왼쪽에서 오른쪽으로 스캔하면서 아래 단계를 순서대로 수행합니다.
- 1단계 – 입력 기호가 피연산자라면 화면에 그대로 출력합니다.
- 2단계 – 입력 기호가 '(' (여는 괄호)라면 스택에 push 합니다.
- 3단계 – 입력 기호가 ')' (닫는 괄호)라면 '(' 를 만날 때까지 스택의 모든 내용을 pop 하여 출력합니다.
- 4단계 – 입력 기호가 연산자라면, 스택 최상단(top)에 있는 연산자의 우선순위와 현재 입력 기호의 우선순위를 비교합니다.
스택 top의 우선순위가 현재 기호보다 크거나 같으면 스택의 내용을 pop 한 뒤, 현재 기호를 스택에 push 합니다. 그렇지 않으면 해당 연산자를 그대로 스택에 push 합니다. - 5단계 – 입력 기호가 '\0'(문자열의 끝)이라면 스택이 빌 때까지 남은 모든 내용을 pop 하여 출력합니다.
이 알고리즘을 적용하면 괄호와 연산자 우선순위를 고려하여 중위 표기법의 수식을 오류 없이 후위 표기법으로 변환할 수 있으며, 컴파일러가 실제 수식을 처리하는 방식과도 동일한 원리입니다.