선형자료구조
- 자료를 구성하는 원소들을 순차적으로 나열시킨 형태의 자료구조를 뜻한다.
- 배열(Array), 연결리스트(Linked List), 스택(Stack), 큐(Queue) 등이 있다.
목차
스택
:나중에 들어가는 원소가 가장 먼저 나오는 후입선출(LIFO:Last In First Out) 형태의 선형자료구조의 일종
스택은 함수 호출 관리, 문법 검사, 연산식 평가 등에 활용된다.
스택 연산
- push : 스택에 원소를 추가하는 연산
- pop : 스택에 원소를 삭제하는 연산
예시
| 연산 | 스택 | top |
|---|---|---|
| 초기상태 | -1 | |
| push(a) | a | 0 |
| push(b) | a b | 1 |
| push(c) | a b c | 2 |
| pop() | a b | 1 |
| push(d) | a b d | 2 |
| push(e) | a b d e | 3 |
| pop() | a b d | 2 |
| pop() | a b | 1 |
스택 구현
C언어로 스택을 구현해보자 push
push 함수는 삽인 원소를 매개 변수로 전달받아 스택이 가득 찬 상태가 아니면 top을 1 증가시킨 후 해당 위치에 원소를 저장한다.
void push(int item){
if(top>=STACK_SIZE - 1){
//top 값이 배열의 상한 경계인 STACK_SIZE - 1이면 삽입 중단
printf("스택이 꽉 찼습니다");
return;
}
stack[++top] = item;
}
pop
pop 함수는 top 포인터가 가리키고 있는 원소를 꺼내어 반환하고 top포인터를 감소 시킨다 top 포인터가 -1이면 빈 상태로 함수를 중단한다.
int pop(){
if(top<0){
printf("비어있는 스택입니다");
return -999;
}
return stack[top--];
}
수식 평가
- 수식(expression)은 연산자(operator)와 피연산자(operand)로 구성된 문장
- 연산자의 종류 : 산술연산자, 논리연산자, 대입연산자
- 피연산자는 변수 또는 상수가 될 수 있다.
- 피연산자에 대한 연산자의 위치에 따라
중위 표기법(infix),후위표기법(postfix),전위표기법(prefix)으로 나뉜다.
| 표기법 | 수식 |
|---|---|
| 중위표기법 | a / b - c + d * e - a * c |
| 후위표기법 | a b / c - d e * + a c * - |
| 전위표기법 | - + - / a b c * d e * a c |
중위표기법 vs 후위표기법
- 중위 표기법
- 수식 안에 여러 개의 연산자가 존재할 경우
👉각 연산자의 연산 순위(predence)가 높은 부분이 우선적으로 계산된다.
👉괄호를 사용하여 우선 순위를 바꿀 수 있다 - 동일 연산 순위를 갖는 연산자가 한 수식에 동시에 존재
👉결합성(associativity)규칙에 의해 연산 방향이 결정된다. - 사람이 이해하기 쉽다(intuitive for human)
- 수식 안에 여러 개의 연산자가 존재할 경우
- 후위 표기법
- 연산자의 우선 순위가 없고 괄호를 사용하지 않는다
- 왼쪽에서 오른쪽으로 계산하므로 프로그래밍이 쉽다
- 사람이 이해하기 어렵다
infix to postfix
- 사용자로부터 문자열을 입력받아
- 피연산자라면 출력하고
- 연산자인 경우 스택에 저장한다
- ’(‘라면 ‘)’가 나올때까지 무조건 스택에 추가한다
#include<stdio.h>
int priority(char op) {
switch (op) {
case '(':return 0;
case '+':return 1;case '-': return 1;
case '*':return 2;case '/':return 2;
}
}
main() {
int i = 0, token_top = -1,cnt=0;
char token,arr[101],temp, tmp[100];
//토큰, 입력받은 수식, 확인용 임시 변수, 연산자 스택
scanf("%s", arr);
while((token=arr[i++])!='\0') {
if (token >= 'A' && token <= 'Z')
printf("%c", token);
else if (token == '(')
tmp[++token_top] = token;
//push에 해당
else if (token == ')')
while ((temp = tmp[token_top--]) != '(')
printf("%c", temp);
//pop에 해당
else {
while(priority(token) <= priority(tmp[token_top]) &&token_top != -1) {
printf("%c", tmp[token_top--]);
}
tmp[++token_top] = token;
if (priority(token) > priority(tmp[token_top]) || token_top == -1)
tmp[++token_top] = token;
}
}
while (token_top > -1)
printf("%c",tmp[token_top--]);
return 0;
}
eval_postfix
- 수식을 왼쪽에서 오른쪽으로 스캔한다
- 수식에서 들어온 입력이 피연산자이면 스택에 넣는다
- 입력이 연산자이면 스택에서 피연산자 2개를 꺼내서 계산한 후 결과 값을 다시 스택에 넣는다
#include<stdio.h>
#include<string.h>
#include<math.h>
#define STACK_SIZE 10
#define EXPR_SIZE 100
int stack[STACK_SIZE];//state
char expr[EXPR_SIZE];//입력
int pos = 0;//토큰위치
char sym;//토큰
int top = -1;//빈스택
int tmp;
int realNum = 0;//변환값저장위치
int eval_postfix();//수식평가
void push(int item);
int pop();
void print_stack();
void change();//숫자 변형
int main(void) {
printf("Input a postfix expression :");
gets(expr);//입력
printf("%s\n", expr);
eval_postfix();
}
void push(int item) {
if (top >= STACK_SIZE - 1) {
printf("stack full\n");
return;
}
top += 1;
stack[top] = item;
}
int pop() {
if (top < 0) {
printf("stack empty\n");
return -999;
}
realNum--;
return stack[top--];
}
int eval_postfix() {
char sym;
int op1, op2;
sym = expr[pos++];
while (sym != '\0') {
if (sym >= '0' && sym <= '9')
push(sym - '0');
else if (sym == ' ') change();
else {
op2 = pop();
op1 = pop();
switch (sym) {
case '+': push(op1 + op2); break;
case '-': push(op1 - op2); break;
case '*': push(op1 * op2); break;
case '/': push(op1 / op2); break;
case '%': push(op1 % op2); break;
default:break;
}
print_stack();
realNum = top;
}
sym = expr[pos++];
}
return pop();
}
void change() {
int cnt = -1;
int num = 0;
tmp = top;
while (tmp-->=realNum) {
cnt++;
}
for (int i = realNum; i <= top; i++) {
num += stack[i] * pow(10, cnt--);
}
top = realNum;
stack[realNum] = num;
realNum++;
print_stack();
}
void print_stack() {
int i;
printf("[STACK] ");
for (i = 0; i <= top; i++)
printf("%6d ", stack[i]);
printf("\n");
}