[C언어로 쉽게 풀어쓴 자료구조] Chapter4. 스택 (2)

4.4 스택의 응용: 괄호 검사 문제
4.5 스택의 응용: 후위 표기 수식의 계산
4.6 스택의 응용: 미로 문제

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

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

[C언어로 쉽게 풀어쓴 자료구조] Chapter4. 스택 (2)

4.4 스택의 응용: 괄호 검사 문제

4.5 스택의 응용: 후위 표기 수식의 계산

4.6 스택의 응용: 미로 문제

'CS > Data Structure' 카테고리의 다른 글

4.4 스택의 응용: 괄호 검사 문제

4.5 스택의 응용: 후위 표기 수식의 계산

4.6 스택의 응용: 미로 문제

'CS > Data Structure' 카테고리의 다른 글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역