Infix to Prefix Conversion in C – Stack Algorithm with Code

Infix to prefix conversion in C turns an everyday expression like (A+B)*C into its prefix (Polish notation) form *+ABC, where every operator comes before its operands. Compilers and expression evaluators use prefix and postfix forms because they need no parentheses and no precedence rules to evaluate — the structure is unambiguous. The standard algorithm is a neat trick: reverse the infix string (swapping parentheses), run a modified infix-to-postfix conversion with a stack, then reverse the result. This page implements it in tested, warning-free C89, including the detail almost every tutorial gets wrong: the right-associativity of the ^ exponent operator.

How It Works — Step by Step

1. Reverse the infix string, swapping every ( with ): (A+B)*C becomes C*(B+A).
2. Scan left to right with an operator stack:
   operands go straight to the output; ( is pushed; ) pops operators to the output until the matching (.
3. For an operator, pop while the stack top has strictly greater precedence (or greater-or-equal for the right-associative ^), then push it.
4. Empty the stack into the output, then reverse the output — that’s the prefix expression.

Hand trace for (A+B)*C → reversed: C*(B+A):

Reverse CBA+* → *+ABC. Done.

C Program for Infix to Prefix Conversion

/* Infix to prefix conversion in C using a stack
 * Compile: gcc -ansi -Wall -Wextra infix_prefix.c -o infix_prefix */
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 100

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

static void push(char c)  { stack[++top] = c; }
static char pop(void)     { return stack[top--]; }
static char peek(void)    { return stack[top]; }
static int  is_empty(void){ return top == -1; }

static int prec(char op)
{
    switch (op) {
    case '^':           return 3;
    case '*': case '/': return 2;
    case '+': case '-': return 1;
    default:            return 0;
    }
}

static void reverse(char *s)
{
    int i = 0, j = (int)strlen(s) - 1;

    while (i < j) {
        char t = s[i];
        s[i] = s[j];
        s[j] = t;
        i++;
        j--;
    }
}

static void swap_parens(char *s)
{
    int i;

    for (i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(') {
            s[i] = ')';
        } else if (s[i] == ')') {
            s[i] = '(';
        }
    }
}

static void infix_to_prefix(char *infix, char *prefix)
{
    int i, j = 0;

    reverse(infix);
    swap_parens(infix);

    for (i = 0; infix[i] != '\0'; i++) {
        char c = infix[i];

        if (isalnum((unsigned char)c)) {
            prefix[j++] = c;
        } else if (c == '(') {
            push(c);
        } else if (c == ')') {
            while (!is_empty() && peek() != '(') {
                prefix[j++] = pop();
            }
            if (!is_empty()) {
                pop();                    /* discard the '(' */
            }
        } else if (prec(c) > 0) {
            if (c == '^') {               /* right-associative */
                while (!is_empty() && prec(peek()) >= prec(c)) {
                    prefix[j++] = pop();
                }
            } else {                      /* left-associative */
                while (!is_empty() && prec(peek()) > prec(c)) {
                    prefix[j++] = pop();
                }
            }
            push(c);
        }
    }
    while (!is_empty()) {
        prefix[j++] = pop();
    }
    prefix[j] = '\0';
    reverse(prefix);
}

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

    printf("Enter an infix expression: ");
    if (fgets(infix, sizeof infix, stdin) == NULL) {
        return 1;
    }
    infix[strcspn(infix, "\n")] = '\0';

    infix_to_prefix(infix, prefix);
    printf("Prefix expression: %s\n", prefix);
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra infix_prefix.c -o infix_prefix
./infix_prefix

Sample Input and Output

Test 1 — parentheses:

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

Test 2 — precedence without parentheses:

Enter an infix expression: A+B*C-D
Prefix expression: -+A*BCD

Test 3 — right-associative exponent:

Enter an infix expression: X^Y^Z
Prefix expression: ^X^YZ

Test 4 — two parenthesized groups:

Enter an infix expression: (A+B)*(C-D)
Prefix expression: *+AB-CD

All outputs are real captured runs of the exact code above.

Code Explanation

• Why reverse-convert-reverse works: reversing the string turns “operator after operands” problems into “operator before operands” ones — a mirrored postfix conversion. Reversing the postfix-style output at the end restores reading order with each operator in front of what it operates on.
• The associativity detail: x^y^z means x^(y^z), not (x^y)^z. On the reversed string that flips: for ^ we pop on greater-or-equal precedence, while left-associative operators pop only on strictly greater. Get this backwards and Test 3 produces the wrong ^^XYZ.
• isalnum() gets an unsigned char cast: passing a plain char that happens to be negative is undefined behavior — a subtle portability bug the cast eliminates.
• Single-letter operands: like the classic textbook version, this handles single-character operands and no spaces. Tokenizing multi-digit numbers is the natural next exercise.

Time and Space Complexity

Every character is pushed and popped at most once — that’s why the whole conversion is linear.

What This Program Teaches

• Stack-based parsing — the shunting-yard idea behind every expression compiler
• Operator precedence and associativity — and why they’re separate concepts
• Problem transformation — solving prefix by reducing it to the already-solved postfix
• In-place string reversal — the two-index swap idiom

Related C Programs

• Infix to Postfix Conversion in C — the algorithm this one is built on
• Infix to Postfix + Evaluate the Result in C — conversion plus a working evaluator
• Stack Implementation in C — push, pop, peek from scratch
• Two Stacks in One Array in C — a classic follow-up interview question

Test yourself: our free C Programming Quiz app for Android has 150+ questions with explanations for every answer.

Recommended Book

The C Programming Language by Kernighan & Ritchie builds a stack-based expression evaluator in Chapter 4. We’ve solved all of the book’s exercises. Also on Amazon.com.