Skip to content

Instantly share code, notes, and snippets.

@ChiNoel-osu
Created May 25, 2022 14:38
Show Gist options
  • Save ChiNoel-osu/6968a12452d3a7e3728c7b090cf7309e to your computer and use it in GitHub Desktop.
Save ChiNoel-osu/6968a12452d3a7e3728c7b090cf7309e to your computer and use it in GitHub Desktop.
Infix expression to Postfix expression (C)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<Windows.h>
#include<math.h>
char LastPopedChar; //Global variable bc im lazy
struct cLinkedList //Use a linked list as a stack
{
char cData;
struct cLinkedList* pLink;
};
struct cLinkedList* PushWhatTo(char x, struct cLinkedList* pHead)
{
struct cLinkedList* Temp = (struct cLinkedList*)malloc(sizeof(struct cLinkedList));
Temp->cData = x;
Temp->pLink = pHead;
pHead = Temp;
return pHead;
}
struct cLinkedList* PopStack(struct cLinkedList* pHead)
{
if (pHead == NULL)
{
puts("Nothing is in the stack! You idiot!");
putchar('\a');
return pHead;
}
struct cLinkedList* Temp = pHead;
LastPopedChar = pHead->cData;
pHead = pHead->pLink;
free(Temp);
return pHead;
}
main()
{
SetConsoleTitle(TEXT("Infix to Postfix converter."));
struct cLinkedList* LLStack = NULL;
char Input[100], Output[100];
int OutputCharCount = 0;
puts("Enter an infix expression below, use () as parenthesis.");
gets(Input);
puts("Converting to postfix....");
for (int i = 0; i < strlen(Input); i++)
{
switch (Input[i])
{
case '+':
case '-':
case '*':
case '/':
case '(':
//If stack operator has higher associativity than input operator
if (IsTopHigher(LLStack, Input[i]))
{
while (!DumpedAll(LLStack)) //Dump & Output all till empty or '('
{
LLStack = PopStack(LLStack);
Output[OutputCharCount++] = LastPopedChar;
}
LLStack = PushWhatTo(Input[i], LLStack); //Then push the input operator
}
else LLStack = PushWhatTo(Input[i], LLStack);
break;
case ')':
while (LLStack->cData != '(') //Dump & Output till the next '('
{
LLStack = PopStack(LLStack);
Output[OutputCharCount++] = LastPopedChar;
}
LLStack = PopStack(LLStack); //Pop the '(' but not outputting
break;
default: //Operand, output as normal.
Output[OutputCharCount++] = Input[i];
break;
}
}
while (LLStack != NULL)
{
Output[OutputCharCount++] = LLStack->cData;
LLStack = PopStack(LLStack);
}
Output[OutputCharCount] = '\0';
puts("The converted expression is:");
printf("%s", Output);
return 0;
}
BOOL IsTopHigher(struct cLinkedList* pHead, char para)
{
if (pHead == NULL) return FALSE; //Empty list, not higher.
if (pHead->cData == '*' || pHead->cData == '/') //Top is higher
{
if (para == '*' || para == '/' || para == '(') return FALSE; //Input is of same level
else return TRUE;
}
else return FALSE; //Top is lower, including when input is of same level or higher
}
BOOL DumpedAll(struct cLinkedList* pHead)
{
if (pHead == NULL || pHead->cData == '(') return TRUE;
else return FALSE;
}
//Logical Refrence: https://blog.csdn.net/sgbfblog/article/details/8001651
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment