Stack

스택
스택(Stack)은 한쪽으로 들어가서 한쪽으로 나오는 자료 구조(Data structure)
수직 계산 등의 알고리즘에서 다방면으로 활용된다.

PUSH: 스택에 데이터를 넣는다.
POP: 스택에서 데이터를 뺀다.
배열을 이용한 스택
메모리 공간이 다소 비효율적으로 사용됨
#include<stdio.h>
#define SIZE 10000
#define INF 99999999
int stack[size]
int top=-1;
void push(int data){
if(top==SIZE -1){
printf("스택 오버플로우가 발생했습니다.\n");
return;
}
stack[++top]=data;
}
int pop(){
if(top==-1) {
printf("스택 언더플로우가 발생했습니다.\n");
return -INF;
}
return stack[top--];
}
void show(){
printf("--- 스택의 최상단 ---\n");
for(int i=top;i>=;i--){
printf("%d\n",stack[i]);
}
printf("--- 스택의 최하단 ---\n");
}
int main(void){
push(7);
push(5);
push(4);
pop();
push(6);
pop();
system("pause");
return 0;
}
연결리스트를 이용한 스택
#include<stdio.h>
#include<stdlib.h>
#define INF 99999999
typedef struct{
int data;
struct Node *next;
}Node;
typedef struct{
Node *top;
}Stack;
void push(Stack *stack, int data){
Node *node=(Node*)malloc(sizeof(Node));
node->data=data;
node->next=stack->top;
stack->top=node;
}
int pop(Stack *stack){
if(stack->top==NULL){
printf("스택 언더플로우가 발생했습니다.\n");
return -INF;
}
NODE *node=stack->top;
int data=node->data;
stack->top=node->next;
free(node);
return data;
}
void show(Stack *stack){
Node *cur=stack->top;
printf("--- 스택의 최상단 ---\n");
while(cur!=NULL){
printf("%d\n", cur->data);
cur=cur->next;
}
printf("--- 스택의 최하단 ---");
})
int main(void){
Stack stack;
stack.top=NULL;
char a[100]="( ( 3 + 4 ) * 5 ) - 5 * 7 * 5 - 5 * 10";
int size=1;
for(int i=0;i<strlen(a);i++){
if(a[i]==' ')size++;
}
char *ptr=strtok(a, " ");
char **input=(char **)malloc(sizeof(char)*100);
for (int i=0;i<size; i++){
input[i]=(char*)malloc(sizeof(char)*100);
}
for(int i=0;i<size;i++){
input[i]=(char *)malloc(sizeof(char)*100);
}
for(int i=0;i<size;i++){
strcpy(input[i],ptr);
ptr=strtok(NULL," ");
}
char b[1000]="";
strcpy(b,transition(&stack, input, size));
printf("후위 표기법: %s\n",b);
size =1;
for(int i=0;i<strlen(b)-1;i++){
if(b[i]==' ')size++;
}
char *ptr2=strtok(b, " ");
for(int i=0;i<size;i++){
strcpy(input[i],ptr2);
ptr2=strtok(NULL, " ");
}
calculate(&stack, input, size);
system("pause");
return 0;
}
스택을 활용한 계산기
중위표기법
일반적으로 사람이 수식을 표기 할 때 사용하는 표기 방법
ex) 7*5+3
후위 표기법
컴퓨터가 계산하기에 편한 수식의 형태
연산자는 뒤쪽에 위치한다.
ex) 7 5 * 3 +
#define _CRT_SERCURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node{
char data[100];
struct Node *next;
}Node;
typedef struct Stack{
Node *top;
}Stack;
void push(Stack *stack, char *data){
Node *node=(Node*)malloc(sizeof(Node));
strcpy(node->data,data);
node->next=stack->top;
stack->top=node;
}
char *getTop(Stack *stack){
Node *top=stack->top;
return top->data;
}
char *pop(Stack *stack){
if(stack->top==NULL){
printf("스택 언더플로우가 발생했습니다.\n");
return NULL;
}
Node *node=stack->top;
char *data=(char*)malloc(sizeof(char)*100);
strcpy(data, node->data);
stack->top=node->next;
free(node);
return data;
}
//중위 표기법을 후위 표기법으로 바꾸기
int getPriority(char *i){
if(!strcmp(i, "("))return 0;
if(!strcmp(i, "+")||!strcmp(i,"-"))return 1;
if(!strcmp(i, "*")||!strcmp(i,"/"))return 2;
return 3;
}
char *transition(Stack *stack, char **s, int size){
char res[1000]="";
for(int i=0;i<size;i++){
if(!strcmp(s[i], "+")||!strcmp(s[i],"-")||!strcmp(s[i],"*")||!strcmp(s[i],"/")){
while(stack->top!=NULL&&getPriority(getTop(stack))>=getPriority(s[i])){
strcat(res,pop(stack));strcat(res, " ");
}
push(stack,s[i]);
}
else if(!strcmp(s[i], "(")) push(stack, s[i]);
else if(!strcmp(s[i], ")")){
while(strcmp(getTop(stack),"(")){
strcat(res,pop(stack));strcat(res, " ");
}
pop(stack);
}
else { strcat(res, s[i]); strcat(res, " ");}
}
while(stack->top!=NULL){
strcat(res, pop(stack)); strcat(res, " ");
}
return res;
}
void calculate(Stack *stack, char **s, int size){
int x, y, z;
for(int i=0;i<size; i++){
if(!strcmp(s[i], "+")||!strcmp(s[i], "-")||!strcmp(s[i], "*")||!strcmp(s[i],"/")){
x=atoi(pop(stack));
y=atoi(pop(stack));
if(!strcmp(s[i],"+")) z=y+x;
if(!strcmp(s[i],"-")) z=y-x;
if(!strcmp(s[i],"*")) z=y*x;
if(!strcmp(s[i],"/")) z=y/x;
char buffer[100];
sprintf(buffer, "%d", z); //sprintf는 숫자로 된 결과를 다시 문자열로 바꿔줌
push(stack, buffer);
}
else{
push(stack, s[i]);
}
}
printf("%s\n",pop(stack));
}
int main(void){
Stack stack;
stack.top=NULL;
char a[100]="( ( 3 + 4 ) * 5 ) - 5 * 7 * 5 - 5 * 10";
int size=1;
for(int i=0;i<strlen(a);i++){
if(a[i]==' ')size++;
}
char *ptr=strtok(a, " ");
char **input=(char **)malloc(sizeof(char)*100);
for (int i=0;i<size; i++){
input[i]=(char*)malloc(sizeof(char)*100);
}
for(int i=0;i<size;i++){
input[i]=(char *)malloc(sizeof(char)*100);
}
for(int i=0;i<size;i++){
strcpy(input[i],ptr);
ptr=strtok(NULL," ");
}
char b[1000]="";
strcpy(b,transition(&stack, input, size));
printf("후위 표기법: %s\n",b);
size =1;
for(int i=0;i<strlen(b)-1;i++){
if(b[i]==' ')size++;
}
char *ptr2=strtok(b, " ");
for(int i=0;i<size;i++){
strcpy(input[i],ptr2);
ptr2=strtok(NULL, " ");
}
calculate(&stack, input, size);
system("pause");
return 0;
}