[알고리즘] 기본 추상자료형(4) - 예제(스택ADT)

[문제1] 스택ADT를 배열로 구현하고 테스트하는 프로그램

- push(stack, value) : stack의 top에 데이터를 추가한다

- pop(stack) : stack의 top에 있는 데이터를 반환하고 stack에서 제거한다

- peek(stack) : stack의 top에 있는 데이터를 화면에 출력한다

- duplicate(stack) : stack의 top에 있는 데이터를 pop해서 두번 push한다

- upRotate(stack, number) : stack의 맨 위의 number개의 데이터를 회전시킨다. 예를들어 n이 5이면 top에서 1,2,3,4,5로 저장되어 있다면 2,3,4,5,1로 변경

- downRotate(stack, number) : stack의 맨 위의 number개의 데이터를 회전시킨다. 예를들어 n이 5이면 top에서 1,2,3,4,5로 저장되어 있다면 5,1,2,3,4로 변경

- print(stack) : stack의 모든 데이터를 top에서부터 순서대로 출력

입력예시               출력예시

4 10 POP PUSH A PUSH B PUSH C PUSH D PRINT UpR 3 PRINT PUSH E PEEK

Stack Empty DCBA CBDA Stack FULL C

#include<stdio.h> #include<stdlib.h> #include<string.h> int stackSize, top; void push(char *stack, char value){ if (top >= stackSize - 1){ printf("Stack FULL\n"); return; } stack[++(top)] = value; } char pop(char *stack){ if (top <= -1){ printf("Stack Empty\n"); return; } return stack[(top)--]; } void peek(char *stack){ if (top <= -1){ printf("Stack Empty\n"); return; } printf("%c\n", stack[top]); } void duplicate(char *stack){ if (top >= stackSize){ printf("Stack FULL\n"); return; } push(stack,pop(stack)); push(stack,stack[top]); } void upRotate(char *stack, int number){ char *tempArray = (char*)malloc(sizeof(char)*number); if (number > (top + 1)) { free(tempArray); return; } for (int i = 0; i < number; i++) { tempArray[i] = pop(stack); } push(stack, tempArray[0]); for (int i = number - 1; i > 0; i--) { push(stack, tempArray[i]); } free(tempArray); } void downRotate(char *stack, int number){ char *tempArray = (char*)malloc(sizeof(char)*number); if (number > (top + 1)) { free(tempArray); return; } for (int i = 0; i < number; i++) { tempArray[i] = pop(stack); } for (int i = number - 2; i > -1; i--) { push(stack, tempArray[i]); } push(stack, tempArray[number - 1]); free(tempArray); } void print(char *stack){ for (int i = (top); i > -1; i--){ printf("%c", stack[i]); } printf("\n"); } void main(){ int calculateSize, number; char *stack, calculate[10], value; scanf("%d", &stackSize); stack = (char*)malloc(sizeof(char)*stackSize); top = -1; scanf("%d", &calculateSize); getchar(); for (int i = 0; i < calculateSize; i++){ scanf("%s", calculate); getchar(); if (strcmp(calculate, "PUSH") == 0){ scanf("%c", &value); getchar(); push(stack, value); } else if (strcmp(calculate, "POP") == 0){ pop(stack); } else if (strcmp(calculate, "PEEK") == 0){ peek(stack); } else if (strcmp(calculate, "DUP") == 0){ duplicate(stack); } else if (strcmp(calculate, "UpR") == 0){ scanf("%d", &number); getchar(); upRotate(stack, number); } else if (strcmp(calculate, "DownR") == 0){ scanf("%d", &number); getchar(); downRotate(stack, number); } else if (strcmp(calculate, "PRINT") == 0){ print(stack); } } free(stack); }

[문제2] 한줄의 수식문장을 입력받고, 그 문장의 괄호 짝 유효성 검사를 하는 프로그램(심볼균형 프로그램)

입력예시                                             출력예시

(3+40*(2+(30-7)*2133)	Wrong_5
3*{4+(2-792)/1} + [3*{4-2* (100 -7)}]	OK_10

#include<stdio.h> #include<stdlib.h> #include<string.h> char *stack; int top; char pop() { if (top <= -1) { printf("Stack Empty\n"); return; } return stack[(top)--]; } void push(char value) { if (top >= 1000 - 1) { printf("Stack FULL\n"); return; } stack[++(top)] = value; } int isEmpty() { if ((top) == -1) { return 1; } else { return 0; } } int isBalanced(char *sentence) { char popItem; for (int i = 0; i < strlen(sentence); i++) { if ((sentence[i] == '(') || (sentence[i] == '{') || (sentence[i] == '[')) { push(sentence[i]); } else if ((sentence[i] == ')') || (sentence[i] == '}') || (sentence[i] == ']')) { if (isEmpty()) { return 0; } popItem = pop(); if (sentence[i] == ')') { if (popItem != '(') { return 0; } } else if (sentence[i] == '{') { if (popItem != '}') { return 0; } } else if (sentence[i] == '[') { if (popItem != ']') { return 0; } } } } return isEmpty(); } void main() { int count = 0; char *sentence = (char*)malloc(sizeof(char) * 1000); stack = (char*)malloc(sizeof(char) * 1000); top = -1; gets(sentence); for (int i = 0; i < strlen(sentence); i++) { if ((sentence[i] == '(') || (sentence[i] == '{') || (sentence[i] == '[') || (sentence[i] == ')') || (sentence[i] == '}') || (sentence[i] == ']')) { count++; } } if (isBalanced(sentence) == 1) { printf("OK_%d", count); } else { printf("Wrong_%d", count); } free(sentence); free(stack); }