C언어 15일차

여는 괄호나오면 무조건 집어넣기
스택이 비었거나, 탑이 여는 괄호면 들어간다. 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;
}