- 1 -
데이터 구조 실습 (7주차)
2021. 4. 14
학번: 성명:
※ 다음과 정의된 스택을 이용하여 문제를 해결하라.
#define MAX_SIZE 20
typedef struct { // 스택 타입 정의 int data[MAX_SIZE];
int top;
} stack_type;
typedef stack_type* stack_ptr;
void init(stack_ptr s) { s->top = -1; } int is_empty(stack_type s) {
return (s.top == -1);
}
int is_full(stack_type s) {
return (s.top == (MAX_SIZE - 1));
}
void push(stack_ptr s, int val) { if (is_full(*s)) {
fprintf(stderr, "Error: stack full\n");
return;
}else
s->data[++s->top] = val;
}
int pop(stack_ptr s) { if (is_empty(*s)) {
fprintf(stderr, "Error: stack empty\n");
exit(1);
}else
return s->data[s->top--];
}
1. 단지 소괄호(‘()’)만을 포함하는 수식에서 괄호가 올바르게 사용되었는지를 검사하는 프로그램을 작성하고자 한다. 다음에 답하시오.
a. 다음은 수식 exp를 매개변수로 전달받아서 그 수식에 포함된 괄호의 사용이 올바른지를 테스트하여 그 결과를 반환하는 paren_test()의 골격을 보여준다. 이를 완성하라.
// 스택 타입 정의: 6주차 실습 참고 // 스택 함수 작성
int paren_test(char exp[]) { char ch;
int i=0;
// 스택 생성 및 초기화: 6주차 실습 참고
while ((ch = exp[i++]) != '\0') {// exp에 포함된 기호를 한 개씩 가져와서 검사/처리 // ...
} // ...
}
b. 다음은 paren_test()를 테스트하는 main()을 다음과 같이 작성하고, 테스트하라.
int main() {
char exp[] = "((()))";
if (paren_test(exp)) printf("\nBalanced");
elseprintf("\nUnbalanced");
return 0;
}
c. exp가 다음의 식일 때 각각 테스트하라.
exp = "((()) (( )))"
exp = "((((()“
- 2 -
2. 1)에서 작성한 paren_test()를 수정하여 수식에 포함된 괄호의 번호를 다음과 같이 출력하도록 하라. 왼쪽 괄호가 나올 때마다 괄호 번호가 하나씩 증가한다. 오른쪽 괄호가 나오면 매칭되는 왼쪽 괄호 번호를 출력한다. 즉,
프로그램 결과는 다음과 같다.
exp = "((()) (( )))“
출력: 1 2 3 3 2 4 5 5 4 1 => Balanced
exp = "((((()“
출력: 1 2 3 4 5 5 => Unbalanced
3. 회문(palindrome)이란 앞뒤 어느 쪽에서 읽어도 같은 단어를 의미한다. 예를 들면, ”eye“, ”madam“은 회문이다. 스택을 이용하여 주어진 문자열이 회문인지 아닌지를 결정하는 프로그램을 작성하고자 한다.
여기서는 문제 단순화를 위해서 문자열에 구두점이나 공백을 포함하지 않는다고 가정한다. 다음에 답하시오.
a. 문자열 str을 매개변수로 전달받아서, str이 회문인지를 판단하여 그 결과(회문이면 1, 그렇지 않으면 0)를 반환하는 is_palindrome()을 작성하라.
b. 문자열 str을 다음과 같이 선언 및 초기화하고서, a)에서 작성한 is_palindrome()에 전달하여 회문 여부에 따라서 다음과 같이 출력하는 main()을 작성하고, 테스트하라.
str 출력
madam madam is palindrome
abcdecba abcdecba is NOT palindrome palindrome palindrome is NOT palindrome
