C Program to Convert Infix to Postfix

by

Converting infix expressions to postfix is a fundamental task in C programming, especially in fields like compiler design and expression evaluation. Infix expressions (e.g., A + B) are the standard way humans write equations, while postfix expressions (e.g., A B +) are optimized for machine processing because they eliminate the need for parentheses and operator precedence rules. In this comprehensive guide, we’ll explore three effective methods to write C Program to Convert Infix to Postfix. Each method includes code examples, detailed explanations, and output to ensure clarity and usability. You can also refer to our complete guide to learn Set, Clear, and Toggle a Bit in C.

C Program to Convert Infix to Postfix: A Complete Guide

What Are Infix and Postfix Expressions?

Infix Expressions

In infix notation, operators are placed between operands. For example, A + B * C requires parentheses or precedence rules to clarify operator order. It’s intuitive for humans but complex for machines.

Postfix Expressions

In postfix notation, operators follow their operands. For the same expression, the postfix equivalent is A B C * +. Postfix eliminates parentheses and is easier for machines to evaluate using a stack.

Method 1) C Program to Convert Infix to Postfix Using a Stack

Overview

The most common way to convert an infix to postfix expression is by using a stack. Operators are pushed onto the stack, and operands are added directly to the postfix string.

Steps to Convert

  1. Scan the expression left to right.
  2. Push operands directly to the postfix output.
  3. Push operators to the stack while maintaining precedence.
  4. Use parentheses to manage grouping.
  5. Pop remaining operators into the postfix string after scanning.

Code Example

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

#define MAX 100

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

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

char pop() {
    return (top == -1) ? -1 : stack[top--];
}

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

void infixToPostfix(char *exp) {
    char *e = exp, x;
    while (*e != '\0') {
        if (isalnum(*e)) {
            printf("%c", *e);
        } else if (*e == '(') {
            push(*e);
        } else if (*e == ')') {
            while ((x = pop()) != '(') printf("%c", x);
        } else {
            while (precedence(stack[top]) >= precedence(*e))
                printf("%c", pop());
            push(*e);
        }
        e++;
    }
    while (top != -1) printf("%c", pop());
}

int main() {
    char exp[MAX];
    printf("Enter infix expression: ");
    scanf("%s", exp);
    printf("Postfix expression: ");
    infixToPostfix(exp);
    return 0;
}

Output

Enter infix expression: A+B*C
Postfix expression: ABC*+

Explanation

The stack handles operator precedence, ensuring multiplication (*) precedes addition (+).

Method 2) C Program to Convert Infix to Postfix Using Recursion

Overview

Recursive methods can also convert infix to postfix by breaking expressions into smaller components and evaluating them recursively.

Steps to Convert

  1. Identify the main operator (lowest precedence).
  2. Recursively convert left and right sub-expressions.
  3. Append the operator at the end.

Code Example

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

void infixToPostfix(char *exp, int start, int end) {
    if (start > end) return;

    int i, minPrecedence = 4, mainOp = -1;

    for (i = start; i <= end; i++) {
        if (exp[i] == '(') {
            int count = 1;
            while (count > 0 && i <= end) {
                i++;
                if (exp[i] == '(') count++;
                if (exp[i] == ')') count--;
            }
        } else if (!isalnum(exp[i]) && precedence(exp[i]) <= minPrecedence) {
            minPrecedence = precedence(exp[i]);
            mainOp = i;
        }
    }

    if (mainOp != -1) {
        infixToPostfix(exp, start, mainOp - 1);
        infixToPostfix(exp, mainOp + 1, end);
        printf("%c", exp[mainOp]);
    } else {
        for (i = start; i <= end; i++) printf("%c", exp[i]);
    }
}

int main() {
    char exp[MAX];
    printf("Enter infix expression: ");
    scanf("%s", exp);
    printf("Postfix expression: ");
    infixToPostfix(exp, 0, strlen(exp) - 1);
    return 0;
}

Output

Enter infix expression: A+(B*C)
Postfix expression: ABC*+

Explanation

The recursive approach evaluates sub-expressions and appends operators at the end.

Method 3) C Program to Convert Infix to Postfix Using Two Stacks

Overview

This method uses two stacks: one for operators and another for operands, ensuring operands and operators are handled separately.

Steps to Convert

  1. Push operands to the operand stack.
  2. Push operators to the operator stack.
  3. Pop and append operators when precedence rules allow.
  4. Combine stacks at the end.

Code Example

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

void twoStackConversion(char *exp) {
    char operators[MAX], postfix[MAX];
    int opTop = -1, postTop = 0;

    for (int i = 0; i < strlen(exp); i++) {
        if (isalnum(exp[i])) {
            postfix[postTop++] = exp[i];
        } else if (exp[i] == '(') {
            operators[++opTop] = exp[i];
        } else if (exp[i] == ')') {
            while (operators[opTop] != '(')
                postfix[postTop++] = operators[opTop--];
            opTop--;
        } else {
            while (opTop != -1 && precedence(operators[opTop]) >= precedence(exp[i]))
                postfix[postTop++] = operators[opTop--];
            operators[++opTop] = exp[i];
        }
    }
    while (opTop != -1) postfix[postTop++] = operators[opTop--];
    postfix[postTop] = '\0';

    printf("Postfix expression: %s\n", postfix);
}

int main() {
    char exp[MAX];
    printf("Enter infix expression: ");
    scanf("%s", exp);
    twoStackConversion(exp);
    return 0;
}

Output

Ener infix expression: A+B*C
Postfix expression: ABC*+

Explanation

The method ensures precise separation of operands and operators, simplifying the process.

Frequently Asked Questions (FAQs)

What is infix notation?

Infix notation places operators between operands, such as A + B.

What is postfix notation?

Postfix notation places operators after operands, such as A B +.

Why is postfix preferred in machines?

Postfix eliminates parentheses and simplifies evaluation using stacks.

What is the role of precedence in conversion?

Precedence determines operator order in postfix notation.

Can postfix expressions include parentheses?

No, postfix notation does not require parentheses.

What is the time complexity of stack-based conversion?

The time complexity is O(n)O(n)O(n), where nnn is the length of the expression.

What are common applications of postfix conversion?

Applications include calculators, compilers, and expression evaluators.

How does recursion handle conversion?

Recursion divides the expression into manageable sub-expressions.

Can spaces affect the conversion process?

Yes, spaces need to be handled carefully during parsing.

Is postfix unique for a given infix expression?

Yes, a given infix expression has a unique postfix equivalent.

Categories C

Leave a Comment