Chapter #18

/*18-1 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다.
•	push X: 정수 X를 스택에 넣는 연산이다.
•	pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
•	size: 스택에 들어있는 정수의 개수를 출력한다.
•	empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
•	top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.*/

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <string.h>

int arr[10001]; 
int cnt = -1; 

void push(int x) { //push함수입니다.
	arr[++cnt] = x; //배열에서의 크기를 증가시키고 그 위치에 입력한 값을 넣습니다.
}

void pop() { //pop함수입니다.
	if (cnt < 0) //스택내부에 값이 존재하지 않으면
		return printf("-1\n"); //-1을 출력합니다.
	int a = arr[cnt]; //가장위의 값을 따로 저장하고
	arr[cnt--] = 0; //그 값을 없앱니다.
	return printf("%d\n", a); //뺀 값을 출력합니다.
}

void size() { //스택의 크기를 출력하는 함수입니다.
	return printf("%d\n", cnt + 1); //스택의 크기인 cnt + 1를 출력합니다.
}

void empty() { //스택이 비어있는지 확인하는 함수입니다.
	if (cnt < 0) return printf("1\n"); //비어있으면 1을
	else return printf("0\n"); //아니면 0을 출력합니다.
}

void top() { //스택의 가장 위의 값을 출력하는 함수입니다.
	if (top < 0) return printf("-1\n"); //스택이 비어있으면 -1을 출력합니다.
	else return printf("%d\n", arr[cnt]); //아니면 가장 위의 값을 출력합니다.
}

int main() {
	int N, i;
	scanf("%d", &N); //명령어를 입력할 횟수를 직접 입력합니다.
	char order[10]; //명령어가 들어갈 배열입니다.
	for (i = 0; i < N; i++) { 
		scanf("%s", order); //명령어를 입력합니다.
		if (!strcmp(order, "push")) { //문자열 비교를 통해 각각의 명령어를 실행합니다.
			int x;
			scanf("%d", &x);
			push(x);
		}
		else if (!strcmp(order, "pop")) pop();
		else if (!strcmp(order, "size")) size();
		else if (!strcmp(order, "empty")) empty();
		else if (!strcmp(order, "top")) top();
	}
	return 0;
}

//Stack을 써서 문자열 비교를 통해 주어진 명령어를 실행하는 프로그램입니다.
![image](https://user-images.githubusercontent.com/80377779/119973983-1aa45b80-bfef-11eb-92c0-39351daf5407.png)

/*18-2 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)
이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.
정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.*/

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <string.h>

typedef struct _stack {
	int arr[100000];
	int cnt;
}Stack; //구조체 Stack입니다.

void Push(Stack* s, int data) { //data값을 Stack에 집어넣는 push함수입니다.
	s->arr[(s->cnt)++] = data; //배열안에 data값을 넣고 cnt를 증가시킵니다.
}
void Pop(Stack* s) { //stack에서 가장 윗값을 빼는 pop함수입니다.
	if ((s->cnt) != 0) (s->cnt)--; //stack이 비어있지않다면 cnt값을 감소시킵니다.
}
int Sum(Stack s) { //stack내부의 원소들의 총합을 나타내는 sum함수입니다.
	int sum = 0; //sum을 0으로 초기화하고
	for (int i = 0; i < s.cnt; i++) { //반복문을 통해
		sum += s.arr[i]; //stack내부의 원소를 모두 sum에 더해 넣습니다.
	}
	return sum; //sum값을 리턴합니다.
}

int main() {
	int k, num;
	Stack stack;
	stack.cnt = 0; //stack의 초기화입니다.

	scanf("%d", &k); //입력할 수의 개수를 적접 정합니다.
	for (int i = 0; i < k; i++) {
		scanf("%d", &num); //num을 입력해
		if (num == 0) Pop(&stack); //0이라면 pop을 실행하고,
		else Push(&stack, num); //아니라면 stack에 push해줍니다.
	}
	printf("%d\n", Sum(stack)); //stack에 남아있는 원소들을 sum함수를 통해 출력합니다.

//stack을 이용해 입력한 수를 집어넣고 빼기를 반복해 남아있는 원소들의 총합을 출력하는 프로그램입니다.
![image](https://user-images.githubusercontent.com/80377779/119974017-2859e100-bfef-11eb-9a8d-5bcf88ebfdfe.png)

/*18-3 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 
그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 
만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 
예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 
판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 
데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 
출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.*/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

char stack[101] = { 0, };
int top = -1;

void init_stack() { //스택 초기화 함수입니다.
    for (int i = 0; i < 101; i++) {
        stack[i] = 0;
    }
    top = -1;
}

void push(char data) {
    top++;
    stack[top] = data;
}

int pop(char data) {
    if (top > -1) { //stack내부에 값이 존재하면,
        if (stack[top] == '(' && data == ')') { //괄호의 짝이 맞으면,
            stack[top] = 0;
            top--; //pop하고
            return 1; //1을 리턴합니다.
        }
        else return 0; //짝이 맞지않으면 0을 리턴합니다.
    }
    else return 0; //stack이 비어있어도 0을 리턴합니다.
}

int main(void) {
    while (1) { //원하는만큼 반복합니다.
        int result = 0;
        char arr[101] = { 0, };
        fgets(arr, sizeof(arr), stdin); //문자열을 입력하는 fgets함수입니다.

        for (int i = 0; i < strlen(arr); i++) { //문자열 탐색하면서 괄호 나오는지 확인할 루프
            if (arr[i] == '(') { //괄호가 시작하면
                push(arr[i]); //그 괄호를 stack에 집어넣습니다.
            }
            else if (arr[i] == ')') { //끝나는 괄호가 있다면
                if (pop(arr[i]) == 0) { //top에 있는 괄호와 입력받은 괄호가 다르면
                    result++; //틀린문장입니다.
                }
            }
        }
        if (top == -1 && result == 0) { //괄호를 모두 검사하고 틀린문장이 아니라면
            printf("YES\n"); //YES를 출력합니다.
        }
        if (top != -1 || result != 0) { //stack내부에 값이 여전히 존재하거나(괄호의 짝이 없는경우), 틀린문장이라고 결정되면
            printf("NO\n"); //NO를 출력합니다.
        }
        init_stack(); //스택을 초기화합니다.
    }

    return 0;
}

//stack을 이용해 괄호의 짝이 맞으면 YES를, 아니면 NO를 출력하는 프로그램입니다.
![image](https://user-images.githubusercontent.com/80377779/119974113-432c5580-bfef-11eb-9bea-a8d2e287b0e1.png)

/*18-4 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <String.h>

#define MAX_STACK_SIZE 100 //스택의 최대 크기
typedef char element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;

// 스택 초기화 함수
void init_stack(StackType* s) {
	s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType* s) {
	return (s->top == -1);
}

// 포화 상태 검출 함수
int is_full(StackType* s) {
	return (s->top == (MAX_STACK_SIZE - 1));
}

// 삽입 함수
void push(StackType* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
	}
	else
		return s->data[++(s->top)] = item;
}

// 삭제 함수
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return s->data[(s->top)--];
}

int check_matching(const char* in) {
	StackType s;
	char ch, open_ch;
	int i, n = strlen(in);
	init_stack(&s);

	for (i = 0; i < n; i++) {
		ch = in[i];
		switch (ch) {
		case'(': case'{': case'[':
			push(&s, ch);
			break;
		case')': case'}': case']':
			if (is_empty(&s)) {
				return 0;
			}
			else {
				open_ch = pop(&s);
				if ((open_ch == '(' && ch != ')') || (open_ch == '{' && ch != '}') 
|| (open_ch == '[' && ch != ']')) {
					return 0;
				}
				break;
			}

		}
	}
	if (!is_empty(&s))
		return 0;
	return 1;
}

int main(void) {
	char* check = malloc(sizeof(char) * 100);
	scanf("%s", check);

	if (check_matching(check) == 1) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;
}

/*사용자에게 문자열을 입력 받고 괄호 검사 프로그램인 check_matching 함수를 이용해서 괄호의 균형이 맞으면 Yes, 
균형이 맞지 않으면 No를 출력하는 프로그램이다. logic은 문자열을 검사 하는데 괄호만 검사하는 형식이다. 
여는 괄호가 있으면 스택에 push를 하고 닫는괄호가 있으면 스택에서 하나를 pop해서 짝이 맞는지 확인하고 짝이 맞지 않으면 0을 return한다. 
이런 logic으로 문자열 끝까지 반복했는데 return 0;이 발생하지 않으면 괄호의 짝이 맞다는 의미이므로 return 1을 해준다.*/
![image](https://user-images.githubusercontent.com/80377779/119974171-56d7bc00-bfef-11eb-8aaa-2bc6791c2051.png)

/*18-5 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 
스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 
임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 
이를 계산하는 프로그램을 작성하라. 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 
불가능한 경우 NO를 출력한다.*/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int n, sti = 0, opi = 0, num = 0; //num은 0부터 n-1까지의 수입니다.
	int stack[100000] = { 0 }; //스택의 빈 자리는 0으로 표시
	char output[200001] = { 0 }; //사용 여부를 체크하는 배열, 출력할 결과를 저장하는 배열
	scanf("%d", &n); 
	while (n > 0) { //입력한 수인 n이 0보다 큰 동안 반복합니다.
		int temp;
		scanf("%d", &temp); //수를 입력합니다.
		if (stack[sti] == temp) { //그 수가 stack의 가장 위에 있으면
			stack[sti--] = 0; //그 위치에 0을 넣고 pop합니다.
			output[opi++] = '-'; //pop이므로 '-'를 넣어줍니다.
		}
		else if (stack[sti] < temp) { //스택의 가장 위의 값보다 입력한 수가 크면
			if (num + 1 > temp) { //입력한 수가 n보다 작으면 
				printf("NO"); //스택에는 n보다 큰 수를 넣을 수없으므로 NO를 출력합니다.
				return 0;
			}
			while (num + 1 <= temp) { //그게 아니라면
				output[opi++] = '+'; //입력한 수에 닿을 때까지 push해야하므로 '+'를 넣어줍니다.
				if (stack[sti] == 0) stack[sti] = num + 1; //스택의 가장 위의 값이 0인것은 그 자리에 위치한 값이 이미 빠진것이므로 그 다음 값을 넣어줍니다.
				else stack[++sti] = num + 1; //값이 빠진게 아니라면 오름차순으로 더해줍니다.
				num++;
			}
			stack[sti--] = 0; //push가 끝나면 값을 출력해야하므로 pop해줍니다.
			output[opi++] = '-'; //pop이므로 '-'를 넣어줍니다.
		}
		else { //위 조건들을 만족하지않으면
			printf("NO"); //NO를 출력합니다.
			return 0;
		}
		n--;
	}
	while (n < opi) printf("%c\n", output[n++]); //output에 저장된 값을을 순서대로 출력해줍니다.
}

//오름차순으로 정리된 스택에서 입력한 수열을 만들기위해 어떻게 push와 pop을 해야하는지 출력하는 프로그램입니다.
![image](https://user-images.githubusercontent.com/80377779/119974280-6c4ce600-bfef-11eb-912e-5287c20f9c4e.png)

/*18-6 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다.
Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.*/

#define _CRT_SECURE_NO_WARNINGS

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

#define MAX_STACK_SIZE 100

typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1;

int is_empty() {
	return (top == -1);
}

int is_full() {
	return (top == (MAX_STACK_SIZE - 1));
}

void push(element item) {
	if (is_full()) {
		fprintf(stderr, "스택 포화 에러\n");
	}
	else
		stack[++top] = item;
}

element pop() {
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return stack[top--];
}

//스택에 넣읗 값 정하는 함수
int find(int n, int* array, int size) {
	int max = array[n];

	for (int j = n+1; j < size; j++) { //max보다 큰 값이 있는지 확인
		if (max < array[j]) {
			return array[j];
		}
	}
	return -1; // max보다 큰 값이 없으면 -1 반환
}

int main(void) {
	int size, num;
	int i;
	scanf("%d", &size);

	int* array = malloc(sizeof(int) * size);
	for (i = 0; i < size; i++) {
		scanf("%d", &num);
		array[i] = num;
	}
	
	// 사용자가 입력한 수들을 반복문을 이용하여 오큰수 or -1을 스택에 push하기
	for (int j = 0; j < size; j++) {
		push(find(j, array, size));
	}
	
	// stack의 0번 index부터 출력하기 
	for (i = 0; i < size; i++) {
		printf("%2d", stack[i]);
	}
	return 0;
}

/*사용자가 입력한 수를 배열에 저장한 다음 오큰수를 찾는 함수를 이용하여 오큰수가 있으면 오큰수를 스택에 push하고 
오큰수가 없으면 -1을 push하여서 stack의 0번 index부터 size만큼 출력하는 프로그램이다.*/
![image](https://user-images.githubusercontent.com/80377779/119974362-825aa680-bfef-11eb-9175-9871a7be914f.png)