#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#define MAX 100 // Maximum size of stack
char stk[MAX];
int top = -1;
int isEmpty() {
return top == -1;
}
int isFull() {
return top == MAX - 1;
}
char peek() {
return stk[top];
}
char pop() {
if (isEmpty())
return -1;
char ch = stk[top];
top--;
return ch;
}
void push(char oper) {
if (isFull())
printf("Stack Full!!!!");
else {
top++;
stk[top] = oper;
}
}
int checkIfOperand(char ch) {
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
int precedence(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
// Function to reverse a string
void reverse(char* expression) {
int n = strlen(expression);
for (int i = 0; i < n / 2; i++) {
char temp = expression[i];
expression[i] = expression[n - i - 1];
expression[n - i - 1] = temp;
}
}
// Function to convert infix to postfix
void covertInfixToPostfix(char* expression, char* postfix) {
int i, j = 0;
for (i = 0; expression[i]; ++i) {
if (checkIfOperand(expression[i])) {
postfix[j++] = expression[i];
} else if (expression[i] == ')') {
push(expression[i]);
} else if (expression[i] == '(') {
while (!isEmpty() && peek() != ')') {
postfix[j++] = pop();
}
if (!isEmpty())
pop(); // Pop the ')'
} else {
while (!isEmpty() && precedence(expression[i]) <= precedence(peek())) {
postfix[j++] = pop();
}
push(expression[i]);
}
}
while (!isEmpty()) {
postfix[j++] = pop();
}
postfix[j] = '\0'; // Null-terminate the postfix string
}
// Function to convert infix to prefix
void covertInfixToPrefix(char* expression) {
// Reverse the infix expression
reverse(expression);
// Replace '(' with ')' and vice versa
for (int i = 0; expression[i]; i++) {
if (expression[i] == '(') {
expression[i] = ')';
} else if (expression[i] == ')') {
expression[i] = '(';
}
}
// Prepare an array to hold the postfix expression
char postfix[MAX];
covertInfixToPostfix(expression, postfix); // Convert reversed infix to postfix
// Reverse the postfix expression to get prefix
reverse(postfix);
printf("Prefix Expression: %s\n", postfix);
}
int main() {
char expression[MAX];
printf("Enter an infix expression: ");
fgets(expression, MAX, stdin);
// Remove the newline character if present
expression[strcspn(expression, "\n")] = 0;
covertInfixToPrefix(expression); // Convert infix to prefix
return 0;
}
