파워욱의 코딩메모장

스택 계산기

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

#define MAX_ARR_LENGTH 100
typedef char element;
typedef struct StackNode
{
	element item;
	struct StackNode* link;
}StackNode;

typedef struct
{
	StackNode* top;
}LinkedStackType;

void Error(char* s)
{
	printf("---<%s>---\n", s);
}

LinkedStackType* CreateStack(void)
{
	LinkedStackType* p = (LinkedStackType*)malloc(sizeof(LinkedStackType));
	return p;
}
void InitStack(LinkedStackType* s)
{
	s->top = NULL;
}
int IsEmptyStack(LinkedStackType* s)
{
	return (s->top == NULL);
}

void Push(LinkedStackType* s, element item)
{
	StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
	if (temp == NULL)
	{
		Error("Memory allocation error!");
		return;
	}
	temp->item = item;
	temp->link = s->top;
	s->top = temp;
}

element Pop(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack Underflow");
		return -1;
	}
	StackNode* temp = s->top;
	element item = temp->item;
	s->top = s->top->link;
	free(temp);
	return item;
}
element PeekStack(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return -1;
	}
	return s->top->item;
}
void PrintStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return;
	}
	while (temp != NULL)
	{
		printf("%c\n", temp->item);
		temp = temp->link;
	}

}
void RemoveAllStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	StackNode* next;
	while (temp != NULL)
	{
		next = temp->link;
		free(temp);
		temp = next;
	}
	s->top = NULL;
}
int ComparePriority(char a, char b) {
	if (a == '*' || a == '/')
	{
		if (b == '*' || b == '/')
		{
			return 0;
		}
		else
		{
			return 1;
		}
	}
	else
	{
		if (b == '*' || b == '/')
		{
			return -1;
		}
		else
		{
			return 0;
		}
	}

}

char* GetPostfix(char* infix, int arrLen)
{
	LinkedStackType* pStack = CreateStack();
	InitStack(pStack);

	int pos = 0;
	char* postfix = (char*)malloc(sizeof(char) * MAX_ARR_LENGTH);

	//..................................
	for (int i = 0; i < arrLen - 1; i++)
	{
		if (infix[i] == '(')
		{
			Push(pStack, infix[i]);
		}
		else if(infix[i] >= '0' && infix[i] <= '9')
		{
			postfix[pos++] = infix[i];
		}
		else if (infix[i] == ')')
		{
			while (PeekStack(pStack) != '(')
			{
				postfix[pos++] = Pop(pStack);
			}
			Pop(pStack);
		}
		else
		{
			if (IsEmptyStack(pStack) || PeekStack(pStack) == '(')
			{
				Push(pStack, infix[i]);
			}
			else if (ComparePriority(infix[i],PeekStack(pStack)) > 0)
			{
				Push(pStack, infix[i]);
			}
			else
			{
				while (!(PeekStack(pStack) == '(' || IsEmptyStack(pStack)))
				{
					postfix[pos++] = Pop(pStack);
				}
				Push(pStack, infix[i]);
			}
		}
	}
	while (!IsEmptyStack(pStack))
	{
		postfix[pos++] = Pop(pStack);
	}
	postfix[pos] = '\0';


	RemoveAllStack(pStack);
	free(pStack);
	return postfix;
}

int CalculatePostfix(char* postfix)
{
	LinkedStackType* pStack = CreateStack();
	InitStack(pStack);
	int result = 0;

	while (*postfix != '\0')
	{
		
		switch (*postfix)
		{
			int temp1, temp2;
		case '+':
			temp1 = Pop(pStack);
			temp2 = Pop(pStack);
			Push(pStack, temp2 + temp1);
			break;
		case '-':
			temp1 = Pop(pStack);
			temp2 = Pop(pStack);
			Push(pStack, temp2 - temp1);
			break;
		case '*':
			temp1 = Pop(pStack);
			temp2 = Pop(pStack);
			Push(pStack, temp2 * temp1);
			break;
		case '/':
			temp1 = Pop(pStack);
			temp2 = Pop(pStack);
			Push(pStack, temp2 / temp1);
			break;
		default:
			Push(pStack, *postfix - 48);
			break;
		}
		result = PeekStack(pStack);
		postfix++;
	}


	RemoveAllStack(pStack);
	free(pStack);
	return result;
}




int main(void)
{
	/*char infix[] = { "2*3*(2+4)+9" };*/
	/*char infix[] = { "4*3*(8-4+2)" };*/
	char infix[] = { "(1+2)*(3/4)+(5+(6-7))" };
	char* postfix = GetPostfix(infix, sizeof(infix) / sizeof(char));
	printf("%s\n", postfix);
	printf("result : %d\n", CalculatePostfix(postfix));

	free(postfix);
	return 0;
}

여는 괄호나오면 무조건 집어넣기
스택이 비었거나, 탑이 여는 괄호면 들어간다. Peek 사용
닫는 괄호나오면 여는 괄호나올때까지 pop


연산자 우선순위에따라
1.높은경우 스택에 Push
2.낮거나 같은경우 스택이 다 비워질때까지 pop

연산자
(, ), +, -, *, /
우선순위 
1. *,/
2. +,-

기존스택 
같음 0
다름 1

기존스택+
다름 -1
같음 0

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

#define MAX_ARR_LENGTH 100
typedef char element;
typedef struct StackNode
{
	element item;
	struct StackNode* link;
}StackNode;

typedef struct
{
	StackNode* top;
}LinkedStackType;

void Error(char* s)
{
	printf("---<%s>---\n", s);
}

LinkedStackType* CreateStack(void)
{
	LinkedStackType* p = (LinkedStackType*)malloc(sizeof(LinkedStackType));
	return p;
}
void InitStack(LinkedStackType* s)
{
	s->top = NULL;
}
int IsEmptyStack(LinkedStackType* s)
{
	return (s->top == NULL);
}

void Push(LinkedStackType* s, element item)
{
	StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
	if (temp == NULL)
	{
		Error("Memory allocation error!");
		return;
	}
	temp->item = item;
	temp->link = s->top;
	s->top = temp;
}

element Pop(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack Underflow");
		return -1;
	}
	StackNode* temp = s->top;
	element item = temp->item;
	s->top = s->top->link;
	free(temp);
	return item;
}
element PeekStack(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return -1;
	}
	return s->top->item;
}
void PrintStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return;
	}
	while (temp != NULL)
	{
		printf("%c\n", temp->item);
		temp = temp->link;
	}

}
void RemoveAllStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	StackNode* next;
	while (temp != NULL)
	{
		next = temp->link;
		free(temp);
		temp = next;
	}
	s->top = NULL;
}
int ComparePriority(char a, char b) {
	if (a == '*' || a == '/')
	{
		if (b == '*' || b == '/')
		{
			return 0;
		}
		else
		{
			return 1;
		}
	}
	else
	{
		if (b == '*' || b == '/')
		{
			return -1;
		}
		else
		{
			return 0;
		}
	}

}

char* GetPostfix(char* infix, int arrLen)
{
	LinkedStackType* pStack = CreateStack();
	InitStack(pStack);

	int pos = 0;
	char* postfix = (char*)malloc(sizeof(char) * MAX_ARR_LENGTH);

	//..................................
	for (int i = 0; i < arrLen - 1; i++)
	{
		if (infix[i] == '(')
		{
			Push(pStack, infix[i]);
		}
		else if(infix[i] >= '0' && infix[i] <= '9')
		{
			postfix[pos++] = infix[i];
		}
		else if (infix[i] == ')')
		{
			while (PeekStack(pStack) != '(')
			{
				postfix[pos++] = Pop(pStack);
			}
			Pop(pStack);
		}
		else
		{
			if (IsEmptyStack(pStack) || PeekStack(pStack) == '(')
			{
				Push(pStack, infix[i]);
			}
			else if (ComparePriority(infix[i],PeekStack(pStack)) > 0)
			{
				Push(pStack, infix[i]);
			}
			else
			{
				while (!(PeekStack(pStack) == '(' || IsEmptyStack(pStack)))
				{
					postfix[pos++] = Pop(pStack);
				}
				Push(pStack, infix[i]);
			}
		}
	}
	while (!IsEmptyStack(pStack))
	{
		postfix[pos++] = Pop(pStack);
	}
	postfix[pos] = '\0';


	RemoveAllStack(pStack);
	free(pStack);
	return postfix;
}



int main(void)
{
	char infix[] = { "2*3*(2+4)+9" };
	char* postfix = GetPostfix(infix, sizeof(infix) / sizeof(char));
	printf("%s\n", postfix);

	free(postfix);
	return 0;
}

DoubleLinkedList

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

typedef int element;
typedef struct DlistNode
{
	element data;
	struct DlistNode* lLink;
	struct DlistNode* rLink;

}DlistNode;

void DInsertNode(DlistNode* before, DlistNode* newNode)
{
	newNode->lLink = before;
	newNode->rLink = before->rLink;
	if (before->rLink != NULL)
	{
		before->rLink->lLink = newNode;
	}
	before->rLink = newNode;

}
void DRemoveNode(DlistNode* removed)
{
	removed->lLink->rLink = removed->rLink;
	if (removed->rLink != NULL)
	{
		removed->rLink->lLink = removed->lLink;
	}

}
void DRemoveAll(DlistNode* pHead)
{
	DlistNode* pNode = pHead->rLink;
	pHead->rLink = NULL;
	while (1)
	{
		if (pNode == NULL)
		{
			break;
		}
		DlistNode* pNext = pNode->rLink;
		free(pNode);
		pNode = pNext;
	}
}

DlistNode* DSearch(DlistNode* pHead, element x)
{
	DlistNode* p = pHead;
	while (p != NULL)
	{
		if (p->data == x)
		{
			return p;
		}
		p = p->rLink;
	}
	return p;
}
void DDisplay(DlistNode* pHead)
{
	DlistNode* p = pHead;
	while (p != NULL)
	{
		printf("%d->", p->data);
		p = p->rLink;
	}
	printf("\n");
}

int main(void)
{
	DlistNode head = { 0,NULL,NULL };
	DlistNode* before = &head;
	DlistNode* pNode;
	for (int i = 1; i < 11; i++)
	{
		pNode = (DlistNode*)malloc(sizeof(DlistNode));
		pNode->data = i * 10;
		DInsertNode(before, pNode);
		before = pNode;
	}
	DDisplay(&head);

	pNode = (DlistNode*)malloc(sizeof(DlistNode));
	pNode->data = 35;
	DInsertNode(DSearch(&head, 30), pNode);
	DDisplay(&head);
	
	pNode = DSearch(&head, 50);
	DRemoveNode(pNode);
	DDisplay(&head);

	DRemoveAll(&head);
	DDisplay(&head);

	return 0;
}

Stack

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

#define MAX_STACK_SIZE 100
typedef int element;
typedef struct StackNode
{
	element item;
	struct StackNode* link;
}StackNode;

typedef struct
{
	StackNode* top;
}LinkedStackType;

void Error(char* s)
{
	printf("---<%s>---\n", s);
}

LinkedStackType* CreateStack(void)
{
	LinkedStackType* p = (LinkedStackType*)malloc(sizeof(LinkedStackType));
	return p;
}
void InitStack(LinkedStackType* s)
{
	s->top = NULL;
}
int IsEmptyStack(LinkedStackType* s)
{
	return (s->top == NULL);
}

void Push(LinkedStackType* s, element item)
{
	StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
	if(temp == NULL)
	{
		Error("Memory allocation error!");
		return;
	}
	temp->item = item;
	temp->link = s->top;
	s->top = temp;
}

element Pop(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack Underflow");
		return -1;
	}
	StackNode* temp = s->top;
	element item = temp->item;
	s->top = s->top->link;
	free(temp);
	return item;
}
element PeekStack(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return -1;
	}
	return s->top->item;
}
void PrintStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return;
	}
	while (temp != NULL)
	{
		printf("%d\n", temp->item);
		temp = temp->link;
	}

}
void RemoveAllStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	StackNode* next;
	while (temp != NULL)
	{
		next = temp->link;
		free(temp);
		temp = next;
	}
	s->top = NULL;
}




int main(void)
{
	LinkedStackType* pStack = CreateStack();
	InitStack(pStack);

	Push(pStack, 10);
	Push(pStack, 20);
	Push(pStack, 30);
	Push(pStack, 40);
	Push(pStack, 50);
	PrintStack(pStack);

	printf("Pop() : %d\n", Pop(pStack));
	PrintStack(pStack);

	printf("Pop() : %d\n", Pop(pStack));
	printf("Pop() : %d\n", Pop(pStack));
	printf("Pop() : %d\n", Pop(pStack));
	printf("Pop() : %d\n", Pop(pStack));
	printf("Pop() : %d\n", Pop(pStack));
	PrintStack(pStack);

	Push(pStack, 10);
	Push(pStack, 20);
	Push(pStack, 30);
	Push(pStack, 40);
	Push(pStack, 50);
	PrintStack(pStack);

	RemoveAllStack(pStack);
	PrintStack(pStack);

	free(pStack);



	return 0;
}

Stack 과제

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

#define MAX_STACK_SIZE 100
typedef char element;
typedef struct StackNode
{
	element item;
	struct StackNode* link;
}StackNode;

typedef struct
{
	StackNode* top;
}LinkedStackType;

void Error(char* s)
{
	printf("---<%s>---\n", s);
}

LinkedStackType* CreateStack(void)
{
	LinkedStackType* p = (LinkedStackType*)malloc(sizeof(LinkedStackType));
	return p;
}
void InitStack(LinkedStackType* s)
{
	s->top = NULL;
}
int IsEmptyStack(LinkedStackType* s)
{
	return (s->top == NULL);
}

void Push(LinkedStackType* s, element item)
{
	StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
	if(temp == NULL)
	{
		Error("Memory allocation error!");
		return;
	}
	temp->item = item;
	temp->link = s->top;
	s->top = temp;
}

element Pop(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack Underflow");
		return -1;
	}
	StackNode* temp = s->top;
	element item = temp->item;
	s->top = s->top->link;
	free(temp);
	return item;
}
element PeekStack(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return -1;
	}
	return s->top->item;
}
void PrintStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return;
	}
	while (temp != NULL)
	{
		printf("%d\n", temp->item);
		temp = temp->link;
	}

}
void RemoveAllStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	StackNode* next;
	while (temp != NULL)
	{
		next = temp->link;
		free(temp);
		temp = next;
	}
	s->top = NULL;
}
int CheckMatch(char* expression)
{
	LinkedStackType* pStack = CreateStack();
	InitStack(pStack);

	char* p = expression;
	int retVal = 1;
	// 여는 괄호 Push , 닫는 괄호일경우 pop , 문자열이 끝났을때 비워져있을 경우 참
	while (*p)
	{
		if (*p == '[' || *p == '{' || *p == '(')
		{
			Push(pStack, *p);
		}
		else
		{
			switch (*p)
			{
			case ']':
				if (IsEmptyStack(pStack) || Pop(pStack) != '[')
				{
					retVal = 0;
				}
				break;
			case '}':
				if (IsEmptyStack(pStack) || Pop(pStack) != '{')
				{
					retVal = 0;
				}
				break;
			case ')':
				if (IsEmptyStack(pStack) || Pop(pStack) != '(')
				{
					retVal = 0;
				}
				break;
			}
			
			if (!retVal)
			{
				RemoveAllStack(pStack);
				free(pStack);
				return retVal;

			}
		}
		p++;
	}
	if (!IsEmptyStack(pStack))
	{
		retVal = 0;
	}
	RemoveAllStack(pStack);
	free(pStack);
	return retVal;
}





int main(void)
{
	char exp1[] = { "[ a { b + c - ( a * 3 ) } + 4 ]" };
	char exp2[] = { "[ a { b + c - ( a * 3 ) + 4 ]" };

	printf("%d\n", CheckMatch(exp1));
	printf("%d\n", CheckMatch(exp2));


	return 0;
}