스택 계산기
#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;
}