스택(Stack)

스택 : 먼저 들어간 것이 나중에 나온다. 후입선출. LIFO(Last-In, First-Out)

 

ex) 배열기반 스택

ArrayBaseStack.h

#ifndef __AB_STACK_H__
#define __AB_STACK_H__

#define TRUE	1
#define FALSE	0
#define STACK_LEN	100

typedef int Data;

typedef struct _arrayStack
{
	Data stackArr[STACK_LEN];
	int topIndex;
} ArrayStack;

typedef ArrayStack Stack;

void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);

void SPush(Stack * pstack, Data data);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);

#endif

ArrayBaseStack.c

#include <stdio.h>
#include <stdlib.h>
#include "ArrayBaseStack.h"

void StackInit(Stack * pstack)
{
	pstack->topIndex = -1;
}

int SIsEmpty(Stack * pstack)
{
	if(pstack->topIndex == -1)
		return TRUE;
	else
		return FALSE;
}

void SPush(Stack * pstack, Data data)
{
	pstack->topIndex += 1;
	pstack->stackArr[pstack->topIndex] = data;
}

Data SPop(Stack * pstack)
{
	int rIdx;

	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	rIdx = pstack->topIndex;
	pstack->topIndex -= 1;

	return pstack->stackArr[rIdx];
}

Data SPeek(Stack * pstack)
{
	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->stackArr[pstack->topIndex];
}

ArrayBaseStackMain.c

#include <stdio.h>
#include "ArrayBaseStack.h"

int main(void)
{
	// Stack의 생성 및 초기화 ///////
	Stack stack;
	StackInit(&stack);

	// 데이터 넣기 ///////
	SPush(&stack, 1);  SPush(&stack, 2);
	SPush(&stack, 3);  SPush(&stack, 4);
	SPush(&stack, 5);

	// 데이터 꺼내기 ///////
	while(!SIsEmpty(&stack))
		printf("%d ", SPop(&stack)); 

	return 0;
}

 

ex) 연결 리스트 기반 스택

ListBaseStack.h

#ifndef __LB_STACK_H__
#define __LB_STACK_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _listStack
{
	Node * head;
} ListStack;


typedef ListStack Stack;

void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);

void SPush(Stack * pstack, Data data);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);

#endif

ListBaseStack.c

 

#include <stdio.h>
#include <stdlib.h>
#include "ListBaseStack.h"

void StackInit(Stack * pstack)
{
	pstack->head = NULL;
}

int SIsEmpty(Stack * pstack)
{
	if(pstack->head == NULL)
		return TRUE;
	else
		return FALSE;
}

void SPush(Stack * pstack, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));

	newNode->data = data;
	newNode->next = pstack->head;

	pstack->head = newNode;
}

Data SPop(Stack * pstack)
{
	Data rdata;
	Node * rnode;

	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}

	rdata = pstack->head->data;
	rnode = pstack->head;

	pstack->head = pstack->head->next;
	free(rnode);

	return rdata;
}

Data SPeek(Stack * pstack)
{
	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->head->data;
}

dListBaseStackMain.c

#include <stdio.h>
#include "ListBaseStack.h"

int main(void)
{
	// Stack의 생성 및 초기화 ///////
	Stack stack;
	StackInit(&stack);

	// 데이터 넣기 ///////
	SPush(&stack, 1);  SPush(&stack, 2);
	SPush(&stack, 3);  SPush(&stack, 4);
	SPush(&stack, 5);

	// 데이터 꺼내기 ///////
	while(!SIsEmpty(&stack))
		printf("%d ", SPop(&stack)); 

	return 0;
}

---

#include <ctype.h>

void * memset(void *ptr, int val, size_t len);

=> ptr로 전달된 주소의 메모리서부터 len 바이트를 val의 값으로 채운다.

 

#include <string.h>

int isdigit(int ch);

=> ch로 전달된 문자의 내용이 10진수라면 1을 반환한다.

 

수식의 표기법 : 중위(infix), 전위(prefix), 후위(postfix) 표기법

중위 표기법 ex) 5+2/7

전위 표기법 ex) +5/27

후위 표기법 ex)5 2 7/+

 

중위 표기법을 후위 표기법으로 바꾸는 방법

연산자가 나오면 쟁반에 넣고 숫자가 나오면 블록에 앞에서부터 넣는다.

연산자의 우선순위 : */ > +- > () 

쟁반에 연산자가 있는데 다른 기호가 들어온 경우

쟁반에 위치한 연산자의 우선순위가 높거나 같다면 기존 쟁반에 위치한 연산자를 꺼내서 옮기고

쟁반에 위치한 연산자의 우선순위가 낮다면 쟁반에 연산자를 쌓는다.

마지막까지 쟁반에 남아있는 연산자들은 위에서부터 꺼내서 옮긴다. 

괄호가 나오는 경우 괄호가 끝날때 모든 연산자들을 옮긴다.

 

후위 표기법으로 표현된 수식의 계산방법

앞에서부터 연산자가 나오면 바로 앞 피연산자두개와 연산을 한다.

ex) 324*+  => 38+ => 11

 

계산기

InfixCalculator.c

0.00MB

InfixCalculator.h

0.00MB

InfixCalculatorMain.c

0.00MB

InfixToPostfix.c

0.00MB

InfixToPostfix.h

0.00MB

ListBaseStack.c

0.00MB

ListBaseStack.h

0.00MB

PostCalculator.c

0.00MB

PostCalculator.h

0.00MB