Created
May 25, 2022 14:38
-
-
Save ChiNoel-osu/6968a12452d3a7e3728c7b090cf7309e to your computer and use it in GitHub Desktop.
Infix expression to Postfix expression (C)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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