반응형
4.4 스택의 응용: 괄호 검사 문제
괄호는 항상 쌍이 되게끔 사용하여야 한다. 대괄호 [ ], 중괄호 { }. 소괄호 ( ) 등이다.
조건1: 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
조건2: 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
조건3: 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다.
왼쪽 괄호들을 스택에 쌓다가 오른쪽 괄호가 나오면 스택의 최상단부터 괄호가 매칭되는지 검사한다.
괄호짝이 맞는지(조건 3 위배), 스택이 비어 있지는 않는지(조건 1, 조건2 위배), 마지막 괄호까지 처리했는데
스택이 비어있지 않은 지(조건1 위배)를 체크해 준다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
typedef char element;
typedef struct{
element *data;
int capacity;
int top;
}StackType;
void init_stack(StackType *s){
s->top=-1;
s->capacity = 1;
s->data=(element*)malloc(s->capacity*sizeof(element));
}
int is_empty(StackType *s){
if(s->top == -1){
return 1;
}
else return 0;
}
int is_full(StackType *s){
if(s->top == (s->capacity-1)){
return 1;
}
else return 0;
}
void push(StackType *s,element item){
if(is_full(s)){
s->capacity *=2;
s->data =(element*)realloc(s->data,s->capacity*(sizeof(element)));
}
s->top ++;
s->data[s->top]=item;
}
element pop(StackType *s){
if(is_empty(s)){
fprintf(stderr,"스택 빔");
exit(1);
}
return s ->data[(s->top)--];
}
/*괄호짝이 맞는지(조건 3 위배), 스택이 비어 있지는 않는지(조건 1, 조건2 위배), 마지막 괄호까지 처리했는데
스택이 비어있지 않은 지(조건1 위배)를 체크해 준다.*/
int check_matching(const char *in)
{
StackType *s;
s=(StackType*)malloc(sizeof(StackType));
init_stack(s);
int length = strlen(in);
char left, right;
for(int i=0;i<length; i++){
left = in[i];
switch(left){
case '(': case '{': case '[':
push(s,left);
break;
case ')': case '}': case ']':
if(is_empty(s)){ //스택이 비어있진 않은가
free(s);
return 0;
}
else{
right = pop(s);
if((right==')' && left !='(')||
(right=='}'&& left !='{')||
(right==']'&& left !='[')){
free(s);
return 0; // 짝이 안맞진 않은가
}
break;
}
}
}
if(!is_empty(s)) {
free(s);
return 0; //오른쪽 괄호가 다 나왔는데 스택이 남아있는가
}
free(s);
return 1;
}
int main(){
char *p= "{A[(i+1]=0;}";
if(check_matching(p)==1){
printf("%s 괄호검사성공\n",p);
}
else{
printf("%s 괄호검사실패\n",p);
}
}♠ 123p Quiz
01 'empty ' → { → { ( → { → { [ → { → 'empty '
02 'empty ' → { → { [ → { [ (→ { [ → { → 'empty '
4.5 스택의 응용: 후위 표기 수식의 계산
수식을 표기하는 방법에는 중위(infix), 후위(postfix), 전위(prefix)의 3가지 방법이 있다.
중위 : 연산자가 피연산자 사이에 위치 ( 2 + 3 * 4 )
후위 : 연산자가 피연산자 뒤에 위치 ( 2 3 4 * + )
전위 : 연산자가 피연산자 앞에 위치 ( + 2 * 3 4 )
● 컴파일러에서 후위 표기 방법을 선호하는 이유
- 먼저 계산해야할 부분을 나타내기 위해서 괄호를 사용할 필요가 없다.
ex) (1+2)*7은 괄호 없이 후위 표기법을 사용할 시 12+7*가 된다.
- 식 자체에 우선순위를 표시하기 때문에 연산자의 우선순위를 고려할 필요가 없다.
- 위와 같은 이유로 식 전체를 읽고 계산할 필요없이 수식을 읽으면서 바로 계산을 할 수 있다.
피연산자를 스택에 담으면서 연산자를 만나면 필요한 피연산자를 스택에서 꺼낸 후 연산 결과를 다시 스택에 담는다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
typedef char element;
typedef struct{
element *data;
int capacity;
int top;
}StackType;
void init_stack(StackType *s){
s->top=-1;
s->capacity = 1;
s->data=(element*)malloc(s->capacity*sizeof(element));
}
int is_empty(StackType *s){
if(s->top == -1){
return 1;
}
else return 0;
}
int is_full(StackType *s){
if(s->top == (s->capacity-1)){
return 1;
}
else return 0;
}
void push(StackType *s,element item){
if(is_full(s)){
s->capacity *=2;
s->data =(element*)realloc(s->data,s->capacity*(sizeof(element)));
}
s->top ++;
s->data[s->top]=item;
printf("%d ",s->data[s->top]); // 오류 디버깅용
}
element pop(StackType *s){
if(is_empty(s)){
fprintf(stderr,"스택 빔");
exit(1);
}
return s ->data[(s->top)--];
}
int eval(char exp[]){
int length = strlen(exp);
char ch;
StackType *s;
s=(StackType*)malloc(sizeof(StackType));
init_stack(s);
int value, op1, op2;
for(int i=0; i<length; i++){
ch = exp[i];
if(ch != '+' && ch != '-' && ch != '*' && ch != '/'){
value = ch - '0';
push(s,value);
}
else{
op2 = pop(s);
op1 = pop(s); // op1이랑 op2를 바꿔서 pop에 넣었다가 나누기에서 몫이 틀리는
// 오류를 발생시켰다. 스택의 pop을 잘 체크하자
switch(ch){
case '+': push(s,op1+op2); break;
case '-': push(s,op1-op2); break;
case '*': push(s,op1*op2); break;
case '/': push(s,op1/op2); break;
}
}
}
return pop(s);
}
int main(){
printf("후위 표기식은 82/3-32*+\n");
printf("결과값은 %d\n",eval("82/3-32*+"));
return 0;
}● 중위표기수식을 후위표기수식으로 변환
- 피연산자는 바로 후위표기수식에 출력
- 연산자는 스택에 저장. 단 연산자의 우선순위를 고려하여 스택 사용하기
- 스택에 존재하는 연산자A가 그 다음으로 만난 연산자B보다 우선순위가 높다면 : A를 스택에서 꺼낸 후 B를 넣음.
- 우선순위가 같을 때도 스택 상단의 요소를 먼저 꺼내어 출력 후 그 다음 연산자를 스택에 넣기
- 괄호가 있을 땐 왼쪽 괄호는 무조건 스택 삽입, 오른쪽 괄호를 만날 때까지 연산자를 스택에 삽입한 후
오른쪽 괄호를 만나면 그 사이에 있는 모든 연산자들을 출력
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
typedef char element;
typedef struct{
element *data;
int capacity;
int top;
}StackType;
void init_stack(StackType *s){
s->top=-1;
s->capacity = 1;
s->data=(element*)malloc(s->capacity*sizeof(element));
}
int is_empty(StackType *s){
if(s->top == -1){
return 1;
}
else return 0;
}
int is_full(StackType *s){
if(s->top == (s->capacity-1)){
return 1;
}
else return 0;
}
void push(StackType *s,element item){
if(is_full(s)){
s->capacity *=2;
s->data =(element*)realloc(s->data,s->capacity*(sizeof(element)));
}
s->top ++;
s->data[s->top]=item;
}
element pop(StackType *s){
if(is_empty(s)){
fprintf(stderr,"스택 빔");
exit(1);
}
return s ->data[(s->top)--];
}
int prec(char op){
switch(op){
case '(': case ')' : return 0;
case '+': case '-' : return 1;
case '*': case '/' : return 2;
}
return -1;
}
void infix_to_postfix(char exp[]){
char ch,top_op;
StackType *s;
s=(StackType *)malloc(sizeof(StackType));
init_stack(s);
int length = strlen(exp);
for(int i=0; i<length; i++){
ch = exp[i];
switch(ch){
case '+': case '-': case '*': case'/':
while(prec(ch)<=prec(s->data[s->top]) && !is_empty(s)){
printf("%c",pop(s));
}
push(s,ch);
break;
case '(':
push(s,ch);
break;
case ')':
top_op=pop(s);
while(top_op !='('){
printf("%c", top_op);
top_op=pop(s);
}
break;
default:
printf("%c",ch);
break;
}
}
while(!is_empty(s)){
printf("%c",pop(s));
}
free(s);
}
int main(){
char *s = "(2+3)*4+9";
printf("중위표시수식 %s\n", s);
printf("후위표시수식 ");
infix_to_postfix(s);
printf("\n");
return 0;
}♠ 135p Quiz
01 'empty stack' → * → * ( → * ( + → * → * % → * → 'empty stack'
5 10 2 + 2 % *
4.6 스택의 응용: 미로 문제
- 생쥐가 지나갈 수 있는 길은 배열의 값을 0, 지나갈 수 없는 벽은 배열의 값을 1로 하는 이차원 배열
- 시작포인트, 즉 입구부터 출구까지 생쥐가 지나가는데 한칸에서 그 다음 칸으로 넘어갈 때 그 칸을 기준으로
상하좌우 네 칸을 모두 확인하여 값이 0이면 스택에 쌓는다.
- 이미 지나온 길은 배열의 값을 .으로 바꾸는데, 특정 칸에서 주변 네 칸을 검사했을 때 값이 0인 칸이 없다면
스택에 저장된 다른 좌표로 이동한다. '
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAZE_SIZE 6
typedef struct{
short r;
short c;
}element;
typedef struct{
element *data;
int capacity;
int top;
}StackType;
void init_stack(StackType *s){
s->top=-1;
s->capacity = 1;
s->data=(element*)malloc(s->capacity*sizeof(element));
}
int is_empty(StackType *s){
if(s->top == -1){
return 1;
}
else return 0;
}
int is_full(StackType *s){
if(s->top == (s->capacity-1)){
return 1;
}
else return 0;
}
void push(StackType *s,element item){
if(is_full(s)){
s->capacity *=2;
s->data =(element*)realloc(s->data,s->capacity*(sizeof(element)));
}
s->top ++;
s->data[s->top]=item;
}
element pop(StackType *s){
if(is_empty(s)){
fprintf(stderr,"스택 빔");
exit(1);
}
return s ->data[(s->top)--];
}
element here = {1,0}, entry = {1,0};
char maze[MAZE_SIZE][MAZE_SIZE] = {
{'1','1','1','1','1','1'},
{'e','0','1','0','0','1'},
{'1','0','0','0','1','1'},
{'1','0','1','0','1','1'},
{'1','0','1','0','0','x'},
{'1','1','1','1','1','1'},
};
void push_loc(StackType *s, int r, int c){
if(r<0||c<0) return;
if(maze[r][c] != '1' && maze[r][c]!='.'){
element tmp;
tmp.r=r;
tmp.c=c;
push(s,tmp);
}
}
void maze_print(char maze[MAZE_SIZE][MAZE_SIZE]){
printf("\n");
for(int r=0;r<MAZE_SIZE;r++){
for(int c=0;c<MAZE_SIZE;c++){
printf("%c", maze[r][c]);
}
printf("\n");
}
}
int main(){
int r,c;
StackType *s;
s=(StackType*)malloc(sizeof(StackType));
init_stack(s);
here = entry;
while(maze[here.r][here.c]!='x'){
r=here.r;
c=here.c;
maze[r][c]='.';
maze_print(maze);
push_loc(s,r-1,c);
push_loc(s,r+1,c);
push_loc(s,r,c-1);
push_loc(s,r,c+1);
if(is_empty(s)){
printf("실패\n");
return 0;
}
else here=pop(s);
}
printf("성공\n");
return 0;
}'CS > Data Structure' 카테고리의 다른 글
| [C언어로 쉽게 풀어쓴 자료구조] Chapter5. 큐 (1) (0) | 2023.10.28 |
|---|---|
| [C언어로 쉽게 풀어쓴 자료구조] 연습문제 4강 (1) | 2023.10.27 |
| [C언어로 쉽게 풀어쓴 자료구조] Chapter4. 스택 (1) (1) | 2023.10.22 |
| [C언어로 쉽게 풀어쓴 자료구조] 연습문제 3강 (0) | 2023.10.21 |
| [C언어로 쉽게 풀어쓴 자료구조] 연습문제 2강 (0) | 2023.10.21 |
