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() {
return s[top--];
}
/* Returns operator precedence */
int pr(char elem) {
switch (elem) {
case '#': return 0;
case '(': return 1;
case '+':
case '-': return 2;
case '*':
case '/': return 3;
}
return -1;
}
/* Removes spaces from a string in-place */
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, elem;
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();
elem = pop(); /* discard the '(' */
} else { /* operator */
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() {
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;
}
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. Modifies the string character by character using two pointers.- 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). This works because digit characters are consecutive in ASCII.
Sample Input and Output
Enter infix expression: 5+((2+6)*9)-8
Infix : 5+((2+6)*9)-8
Postfix : 526+9*+8-
Result : 69
Limitations of This Program
- Single-digit operands only —
12 + 3 would treat 1, 2, and 3 as separate operands. Extend with an integer stack and string parsing for multi-digit numbers.
- No error handling — mismatched parentheses or invalid characters cause undefined behavior.
- Right-associative operators (like
^ for exponentiation) need a small tweak: use > instead of >= in the while loop when the current operator is right-associative.
Related Programs
As an Amazon Associate we earn from qualifying purchases.
Further Reading
The definitive reference for C — The C Programming Language by Brian Kernighan and Dennis Ritchie. Covers every concept on this site: pointers, arrays, structs, file I/O, and the standard library. Worth having on your desk.
