저번 시간에는 전역 변수 또는 포인터와 구조체를 활용해 스택을 구현하는 방법에 대해서 살펴보았다.
이번 시간에는 구현한 스택으로 어떤 것을 할 수 있을지 알아볼 예정이다.
저저번 시간에 스택은 괄호의 유효성 검사, 후위 표기식의 계산, 그리고 회문 검사 등에 사용될 수 있다고 하였다.
기억이 잘 나지 않는다면 아래의 글을 읽으면서 다시 복습해도 좋다.
출처- 2022.11.14 - [수업내용정리/자료구조] - [자료구조][C언어] 스택이란?_스택의 개념(1)
[자료구조][C언어]스택이란?_스택의 개념(1)
스택이란? Stack, 즉 쌓아놓은 더미이다 스택은 왜 사용하는 것일까?? 다른 구조에 비해 단순하여 구현이 쉽고, 트리나 그래프 등의 다른 자료구조의 연산에서도 종종 사용되기 때문이다. 또한 괄
all4null.tistory.com
먼저 괄호가 유효한지 판별하는 알고리즘에 대해 알아보도록 하겠다.
스택의 활용1_괄호의 유효성 검사
우리는 스택을 활용해서 괄호가 유효한지 판별할 수 있다.
괄호는 먼저 대괄호[], 중괄호{}, 소괄호() 3가지가 있다.
괄호가 유효한지 판별하기 위해서는 제일 안에 들어있는 괄호인 소괄호부터 판별해 주어야 한다.
이때, 스택을 활용하면 쉽게 해결이 가능하다.
괄호의 조건
괄호가 유효하기 위한 조건으로는 여는 괄호의 개수와 닫는 괄호의 개수가 같아야 하며,
같은 괄호에서 여는 괄호는 닫는 괄호보다 먼저 나와야 하며,
괄호 사이에는 포함관계만 존재한다.
괄호 사이에는 오로지 포함관계만 존재해야 한다는 것이 잘 이해가 되지 않았다.
그래서 이러한 조건의 의미는, 괄호 사이에는 짝을 이룬 괄호만 있어야 한다고 이해를 했다.
{ ( ) } 이런 식으로 말이다. { ( } ) 이런 것은 되지 않는다는 말이다.
알고리즘 작동 방식
(1) 먼저 스택에는 여는 괄호만 입력을 받을 것이다.
(2) 입력에 만약 닫는 괄호가 나온다면 그때 스택의 최상단과 비교해서 쌍을 이룬다면
해당하는 괄호를 스택에서 꺼내 줄 것이다.
그렇지 않다면 그 괄호는 성립하지 않을 것이다.
ex) { ( }
(3) 입력이 모두 끝난 후 스택이 비어있으면 괄호는 성립, 그렇지 않으면 괄호는 성립하지 않는다.
이해가 잘 되지 않는다면 위 과정을 아래 그림으로 이해해보자.
if( ( i != 0 ) && ( j == 1 ) 를 예시로 들어볼 것이다.
1. 여는 괄호" ( " 가 나왔으므로 스택에 넣어준다.
2. 여는 괄호" ( " 가 나왔으므로 스택에 넣어준다.
3-1. 닫는 괄호 " ) " 가 나왔으므로 스택의 최상단에 있는 값과 비교한다.
3-2. 괄호의 종류가 일치하므로 스택의 최상단의 값을 제거한다.
4. 여는 괄호" ( " 가 나왔으므로 스택에 넣어준다.
5-1. 닫는 괄호 " ) " 가 나왔으므로 스택의 최상단에 있는 값과 비교한다.
5-2. 괄호의 종류가 일치하므로 스택의 최상단의 값을 제거한다.
식에 더 이상 괄호가 없으나 스택에 괄호가 남아있으므로 위 괄호는 유효하지 않다.
if { (i != 0) && ( j == 1 ) }의 경우 아래와 같은 방식으로 동작한다.
해당 과정을 글로 자세히 설명하면 이렇게 된다.
1. 여는 괄호" { " 가 나왔으므로 스택에 넣어준다.
2. 여는 괄호" ( " 가 나왔으므로 스택에 넣어준다.
3-1. 닫는 괄호 " ) " 가 나왔으므로 스택의 최상단에 있는 값과 비교한다.
3-2. 괄호의 종류가 일치하므로 스택의 최상단의 값을 제거한다.
4. 여는 괄호" ( " 가 나왔으므로 스택에 넣어준다.
5-1. 닫는 괄호 " ) " 가 나왔으므로 스택의 최상단에 있는 값과 비교한다.
5-2. 괄호의 종류가 일치하므로 스택의 최상단의 값을 제거한다.
6-1. 닫는 괄호 " } " 가 나왔으므로 스택의 최상단에 있는 값과 비교한다.
6-2. 괄호의 종류가 일치하므로 스택의 최상단의 값을 제거한다.
식이 끝났고 스택에 남아있는 괄호가 더 이상 없으므로 위 식의 괄호는 유효하다.
만약에 이런 경우는 어떨까??
위처럼 스택의 괄호의 종류와 입력의 괄호의 종류가 다른 경우, 괄호가 성립하지 않게 된다.
괄호 유효성 검사 구현
위 알고리즘을 이제 C언어로 구현해볼 차례다.
저번 시간에 만들었던 코드를 가져와보자.
[자료구조][C언어]스택이란?_스택의구현(2)
저번 시간에는 스택이 무엇인지에 대해 간략하게 살펴 보았다. 스택은 맨 윗부분에서만 데이터의 삭제와 삽입이 가능한 자료구조이다. 스택의 구현 스택의 구현을 하기 위해서는 먼저 스택을
all4null.tistory.com
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define SIZE 100
typedef struct StackType{
int top;
int elem[SIZE];
}StackType;
void init(StackType *S){
S->top = -1;
}
int isFull(StackType *S){
return S->top == SIZE - 1;
}
int isEmpty(StackType *S){
return S->top == -1;
}
void push(StackType *S,int e){
S->elem[++S->top] = e;
}
int peek(StackType *S){
if(isEmpty(S)){
return -1;
}
int top = S->elem[S->top];
return top;
}
int size(StackType *S){
int size = S->top+1;
return size;
}
int pop(StackType *S){
if(isEmpty(S))
return -1;
else{
int e = S->elem[S->top--];
return e;
}
}
int main()
{
return 0;
}
스택에 숫자가 아닌 문자를 집어넣어야 하므로 char 배열로 바꿔야 하는 게 아니냐고 할 수 있지만
C언어의 문자는 기본적으로 숫자로 다루어지기 때문에 int 형 배열이어도 큰 문제는 없다.
이제 괄호가 유효한지 검사하는 check() 함수를 만들어 보자.
void check(){
StackType S;
init(&S);
char input[100];
char NoSpace[100];
printf("input: \n");
scanf("%[^\n]s", &input);
int n = strlen(input); //입력의 길이
int j = 0;
for(int i = 0; i < n; i++){
if(isspace(input[i]) == 0){
NoSpace[j++] = input[i];
}
}
n = strlen(NoSpace); //공백을 제거한 입력의 길이
for(int i = 0; i < n; i++)
{
if(NoSpace[i] == '(' || NoSpace[i] == '{' ||
NoSpace[i] == '[') // 여는 괄호인 경우
push(&S,NoSpace[i]); //스택에 넣는다
if((NoSpace[i] == ')') || (NoSpace[i] == '}') ||
(NoSpace[i] == ']')) //i번째 입력이 닫는 괄호인 경우
{
char ch = pop(&S); //스택 내의 비교할 값
if(((NoSpace[i]== ')') && (ch != '(')) ||
((NoSpace[i]== '}') && (ch != '{')) ||
((NoSpace[i]== ']') && (ch != '[')))
//입력의 닫는 괄호의 종류와
//스택 내의 최상단의 괄호의 종류가
//다르다면
{
printf("Error"); //괄호가 유효하지 않다.
return;
}
}
}
//위 과정을 거친 후
//스택이 비어있다면
if(isEmpty(&S)){
//괄호가 유효하다.
printf("Success!");
}
//스택에 괄호가 남아있다면
else{
//괄호가 유효하지않다
printf("Error");
}위의 알고리즘을 그대로 C로 작성한 결과이다.
int main()
{
check();
return 0;
}위의 코드들을 하나로 정리한 코드이다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define SIZE 100
typedef struct StackType{
int top;
int elem[SIZE];
}StackType;
void init(StackType *S){
S->top = -1;
}
int isFull(StackType *S){
return S->top == SIZE - 1;
}
int isEmpty(StackType *S){
return S->top == -1;
}
void push(StackType *S,int e){
S->elem[++S->top] = e;
}
int peek(StackType *S){
if(isEmpty(S)){
return -1;
}
int top = S->elem[S->top];
return top;
}
int size(StackType *S){
int size = S->top+1;
return size;
}
int pop(StackType *S){
if(isEmpty(S))
return -1;
else{
int e = S->elem[S->top--];
return e;
}
}
void check(){
StackType S;
init(&S);
char input[100];
char NoSpace[100];
printf("input: \n");
scanf("%[^\n]s", &input);
int n = strlen(input); //입력의 길이
int j = 0;
for(int i = 0; i < n; i++){
if(isspace(input[i]) == 0){
NoSpace[j++] = input[i];
}
}
n = strlen(NoSpace); //공백을 제거한 입력의 길이
for(int i = 0; i < n; i++)
{
if(NoSpace[i] == '(' || NoSpace[i] == '{' ||
NoSpace[i] == '[') // 여는 괄호인 경우
push(&S,NoSpace[i]); //스택에 넣는다
if((NoSpace[i] == ')') || (NoSpace[i] == '}') ||
(NoSpace[i] == ']')) //i번째 입력이 닫는 괄호인 경우
{
char ch = pop(&S); //스택 내의 비교할 값
if(((NoSpace[i]== ')') && (ch != '(')) ||
((NoSpace[i]== '}') && (ch != '{')) ||
((NoSpace[i]== ']') && (ch != '[')))
//입력의 닫는 괄호의 종류와
//스택 내의 최상단의 괄호의 종류가
//다르다면
{
printf("Error"); //괄호가 유효하지 않다.
return;
}
}
}
//위 과정을 거친 후
//스택이 비어있다면
if(isEmpty(&S)){
//괄호가 유효하다.
printf("Success!");
}
//스택에 괄호가 남아있다면
else{
//괄호가 유효하지않다
printf("Error");
}
}
int main()
{
check();
return 0;
}
'수업내용정리 > 자료구조' 카테고리의 다른 글
| [자료구조][C언어]그래프란?(1)_그래프의 개념 (0) | 2022.12.01 |
|---|---|
| [자료구조][C언어]스택이란?(5)_후위표기식 만들기 (0) | 2022.11.28 |
| [자료구조][C언어]스택이란?(4)_후위 표기식의 계산 (0) | 2022.11.18 |
| [자료구조][C언어]스택이란?_스택의구현(2) (0) | 2022.11.14 |
| [자료구조][C언어]스택이란?_스택의 개념(1) (2) | 2022.11.14 |
