자료구조 (연결 스택)

---

참고자료

 

https://jung-story.tistory.com/23?category=826491 

자료구조 (순차 스택)

 

---

개요

 

스택에 대해서는 순차로 구현하는 방식과 연결로 구현 하는 방식이 있는데

이번에는 연결로 구현 하는 스택에 대해서 알아보겠습니다.

 

#include <stdio.h>
#include <stdlib.h>
//typedef int element; // 스택 원소(element)의 자료형을 int로정의
typedef char element;
typedef struct StackNode {
	element data;
	struct StackNode* link;
}StackNode;
StackNode* top;
int isEmpty() {
	if (top == NULL) {
		return 1;
	}
	else {
		return 0;
	}
}
void push(element item) {
	StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
	temp->data = item;	// 새로운 heap공간에 temp라는 걸 만들어주고 temp가 가리키는 data는 element의 
	temp->link = top;	// 삽입 노드를 top의 위에 연결	//temp가 가리키는게 메인에서 처음에는 NULL;
	top = temp;		// top 위치를 삽입노드로 이동	NULL이였던 top의값이 temp로 바뀌게됩니다.
						// 그러므로 계속 삽입할때마다 temp의 값은 그 위에 쌓은top의 값으로 계속 바뀌게 됩니다.
}
element pop() {
	element item;
	StackNode* temp = top;

	if (isEmpty()) {
		printf("\n 스택이 비어있습니다..");
		return 0;
	}
	else {
		item = temp->data;		// top이가지고 있는 data를 item에 저장
		top = temp->link;		    // top 이 가지고있는 data와link를 temp->link 에 대입한다.
		free(temp);					// 삭제된 노드의 메모리 반환
		return item;					// 삭제된 원소 반환
	}
}
void printStack() {
	StackNode* p = top;
	while (p) {
		printf("[%d] ,", p->data);	// top이가지고 있는 data;
		p = p->link;		// p는 다음 거를 가리켜 주기위해 p = p->link를 사용
	}
	printf("\n");
}

int testPair(char* exp) {
	char symbol, open_pair;
	int i, length = strlen(exp);
	top = NULL;

	for (i = 0; i < length; i++) {
		symbol = exp[i];
		switch (symbol) {
			// (1) 왼쪽 괄호는 스택에 삽입!
		case '(':
		case '[':
		case '{':
			push(symbol); break;
		case ')':
		case ']':
		case '}':
			if (isEmpty()) {
				return 0;
			}
			else {
				//(2)-1 스택에서 마지막으로 읽은 괄호를 꺼냄
				open_pair = pop();
				// (2)-2 괄호 쌍이 맞는지 검사
				if ((open_pair == '(' && symbol != ')') || (open_pair == '[' && symbol != ']') || (open_pair == '{' && symbol != '}'))
					// (2)-3 괄호 쌍이 틀리면 수식오류
					return 0;
				// (2)-4 괄호 쌍이 맞으면 다음 symbol 검사를 계속함
				else break;
			}
		}
	}
	if (top == NULL) return 1;
	else return 0;
}


int main() {
	element item;


	char* express = "{(A+B)-3}*5+[{cos(x+y)+7}-1}*4";
	printf("%s", express);
	if (testPair(express) == 1) {
		printf("\n\n 수식의 괄호가 맞게 사용되었습니다.");
	}
	else {
		printf("\n\n수식의 괄호가 틀렸습니다.");
	}
	return 0;
}

 

 

실행화면

실행화면