C Program to Convert Infix Expression to Postfix

A C program to convert infix to postfix uses a stack to reorder operators by precedence; for example, use push(), pop(), and precedence checks to output the postfix expression from the infix input.

Examples

InputA+B

OutputAB+

InputA+B*C

OutputABC*+

Input(A+B)*C

OutputAB+C*

How to Think About It

To convert infix to postfix, read the expression left to right. Output operands immediately. Use a stack to hold operators. Push operators on the stack, but pop and output operators with higher or equal precedence first. Handle parentheses by pushing '(' and popping until '(' when ')' is found. This rearranges operators after operands to postfix order.

Algorithm

1

Read the infix expression from left to right.

2

If the character is an operand, add it to the postfix output.

3

If the character is '(', push it onto the stack.

4

If the character is ')', pop and output from the stack until '(' is found; remove '(' from stack.

5

If the character is an operator, pop from the stack to output all operators with higher or equal precedence, then push the current operator.

6

After reading the expression, pop and output all remaining operators from the stack.

Code

c

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) {
    stack[++top] = c;
}

char pop() {
    if (top == -1) return '\0';
    return stack[top--];
}

int precedence(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 0;
}

void infixToPostfix(char* infix, char* postfix) {
    int i = 0, k = 0;
    char c;
    while ((c = infix[i++]) != '\0') {
        if (isalnum(c)) {
            postfix[k++] = c;
        } else if (c == '(') {
            push(c);
        } else if (c == ')') {
            while (top != -1 && stack[top] != '(') {
                postfix[k++] = pop();
            }
            if (top != -1) pop(); // remove '('
        } else { // operator
            while (top != -1 && precedence(stack[top]) >= precedence(c)) {
                postfix[k++] = pop();
            }
            push(c);
        }
    }
    while (top != -1) {
        postfix[k++] = pop();
    }
    postfix[k] = '\0';
}

int main() {
    char infix[MAX], postfix[MAX];
    printf("Enter infix expression: ");
    fgets(infix, MAX, stdin);
    infix[strcspn(infix, "\n")] = '\0';
    infixToPostfix(infix, postfix);
    printf("Postfix expression: %s\n", postfix);
    return 0;
}

Dry Run

Let's trace the input 'A+B*C' through the code

1

Read 'A'

It's an operand, add to postfix: postfix = 'A'

2

Read '+'

Stack empty, push '+': stack = ['+']

3

Read 'B'

Operand, add to postfix: postfix = 'AB'

4

Read '*'

Top of stack is '+', which has lower precedence than '*', so push '*': stack = ['+', '*']

5

Read 'C'

Operand, add to postfix: postfix = 'ABC'

6

End of input

Pop all from stack to postfix: pop '*', postfix = 'ABC*'; pop '+', postfix = 'ABC*+'

Step	Input Char	Stack	Postfix Output
1	A	[]	A
2	+	[+]	A
3	B	[+]	AB
4	*	[+, *]	AB
5	C	[+, *]	ABC
6	End	[]	ABC*+

Why This Works

Step 1: Operands go directly to output

When the code reads a letter or number (operand), it adds it immediately to the postfix string because operands keep their order.

Step 2: Operators use stack for precedence

Operators are pushed on a stack but before pushing, the code pops operators with higher or equal precedence to keep correct order.

Step 3: Parentheses control grouping

When '(' is found, it is pushed to mark a group; when ')' is found, operators are popped until '(' is removed, ensuring grouped operations.

Alternative Approaches

Using linked list stack

c

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

typedef struct Node {
    char data;
    struct Node* next;
} Node;

Node* push(Node* top, char c) {
    Node* newNode = malloc(sizeof(Node));
    newNode->data = c;
    newNode->next = top;
    return newNode;
}

Node* pop(Node** top) {
    if (*top == NULL) return NULL;
    Node* temp = *top;
    *top = (*top)->next;
    return temp;
}

int precedence(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 0;
}

void infixToPostfix(char* infix, char* postfix) {
    Node* stack = NULL;
    int i = 0, k = 0;
    char c;
    while ((c = infix[i++]) != '\0') {
        if (isalnum(c)) {
            postfix[k++] = c;
        } else if (c == '(') {
            stack = push(stack, c);
        } else if (c == ')') {
            while (stack && stack->data != '(') {
                postfix[k++] = pop(&stack)->data;
            }
            Node* temp = pop(&stack);
            free(temp);
        } else {
            while (stack && precedence(stack->data) >= precedence(c)) {
                postfix[k++] = pop(&stack)->data;
            }
            stack = push(stack, c);
        }
    }
    while (stack) {
        postfix[k++] = pop(&stack)->data;
    }
    postfix[k] = '\0';
}

int main() {
    char infix[100], postfix[100];
    printf("Enter infix expression: ");
    fgets(infix, 100, stdin);
    infix[strcspn(infix, "\n")] = '\0';
    infixToPostfix(infix, postfix);
    printf("Postfix expression: %s\n", postfix);
    return 0;
}

Uses dynamic memory and linked list for stack instead of array; more flexible but more complex.

Using recursion to parse expression

c

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

// This method is complex and not shown fully here due to length.
// It parses expression recursively and builds postfix.
// Tradeoff: harder to implement but elegant for expression trees.

Recursion can parse and convert but is more complex and less efficient for simple conversion.

Complexity: O(n) time, O(n) space

Time Complexity

The program processes each character once, pushing or popping from the stack, so it runs in linear time relative to the expression length.

Space Complexity

The stack can hold up to all operators in the expression, so space used is proportional to the input size.

Which Approach is Fastest?

Array-based stack is faster and simpler than linked list stack due to less overhead; recursion is elegant but slower and more complex.

Approach	Time	Space	Best For
Array Stack	O(n)	O(n)	Simple and fast conversion
Linked List Stack	O(n)	O(n)	Dynamic size, flexible memory
Recursive Parsing	O(n)	O(n)	Complex expressions, expression trees