Infix to Postfix Conversion in C – Shunting-Yard Algorithm

Infix to postfix conversion in C transforms a human-readable arithmetic expression like A + B * C into postfix notation A B C * +, where operators follow their operands. Postfix eliminates the need for parentheses and precedence rules during evaluation — a stack scan from left to right is all that’s needed.

This page covers the Shunting-Yard algorithm with a complete C implementation, step-by-step trace, and sample conversions.

Infix vs Postfix

Algorithm — Shunting-Yard (Dijkstra)

Scan the expression left to right. Use a stack for operators and write operands directly to output:

1. Operand (letter or digit) → write to output.
2. ( → push onto stack.
3. ) → pop and output until ( is found; discard the parentheses.
4. Operator → pop and output all stack operators with equal or higher precedence, then push the current operator.
5. End of input → pop and output everything remaining.

Precedence: * / = 3 > + - = 2 > ( = 1

Walkthrough — converting A + B * C:

Token  Action                    Stack     Output
A      operand → output          []        A
+      push (stack empty)        [+]       A
B      operand → output          [+]       A B
*      pr(*)=3 > pr(+)=2, push  [+ *]     A B
C      operand → output          [+ *]     A B C
end    pop all                   []        A B C * +

Walkthrough — converting (A + B) * C:

Token  Action                    Stack     Output
(      push                      [(]
A      output                    [(]       A
+      push                      [(+]      A
B      output                    [(+]      A B
)      pop until (               []        A B +
*      push                      [*]       A B +
C      output                    [*]       A B + C
end    pop all                   []        A B + C *

C Program for Infix to Postfix Conversion

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

#define SIZE 50

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

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

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

void infixToPostfix(const char *infix, char *postfix)
{
    int i, k = 0;
    char ch;

    push('#');   /* sentinel with precedence 0 */

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

        if (isalnum(ch)) {
            postfix[k++] = ch;
        } else if (ch == '(') {
            push(ch);
        } else if (ch == ')') {
            while (!isEmpty() && peek() != '(')
                postfix[k++] = pop();
            if (!isEmpty()) pop();   /* discard '(' */
        } else {
            while (!isEmpty() && precedence(peek()) >= precedence(ch))
                postfix[k++] = pop();
            push(ch);
        }
    }
    while (peek() != '#')
        postfix[k++] = pop();

    postfix[k] = '\0';
}

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

    printf("Enter infix expression: ");
    scanf("%49s", infix);

    infixToPostfix(infix, postfix);
    printf("Postfix: %s\n", postfix);

    return 0;
}

How to Compile and Run

gcc -Wall -o infix infix.c
./infix

Sample Output

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

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

Enter infix expression: A-B+C
Postfix: AB-C+

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

Code Notes

• Sentinel #: Pushed at the start so the while (peek() != '#') loop at the end is safe — it never pops from an empty stack.
• isalnum(ch): Treats single-letter variables and single-digit numbers as operands. Multi-digit numbers and variable names require a tokenizer (beyond this scope).
• Left-associativity: The condition precedence(peek()) >= precedence(ch) uses >= (not >), which handles left-to-right associativity for same-precedence operators like + and -.
• Input limit: scanf("%49s", infix) limits input to 49 characters, preventing buffer overflow.

What This Program Teaches

• How a stack naturally handles operator precedence without any backtracking
• Why postfix notation is easier for computers: no parentheses, no precedence lookups — just push operands, pop on operators
• The sentinel pattern: a dummy element at the bottom of the stack eliminates empty-stack edge cases
• Left-associativity: same-precedence operators must be output left to right — the >= vs > distinction

Related Programs

• Infix to Postfix Conversion and Evaluation in C
• Stack Implementation in C Using Arrays
• Stack Implementation Using Linked Lists
• C Aptitude Questions and Answers

As an Amazon Associate we earn from qualifying purchases.

Recommended Book

Stacks and expression parsing are natural exercises after reading chapters 4 and 5 of The C Programming Language by Kernighan & Ritchie. Also on Amazon.com.