Infix to Postfix Conversion and Evaluation in C

Infix notation is the way humans write arithmetic: A + B, 5 * (2 + 3). The operator sits between its operands. Computers, however, evaluate expressions more efficiently in postfix notation (also called Reverse Polish Notation), where the operator comes after its operands: A B +, 5 2 3 + *.

This C program does both jobs in one pass: it converts an infix expression to postfix using a stack, then evaluates the postfix result to give the final answer.

Infix vs Postfix — The Key Difference

Expression	Infix	Postfix
A plus B	`A + B`	`A B +`
A plus B times C	`A + B * C`	`A B C * +`
Parenthesised	`(A + B) * C`	`A B + C *`
Complex	`5 + ((2 + 6) * 9) - 8`	`5 2 6 + 9 * + 8 -`

Why postfix? It eliminates the need for parentheses and operator precedence rules during evaluation. A simple left-to-right scan with a stack is all you need — no lookahead required. This is how compilers and calculators work internally.

Algorithm — Infix to Postfix Conversion

Uses a stack to hold operators temporarily. Operands go straight to output; operators wait on the stack until a lower-precedence operator or end of expression forces them out.

Rules:

Scan left to right.
Operand (letter or digit) → write to output immediately.
( → push onto stack.
) → pop and output until ( is found; discard both parentheses.
Operator → pop and output all operators of equal or higher precedence first, then push the current operator.
End of expression → pop and output everything remaining on the stack.

Precedence: * / (level 3) > + - (level 2) > ( (level 1) > # sentinel (level 0)

Walkthrough: Converting A + B * C

Token   Action                Stack       Output
A       operand → output      [#]         A
+       pr(#)=0 < pr(+)=2     [# +]       A
        push +
B       operand → output      [# +]       A B
*       pr(+)=2 < pr(*)=3     [# + *]     A B
        push *
C       operand → output      [# + *]     A B C
end     pop all: * then +     [#]         A B C * +

Result: A B C * +

Algorithm — Postfix Evaluation

Scan left to right.
Operand → push onto stack.
Operator → pop two operands, apply operator, push result.
End of expression → the single value on the stack is the answer.

Walkthrough: Evaluating 5 2 6 + 9 * + 8 -

Token   Stack after
5       [5]
2       [5, 2]
6       [5, 2, 6]
+       pop 6,2 → 2+6=8    [5, 8]
9       [5, 8, 9]
*       pop 9,8 → 8*9=72   [5, 72]
+       pop 72,5 → 5+72=77 [77]
8       [77, 8]
-       pop 8,77 → 77-8=69 [69]

Result: 69

C Program — Infix to Postfix Conversion and Evaluation

#define SIZE 50
#include <ctype.h>
#include <stdio.h>

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

void push(char elem)
{
    s[++top] = elem;
}

char pop(void)
{
    return s[top--];
}

int pr(char elem)
{
    switch (elem) {
        case '#': return 0;
        case '(': return 1;
        case '+':
        case '-': return 2;
        case '*':
        case '/': return 3;
    }
    return -1;
}

void remove_spaces(char *src)
{
    char *i = src, *j = src;
    while (*j != 0) {
        *i = *j++;
        if (*i != ' ')
            i++;
    }
    *i = 0;
}

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

    remove_spaces(infix);
    push('#');

    while ((ch = infix[i++]) != '\n') {
        if (ch == '(')
            push(ch);
        else if (isalnum(ch))
            postfix[k++] = ch;
        else if (ch == ')') {
            while (s[top] != '(')
                postfix[k++] = pop();
            pop();   /* discard '(' */
        } else {
            while (pr(s[top]) >= pr(ch))
                postfix[k++] = pop();
            push(ch);
        }
    }

    while (s[top] != '#')
        postfix[k++] = pop();

    postfix[k] = '\0';
}

int eval_postfix(char *postfix)
{
    char ch;
    int i = 0, op1, op2;

    while ((ch = postfix[i++]) != '\0') {
        if (isdigit(ch))
            push(ch - '0');
        else {
            op2 = pop();
            op1 = pop();
            switch (ch) {
                case '+': push(op1 + op2); break;
                case '-': push(op1 - op2); break;
                case '*': push(op1 * op2); break;
                case '/': push(op1 / op2); break;
            }
        }
    }
    return s[top];
}

int main(void)
{
    char infx[50], pofx[50];

    printf("Enter infix expression: ");
    fgets(infx, 50, stdin);

    infix_to_postfix(infx, pofx);

    printf("Infix    : %s", infx);
    printf("Postfix  : %s\n", pofx);

    top = -1;   /* reset stack for evaluation */
    printf("Result   : %d\n", eval_postfix(pofx));

    return 0;
}

Sample Input and Output

Enter infix expression: 5+((2+6)*9)-8

Infix    : 5+((2+6)*9)-8
Postfix  : 526+9*+8-
Result   : 69

Code Explanation

Shared stack s[]: Used for both phases. After conversion, top is reset to -1 so the same array is reused cleanly for evaluation.
Sentinel '#': Pushed before scanning begins. Acts as a stack bottom marker with precedence 0, so the loop while (pr(s[top]) >= pr(ch)) always terminates safely without checking for an empty stack.
remove_spaces(): Strips spaces in-place so A + B and A+B are treated identically.
Operand vs operator: isalnum(ch) covers both letters (variables) and digits. Single-digit numbers only — extend with a numeric stack for multi-digit support.
Evaluation — ch - '0': Converts a digit character to its integer value (e.g., '7' - '0' = 7).

Limitations

Single-digit operands only — 12 + 3 would treat 1, 2, and 3 as separate operands.
No error handling — mismatched parentheses or invalid characters cause undefined behavior.
Right-associative operators (like ^) need a tweak: use > instead of >= in the while loop when the current operator is right-associative.

How to Compile and Run

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

Related Programs

Recommended Books

The C Programming Language – Kernighan & Ritchie (India) | Amazon.com
C Programming: A Modern Approach – K.N. King (India) | Amazon.com

Practice data structures and algorithms with the C Programming Quiz App — 500+ MCQs covering stacks, expressions, sorting, and more.
Download on Google Play →

Infix to Postfix Conversion and Evaluation in C – With Example