Chap6. Stack

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void StackInit(Stack * pstack);
// 스택의 초기화 진행, 스택 생성 후 제일 먼저 호출되어야 함

int SIsEmpty(Stack * pstack);
// 스택인 빈 경우 TRUE, 그렇지 않으면 FALSE 

void SPush(Stack * pstack, Data data);
// 스택에 데이터를 저장, 매개변수 data로 전달된 값을 저장

Data SPop(Stack * pstack);
// 마지막에 저장된 요소를 반환하고 삭제
// 본 함수 호출을 위해 데이터가 하나 이상 존재함이 보장되어야 함 => SIsEmpty 사용

Data SPeek(Stack * pstack);
// 마지막 저장요소를 반환하되 삭제하지 않음
// 본 함수 호출을 위해 데이터가 하나 이상 존재함이 보장되어야 함 => SIsEmpty 사용

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

void StackInit(Stack * pstack)
{
	pstack->topIndex = -1; // 01은 빈 스택 의미
}

int SIsEmpty(Stack * pstack)
{
	if(pstack->topIndex == -1)  // 빈 경우 TRUE
		return TRUE;
	else
		return FALSE;
}

void SPush(Stack * pstack, Data data)
{
	pstack->topIndex += 1;  // -1이 초기값이므로 먼저 증가해야 함
	pstack->stackArr[pstack->topIndex] = data;
}

Data SPop(Stack * pstack)
// 배열에서 삭제 의미 : 값이 있어도 유효한 값으로 인정받지 못하면 삭제 된 것
// 어차피 Push되면 새 데이터로 초기화 되므로 미리 초기화 필요 X
{
	int rIdx;

	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	rIdx = pstack->topIndex;    // 삭제 될 인덱스 저장
	pstack->topIndex -= 1;

	return pstack->stackArr[rIdx];
}

Data SPeek(Stack * pstack)
{
	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->stackArr[pstack->topIndex];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

// 새 노드를 머리에 추가하고 삭제시 머리부터 삭제하는 단순 연결 리스트와 비슷
void StackInit(Stack * pstack)
{
	pstack->head = NULL;  
}

int SIsEmpty(Stack * pstack)
{
	if(pstack->head == NULL)
		return TRUE;
	else
		return FALSE;
}

void SPush(Stack * pstack, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));

	newNode->data = data;
	newNode->next = pstack->head;

	pstack->head = newNode;
}

Data SPop(Stack * pstack)
{
	Data rdata;
	Node * rnode;

	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}

	rdata = pstack->head->data;   // 데이터 백업
	rnode = pstack->head;

	pstack->head = pstack->head->next;   // 데이터 헤드 앞당김
	free(rnode);     // 삭제

	return rdata;
}

Data SPeek(Stack * pstack)
{
	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->head->data;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

// 하나의 함수가 너무 많은 일을 할때 이를 나누는 함수도 큰 의미
// Helper 1
int GetOpPrec(char op)   // 연산 우선순위 반환
{
	switch(op)    // 값이 클 수록 우선순위 높음
	{
	case '*':
	case '/':
		return 5;
	case '+':
	case '-':
		return 3;
	case '(':       // 연산자가 등장 할 때 까지 남아있어야 하므로 가장 낮은 우선순위
		return 1;
	}
// ) 연산자는 소괄호의 끝을 알이므로 쟁반으로 가지 않아서 정의 X

	return -1;   // 등록되지 않은 연산자
}

// Helper 2
int WhoPrecOp(char op1, char op2)   // 두 연산자 우선순위 비교 결과 반환
{
	int op1Prec = GetOpPrec(op1);
	int op2Prec = GetOpPrec(op2);

	if(op1Prec > op2Prec)
		return 1;
	else if(op1Prec < op2Prec)
		return -1;
	else
		return 0;
}

void ConvToRPNExp(char exp[])
{
	Stack stack;
	int expLen = strlen(exp);
	char * convExp = (char*)malloc(expLen+1);  // 변환된 수식을 담을 공간 마련

	int i, idx=0;
	char tok, popOp;
	
	memset(convExp, 0, sizeof(char)*expLen+1);   // 공간 0으로 초기화
	StackInit(&stack);

	for(i=0; i<expLen; i++)   // 한 문자씩 처리
	{
		tok = exp[i];
		if(isdigit(tok))    // 피연산자라면 자리잡기
		{
			convExp[idx++] = tok;
		}
		else                // 연산자라면 stack
		{
			switch(tok)       // stack 순위처리
			{
			case '(':          // 새로운 바닥이므로 무조건 push
				SPush(&stack, tok);
				break;

			case ')':         // 닫는 소괄호는 과정 진행
				while(1)
				{   
					popOp = SPop(&stack);    // 스택에서 연산자를 꺼내서
					if(popOp == '(')         // ( 을 만날 때까지
						break;
					convExp[idx++] = popOp;      // 배열에 저장
				}
				break;

			case '+': case '-': 
			case '*': case '/':    // tok에 저장된 연산자를 스택에 저장
				while(!SIsEmpty(&stack) && WhoPrecOp(SPeek(&stack), tok) >= 0)
					convExp[idx++] = SPop(&stack);

				SPush(&stack, tok);
				break;
			}
		}
	}

	while(!SIsEmpty(&stack))
		convExp[idx++] = SPop(&stack);  // 남은 연산자 모두 이동

	strcpy(exp, convExp);    // 연환된 수식 반환
	free(convExp);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

int EvalRPNExp(char exp[])
{
	Stack stack;
	int expLen = strlen(exp);    // 문자의 수
	int i;
	char tok, op1, op2;

	StackInit(&stack);

	for(i=0; i<expLen; i++)
	{
		tok = exp[i];

		if(isdigit(tok))           // 피연산자라면
		{
			SPush(&stack, tok - '0');     // char를 숫자로 변환하여 PUSH!
		}
		else           // 연산자라면
		{
			op2 = SPop(&stack);     // 먼저 꺼낸 값이 두 번째 피연산자!
			op1 = SPop(&stack);

			switch(tok)
			{
			case '+':
				SPush(&stack, op1+op2);
				break;
			case '-':
				SPush(&stack, op1-op2);
				break;
			case '*':
				SPush(&stack, op1*op2);
				break;
			case '/':
				SPush(&stack, op1/op2);
				break;
			}
		}
	}   // 최종 결과는 stack에 있음
	return SPop(&stack);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int EvalInfixExp(char exp[])
{
	int len = strlen(exp);
	int ret;
	char * expcpy = (char*)malloc(len+1);     // 문자열 저장 공간 마련
	strcpy(expcpy, exp);                 // 원본 유지를 위한 복사본 생성

	ConvToRPNExp(expcpy);       // 후위 표기법으로 수식 변환
	ret = EvalRPNExp(expcpy);   // 후위 표기법 계산

	free(expcpy);          // 복사한 저장공간 해제
	return ret;
}