C언어 16일차

스택 계산기

 

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