Infix to Postfix | Stack (C) | Nikhil Learn Hub

Infix to postfix conversion

Infix is how we normally write expressions (operators between operands), e.g. a + b * c. Postfix (also called Reverse Polish Notation) puts each operator after its operands, e.g. a b c * +, which is easy to evaluate with a stack. Converting infix → postfix uses an operator stack and rules for precedence and parentheses—the classic shunting-yard idea (Dijkstra).

On this page

Notations — infix vs postfix (and prefix)
Precedence — which operator binds tighter
Algorithm — what to do for each symbol
Example in C — stack of operators, output string

1) Infix, postfix, and prefix

Three common expression notations (binary operators)
Notation	Operator position	Example (same meaning)
Infix	Between operands	`a + b * c`
Postfix (RPN)	After both operands	`a b c * +`
Prefix (Polish)	Before both operands	`+ a * b c`

Postfix has no parentheses needed when the order is unambiguous; the conversion from infix encodes precedence and parentheses into the order of operators in the output.

2) Precedence and parentheses

Operators like * and / bind tighter than + and -. Parentheses ( ) override that. The conversion algorithm compares the incoming operator with operators on the stack: higher (or equal, for left-associative ops) precedence on the stack is popped to the output first.

Precedence used in the C example (higher number = binds tighter)
Operators	Precedence	Associativity (example)
`+` `-`	`1`	Left: `a - b - c` is `(a - b) - c`
`*` `/`	`2`	Left
`(` `)`	—	`(` is pushed; `)` pops until `(` is removed

3) Shunting-yard style rules

Scan the infix string left to right. Use one stack for operators and ‘(’, and build the postfix string on the side.

What to do for each token
Token	Action
Operand	Append it to the postfix output.
`(`	Push onto the operator stack.
`)`	Pop operators to the output until you pop a matching `(` (do not output parentheses).
Operator `op`	While the stack top is an operator with precedence ≥ `op` (and not `(`), pop it to the output; then push `op`.
End of input	Pop any remaining operators to the output (should be no `(` left in a valid expression).

4) Example in C

The program below uses a char array stack with top == -1 when empty (same spirit as a stack using array). It reads an infix expression with scanf("%s", ...), prints the postfix form as it goes, and pops any remaining operators at the end. Operands are single characters (letters or digits); spaces are not handled in the input string.

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

#define MAX 100

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

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

// Pop
char pop() {
    if (top == -1)
        return -1;
    return stack[top--];
}

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

int main() {
    char exp[MAX];
    char *e, x;

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

    e = exp;

    printf("Postfix expression: ");

    while (*e != '\0') {
        // If operand, print it
        if (isalnum(*e)) {
            printf("%c", *e);
        }
        // If '(', push
        else if (*e == '(') {
            push(*e);
        }
        // If ')', pop until '('
        else if (*e == ')') {
            while ((x = pop()) != '(')
                printf("%c", x);
        }
        // Operator
        else {
            while (top != -1 && priority(stack[top]) >= priority(*e))
                printf("%c", pop());
            push(*e);
        }
        e++;
    }

    // Pop remaining elements
    while (top != -1) {
        printf("%c", pop());
    }

    return 0;
}

The operator branch’s inner while uses top != -1 && before priority(stack[top]) so an empty stack is not read (without that guard, the first operator can access stack[-1]). Prefer fgets and length checks over bare scanf("%s") in real programs. Right-associative operators need a different precedence test; multi-digit operands need tokenizing.

Trace for `a + b * c` (input `a+b*c`)

Operator stack is shown bottom → top (left to right). Postfix is built left to right.

Conversion trace
Step	Read	Action	Operator stack	Postfix so far
1	`a`	Operand → output	`(empty)`	`a`
2	`+`	Stack empty → push `+`	`+`	`a`
3	`b`	Operand → output	`+`	`ab`
4	`*`	`` > precedence of `+` on stack → push ``	`+ *`	`ab`
5	`c`	Operand → output	`+ *`	`abc`
6	end	Pop all operators to output (`*` then `+`)	`(empty)`	`abc*+`

Sample run (input `a+b*c`)
Step	Console
1	Program prints `Enter infix expression:`
2	You type `a+b*c` and press Enter.
3	Program prints `Postfix expression: abc*+` (no newline is added at the end unless you add `printf("\n");`).

Key points

Idea	Explanation
`*` before `+` in postfix	Multiplication binds tighter, so `*` appears immediately after its operands (`b` and `c`) before the `+` combines `a` with that result.
Stack holds operators	Operands go straight to the output; operators wait on the stack until their right-hand side is fully known.
Parentheses	`(` blocks popping; `)` flushes operators until the matching `(` is removed.
Next step	Evaluate postfix with a stack of values — see Postfix evaluation.

Key takeaway

Scan infix left to right: send operands to the output, use a stack to delay operators until precedence and parentheses say it is safe to pop them. The result is postfix ready for a simple stack-based evaluator.