자료구조 공부#10 (수식의 계산)

 

2021.03.27 - [이론공부/자료구조] - 자료구조 공부#9 (스택)

이전 내용을 참고합시당

---

수식의 표기 방법

전위, 중위, 후위

중위 표기법	전위 표기법	후위 표기법
2+3*4	+2*34	234*+
a*b+5	+*ab5	ab*5+
(1+2)*7	*+127	12+7*

 

컴퓨터에서 수식 계산 순서

• 중위 표기식 -> 후위 표기식 -> 계산
• 2+3*4 -> 234* -> 14
• 모두 스택을 사용함

 

우리의 시점(고급언어)에서는 중위표기식이 익숙하지만 컴퓨터의 시점(저급언어)로 가게 되면 후위표기로 해석하기가 편하다.

 

 

후위 표기식의 계산

수식을 왼쪽에서 오른쪽으로 스캔하여 피연산자면 스택에 저장, 연산자면 필요한수만큼 피연산자를 스택에서 꺼내 연산을 실행하고 연산 결과를 다시 스택에 저장.

 

8,2를 먼저 스택에 넣고, /를 연산하여 4의 결과값을 넣고 3을 넣어 - 연산을 계산.... 이런식..

 

중위 표기법 : (8/2-3)+3*2

 

스택에 값을 먼저 넣고, 그 다음 연산자를 넣어 연산후 나온 결과값을 다시 스택에 넣는 구조.

 

간단한 일부분 연산 순서의 스택 예시 그림

이전 스택 알고리즘에 이어지는 연산 함수 C 코드 예제

 

int eval(char exp[]){
	int op, op2, value, i = 0;
    int len = strlen(exp);
    char ch;
    StackType s;
    
    init_stack(&s);
    
    for(i=0;i<len;i++){
    	ch = exp[i];
        if (ch != '+' && ch != '-' && ch != '*' && ch != '/'){
        
    		value = ch - "0"; // 입력이 피연산자인 경우
        	push(&s, value);
    	}
    	else{ //입력이 연산자이면 피연산자를 스택에서 제거
    		op2 = pop(&s);
    	    op1 = pop(&s);
        	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); 
}

 

중위 표기식 -> 후위 표기식 방법

• 중위 표기법과 후위표기법의 공통점은 피연산자의 순서는 동일하다는 점이다.
• 연산자들의 순서만 다르므로 연산자만 스택에 저장했다가, 출력하면 된다.

중위 표기법	후위 표기법
a+b	ab+
(a+b)*c	ab+c*
a+b*c	abc*+

 

2번쨰의 경우 괄호로 인해 먼저 연산해야 하므로 후위 표기법에서도 ab+로 먼저 표기하구 후에 *연산을 표기한다.

 

괄호를 포함한 후위표기식 변환 알고리즘

 

---

 

스택 응용(미로 탐색)

현재의 위치에서 가능한 방향을 스택에 저장해 놓았다가 막다른길을 만나면 스택에서 다음 탐색 위치를 꺼내고 다시 탐색

 

 

알고리즘 이해 이미지

 

C로 구현한 코드 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STACK_SIZE 100 
#define MAZE_SIZE 6


// 현재 위치 구조체
typedef struct {
	short r;
	short c;
} element;

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'}
};

// 저장되는 스택 구조체
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화
void init_stack(StackType* s) {
	s->top = -1;
}

// 스택 공백여부
int is_empty(StackType* s) {
	return (s->top == -1);
}
// 스택 포화여부
int is_full(StackType* s) {
	return (s->top == (MAX_STACK_SIZE - 1));
}
//스택 push
void push(StackType* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화됨\n");
		return;
	}
	else s->data[++(s->top)] = item;
}
//스택 pop
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 비어있음\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}

//mov esp? 맨위에 스택값 가져오기 pop은 안함
element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 오류\n");
		exit(1);
	}
	else return s->data[s->top];
}



void push_loc(StackType* s, int r, int c) {
	if (r < 0 || c < 0) return;
	// 미로 벽이거나, 지나간곳 여부 판단 (벽은 1 지나간곳은 m)
	if (maze[r][c] != '1' && maze[r][c] !='m') {
		element trail;
		trail.r = r;
		trail.c = c;
		// 스택 최상단에 저장 (r,c)위치
		push(s, trail);

	}
}

// 미로 배열 받아서 출력 하는 함수
void miro_print(char miro[MAZE_SIZE][MAZE_SIZE]) {
	printf("\n");
	// 미로 크기 만큼 반복
	for (int r = 0; r < MAZE_SIZE; r++) {
		//미로 열 입력
		for (int c = 0; c < MAZE_SIZE; c++) {
			printf("%c", miro[r][c]);
		}
		// 행 넘기기
		printf("\n");
	}
}


int main(void) {
	int r, c;
	StackType s;
	init_stack(&s);
	here = entry; //현재 위치에 시작 위치값 삽임
	
	// 목표지점 'x'에 도달할때 까지 반복
	while (maze[here.r][here.c] != 'x')
	{
		r = here.r, c = here.c;
		maze[r][c] = 'm';
		miro_print(maze);

		// 범위 상하좌우 1 만큼 탐색
		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에 저장
			here = pop(&s);
	}
	printf("성공\n");
	return 0;

}

 

---

느낀점 : 후위표기법이 스택 구조랑 잘맞아서 컴퓨터 연산에 선호되는 느낌이다.
후위 표기법은 괄호가 없어도 계산 순서를 쉽게 알수 있고, 순서에 맞추어 계산할 수 있는 장점이 있는 듯 하다.