Program to Convert Infix to Postfix using Stack in C

This article explains the C program for converting infix expressions to postfix notation using a stack. By the end of this guide, you’ll understand how stacks are used to handle operator precedence and associativity effectively. Let’s break the code into meaningful sections for clarity.

Understanding Infix and Postfix Notation

  • Infix Notation: Operators are placed between operands. Example: A + B.
  • Postfix Notation: Operators follow their operands. Example: AB+.

Why Convert? Postfix expressions eliminate the need for parentheses and are easier for machines to evaluate using stacks.

Core Components of the Code

In this section any postfix notation you will enter, the following code will provide the output in term of result. Let start with first component

1. Stack Data Structure

The stack is implemented using an array with the following operations:

typedef struct {
char data[MAX]; // Array to hold stack elements
int top; // Index of the top element
} Stack;

2. Key Stack Operations:

  • Push: Adds an element to the top of the stack.
  • Pop: Removes and returns the top element.
  • Peek: Returns the top element without removing it.
void push(Stack *stack, char value) {
if (stack->top == MAX – 1) {
printf(“Stack overflow\n”);
return;
}
stack->data[stack->top + 1] = value;
stack->top++;
}

char pop(Stack *stack) {
if (stack->top == -1) {
printf(“Stack underflow\n”);
return ‘\0’;
}
char value = stack->data[stack->top];
stack->top–;
return value;
}

char peek(Stack *stack) {
if (stack->top == -1) {
return ‘\0’;
}
return stack->data[stack->top];
}

Explanation: 

  • push Function: Adds a value to the stack. It checks if the stack is full (stack->top == MAX - 1) to prevent overflow. If not full, it increments the top and inserts the value.
  • pop Function: Removes the top value from the stack. It checks if the stack is empty (stack->top == -1) to prevent underflow. If not empty, it retrieves the top value, decrements top, and returns the value.
  • peek Function: Returns the value at the top of the stack without removing it. If the stack is empty, it returns '\0' (null character).

4. Operator Precedence

To determine which operator should be evaluated first, we assign precedence levels:

  • ^: High precedence (3).
  • * and /: Medium precedence (2).
  • + and -: Low precedence (1).
int precedence(char operator) {
if (operator == ‘^’) return 3;
if (operator == ‘*’ || operator == ‘/’) return 2;
if (operator == ‘+’ || operator == ‘-‘) return 1;
return 0;
}

5. Operator Check

We check if a character is an operator (+, -, *, /, ^):

int isOperator(char ch) {
return (ch == ‘+’ || ch == ‘-‘ || ch == ‘*’ || ch == ‘/’ || ch == ‘^’);
}

6. Converting Infix to Postfix

The function infixToPostfix performs the conversion step-by-step:

void infixToPostfix(char *infix, char *postfix) {
Stack stack;
stack.top = -1; // Initialize stack
int i, j = 0;

for (i = 0; infix[i] != ‘\0’; i++) {
char ch = infix[i];

if (isalnum(ch)) {
// Append operands (letters/numbers) directly to postfix
postfix[j++] = ch;
} else if (ch == ‘(‘) {
// Push ‘(‘ onto the stack
push(&stack, ch);
} else if (ch == ‘)’) {
// Pop all operators until ‘(‘ is found
while (peek(&stack) != ‘(‘) {
postfix[j++] = pop(&stack);
}
pop(&stack); // Discard ‘(‘
} else if (isOperator(ch)) {
// Handle operators based on precedence
while (stack.top != -1 && precedence(peek(&stack)) >= precedence(ch)) {
postfix[j++] = pop(&stack);
}
push(&stack, ch);
}
}

// Append remaining operators in the stack to postfix
while (stack.top != -1) {
postfix[j++] = pop(&stack);
}
postfix[j] = ‘\0’; // Null-terminate the postfix string
}

7. Main Function

The program takes an infix expression from the user, converts it to postfix, and displays the result:

int main() {
char infix[MAX], postfix[MAX];

printf(“Enter an infix expression: “);
scanf(“%s”, infix); // Input infix expression

infixToPostfix(infix, postfix); // Conversion function

printf(“Postfix expression: %s\n”, postfix); // Output result

return 0;
}

This code converts an infix expression (e.g., “A+BC”) to a postfix expression (e.g., “ABC+”) using a stack-based algorithm. It processes the input character by character, appending operands directly to the result and handling operators, parentheses, and precedence using the stack. Remaining operators in the stack are appended to the postfix expression at the end. The main function takes user input, performs the conversion, and displays the result.

Complete Program to Convert Infix to Postfix using Stack in C

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

// Stack structure
typedef struct {
char data[MAX];
int top;
} Stack;

// Stack operations
void push(Stack *stack, char value) {
if (stack->top == MAX – 1) {
printf(“Stack overflow\n”);
return;
}
stack->data[stack->top + 1] = value;
stack->top++;
}

char pop(Stack *stack) {
if (stack->top == -1) {
printf(“Stack underflow\n”);
return ‘\0’;
}
char value = stack->data[stack->top];
stack->top–;
return value;
}

char peek(Stack *stack) {
if (stack->top == -1) {
return ‘\0’;
}
return stack->data[stack->top];
}

int precedence(char operator) {
if (operator == ‘^’) {
return 3;
} else if (operator == ‘*’ || operator == ‘/’) {
return 2;
} else if (operator == ‘+’ || operator == ‘-‘) {
return 1;
} else {
return 0;
}
}

int isOperator(char ch) {
if (ch == ‘+’ || ch == ‘-‘ || ch == ‘*’ || ch == ‘/’ || ch == ‘^’) {
return 1;
}
return 0;
}

void infixToPostfix(char *infix, char *postfix) {
Stack stack;
stack.top = -1;
int i, j = 0;

for (i = 0; infix[i] != ‘\0’; i++) {
char ch = infix[i];

if (isalnum(ch)) {
postfix[j] = ch;
j++;
} else if (ch == ‘(‘) {
push(&stack, ch);
} else if (ch == ‘)’) {
while (peek(&stack) != ‘(‘) {
postfix[j] = pop(&stack);
j++;
}
pop(&stack); // Remove ‘(‘ from stack
} else if (isOperator(ch)) {
while (stack.top != -1 && precedence(peek(&stack)) >= precedence(ch)) {
postfix[j] = pop(&stack);
j++;
}
push(&stack, ch);
}
}

while (stack.top != -1) {
postfix[j] = pop(&stack);
j++;
}

postfix[j] = ‘\0’;
}

int main() {
char infix[MAX], postfix[MAX];

printf(“Enter an infix expression: “);
scanf(“%s”, infix);

infixToPostfix(infix, postfix);

printf(“Postfix expression: %s\n”, postfix);

return 0;
}

Output:

Enter an infix expression: 7+5*3/5^1+(3-2)
Postfix expression: 753*51^/+32-+