Published: 29 Oct 2025 | Reading Time: 6 min read
In programming, converting expressions from infix to postfix notation is crucial for efficiently evaluating them. This technique is widely used in compiler design and optimisation.
The Infix notation is the standard way in which we write math expressions. It has operators placed between operands, such as A + B. It's intuitive for humans to write it like that, and hence, it's the go-to format for everyday arithmetic. However, for computers, it can be tricky to process due to the parentheses and varying operator precedence in the expressions.
The Postfix notation, which is also called the Reverse Polish Notation (RPN), places the operator after the operands. So, A + B becomes AB+. This format removes the need for parentheses and follows a simple, consistent logic that is easy for the computer to pick up. It makes it much easier for computers to evaluate expressions quickly and efficiently.
In this article, we'll explore the basics of an infix to postfix program in C and its significance in simplifying algorithm implementation.
Here's the infix to postfix algorithm in C:
Traversing the Expression: Scan the given infix expression from left to right and go character by character.
If the Scanned Character is an Operand: Directly output the operand (e.g., A, B, 3, etc.) to the postfix expression.
If the Scanned Character is an Operator:
If the Scanned Operator has Lower or Equal Precedence:
Parentheses Handling: If you encounter a ( during popping, stop popping and push the scanned operator onto the stack.
If the Scanned Character is a Left Parenthesis (:
If the Scanned Character is a Right Parenthesis ):
Repeat Steps 2 to 6: Continue scanning the entire expression, applying the above steps for each character.
End of Expression:
Now let's look at the infix to postfix program in C by two different approaches.
Here's how to implement infix to postfix conversion using stack in C:
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
char stk[20];
int top = -1;
int isEmpty()
{
return top == -1;
}
int isFull()
{
return top == MAX - 1;
}
char peek()
{
return stk[top];
}
char pop()
{
if (isEmpty())
return -1;
char ch = stk[top];
top--;
return(ch);
}
void push(char oper)
{
if (isFull())
printf("Stack Full!!!!");
else {
top++;
stk[top] = oper;
}
}
int checkIfOperand(char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
int precedence(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
void convertInfixToPostfix(char* expression)
{
int i, j = 0;
char postfix[MAX];
for (i = 0; expression[i]; ++i)
{
if (checkIfOperand(expression[i]))
postfix[j++] = expression[i];
else if (expression[i] == '(')
push(expression[i]);
else if (expression[i] == ')')
{
while (!isEmpty() && peek() != '(')
postfix[j++] = pop();
if (!isEmpty() && peek() != '(')
return; // Invalid expression
else
pop();
}
else
{
while (!isEmpty() && precedence(expression[i]) <= precedence(peek()))
postfix[j++] = pop();
push(expression[i]);
}
}
while (!isEmpty())
postfix[j++] = pop();
postfix[j] = '\0'; // Null-terminate the postfix expression
printf("Postfix Expression: %s\n", postfix);
}
int main()
{
char expression[] = "((x+(y*z))-w)";
convertInfixToPostfix(expression);
return 0;
}
xyz*+w-
#include<stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
// Define the Stack structure
struct Stack {
int top;
int maxSize;
char* array; // Change from int* to char* to store characters
};
// Function to create a stack
struct Stack* create(int max)
{
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->maxSize = max;
stack->top = -1;
stack->array = (char*)malloc(stack->maxSize * sizeof(char)); // Allocate memory for char type
return stack;
}
// Function to check if the stack is full
int isFull(struct Stack* stack)
{
if (stack->top == stack->maxSize - 1)
{
printf("Will not be able to push, maxSize reached\n");
}
return stack->top == stack->maxSize - 1;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
// Function to push an item onto the stack
void push(struct Stack* stack, char item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
}
// Function to pop an item from the stack
char pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN; // Return INT_MIN if stack is empty
return stack->array[stack->top--];
}
// Function to peek the top item of the stack
char peek(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN; // Return INT_MIN if stack is empty
return stack->array[stack->top];
}
// Function to check if a character is an operand
int checkIfOperand(char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
// Function to return the precedence of operators
int precedence(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
// Function to convert infix to postfix expression
int covertInfixToPostfix(char* expression)
{
int i, j;
// Create a stack for the expression
struct Stack* stack = create(strlen(expression));
if (!stack)
return -1; // Return error if memory allocation fails
// Traverse the expression character by character
for (i = 0, j = -1; expression[i]; ++i)
{
// If the character is an operand, append it to the postfix expression
if (checkIfOperand(expression[i]))
expression[++j] = expression[i];
// If the character is a left parenthesis
else if (expression[i] == '(')
push(stack, expression[i]);
// If the character is a right parenthesis
else if (expression[i] == ')')
{
// Pop from stack until we encounter a left parenthesis
while (!isEmpty(stack) && peek(stack) != '(')
expression[++j] = pop(stack);
if (!isEmpty(stack) && peek(stack) != '(')
return -1; // Return error if parentheses mismatch
else
pop(stack);
}
else
{
// Pop operators from the stack if they have higher or equal precedence
while (!isEmpty(stack) && precedence(expression[i]) <= precedence(peek(stack)))
expression[++j] = pop(stack);
push(stack, expression[i]);
}
}
// Pop remaining operators from the stack
while (!isEmpty(stack))
expression[++j] = pop(stack);
expression[++j] = '\0';
printf("Postfix Expression: %s\n", expression); // Output the postfix expression
return 0;
}
// Main function to test the conversion
int main()
{
char expression[] = "((x+(y*z))-w)";
covertInfixToPostfix(expression);
return 0;
}
xyz*+w-
Understanding the conversion from infix expression to postfix expression (also known as Reverse Polish Notation) is easier with concrete examples. Below, we walk through the process step by step, showing the stack status at each stage and highlighting how the infix-to-postfix (exp) algorithm works in practice.
Infix Expression: A + B * C
Step-by-Step Conversion:
Postfix Expression: ABC*+
Infix Expression: (a + b) * (c - d)
Step-by-Step Conversion:
Postfix Expression: ab+cd-*
After converting an infix expression to postfix, you can easily evaluate the postfix expression using a stack. For example, assess the postfix expression "82/3-" means:
Throughout the infix-to-postfix (efficient solution) process, the stack temporarily holds operators and parentheses. This helps ensure that operator precedence and associativity are handled correctly, and that the final postfix expression can be evaluated from left to right without ambiguity.
Understanding the infix-to-prefix algorithm in C is a critical skill for any programmer. This concept not only strengthens your grasp of data structures like stacks but also lays the foundation for solving complex problems in compiler design and expression evaluation. It is also a popular topic in coding interviews, where questions often test your ability to convert expressions and evaluate postfix notation efficiently. Mastering this algorithm helps students write better code and improve problem-solving skills crucial to real-world programming challenges. To build your skills further, enroll in the CCBP 4.0 Academy now to start your professional journey in software engineering.
Postfix is used in real compilers and AI math engines. It removes errors, speeds up code, and is a top interview question. Master it to stand out in tech jobs and build strong problem-solving skills.
Infix notation is the standard way of writing mathematical expressions. It is where operators are placed between operands. Think of A + B as an example where the + sign is the operator and A and B are operands.
Postfix notation is also called Reverse Polish Notation (RPN). It places operators after operands. In the same example as above, it looks like AB+.
Postfix eliminates the need for parentheses and simplifies expression evaluation. It makes it easier for computers to process.
The stack data structure is used to handle operators and parentheses during the conversion process.
Infix-to-postfix conversion tests your understanding of stacks, operator precedence, and expression evaluation. Therefore, it is a common question in technical interviews.
| Operator | Precedence Level | Description |
|---|---|---|
| ^ | 3 | Exponentiation (highest precedence) |
| *, / | 2 | Multiplication and Division |
| +, - | 1 | Addition and Subtraction (lowest precedence) |