Infix to Postfix Conversion Using Stack in DSA C - Build from Scratch

Infix to Postfix Conversion Using Stack

📖 Scenario: You are building a simple calculator program that converts mathematical expressions written in the usual way (called infix notation) into a form that computers find easier to evaluate (called postfix notation).For example, the infix expression (A + B) * C becomes AB+C* in postfix.

🎯 Goal: Build a program that reads an infix expression and converts it to postfix using a stack data structure.

📋 What You'll Learn

Create a stack to hold operators

Use a precedence function to compare operator priorities

Process the infix expression character by character

Output the correct postfix expression

💡 Why This Matters

🌍 Real World

Converting infix to postfix is a key step in calculators and compilers to evaluate expressions correctly.

💼 Career

Understanding stacks and expression parsing is important for software developers working on interpreters, compilers, and calculators.

1

Create the stack and input expression

Create a character array called infix initialized with the string "(A+B)*C". Also, declare a character array called stack of size 20 and an integer variable called top initialized to -1.

DSA C

# Declare the infix expression, stack array, and top variable
# Your code here

Hint

Use char infix[] = "(A+B)*C"; to store the expression.

Use char stack[20]; to create the stack.

Initialize top to -1 to indicate the stack is empty.

2

Create the precedence function

Write a function called precedence that takes a character op and returns an integer representing its precedence: return 2 for '*' and '/', 1 for '+' and '-', and 0 for any other character.

DSA C

char infix[] = "(A+B)*C";
char stack[20];
int top = -1;

// Write the precedence function below
// Your code here

Hint

Use if and else if to check the operator.

Return the correct precedence number for each operator.

3

Implement the infix to postfix conversion logic

Write a for loop to iterate over each character in infix. Use variables i for index and j for postfix array index. For each character, if it is an uppercase letter, add it to postfix. If it is '(', push it to stack. If it is ')', pop from stack to postfix until '(' is found. For operators, pop from stack to postfix while the top of stack has higher or equal precedence, then push the current operator. Declare postfix as a character array of size 20 and initialize j to 0.

DSA C

char infix[] = "(A+B)*C";
char stack[20];
int top = -1;

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

// Declare postfix array and index j
// Write the for loop to convert infix to postfix
// Your code here

Hint

Use a loop to check each character in infix.

Use conditions to handle letters, parentheses, and operators.

Push and pop from stack as needed.

Build the postfix string step by step.

4

Print the postfix expression

Write a printf statement to print the string postfix with the message "Postfix expression: %s\n".

DSA C

char infix[] = "(A+B)*C";
char stack[20];
int top = -1;

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

char postfix[20];
int j = 0;

for (int i = 0; infix[i] != '\0'; i++) {
    char ch = infix[i];
    if (ch >= 'A' && ch = precedence(ch)) {
            postfix[j++] = stack[top--];
        }
        stack[++top] = ch;
    }
}
while (top != -1) {
    postfix[j++] = stack[top--];
}
postfix[j] = '\0';

// Print the postfix expression below
// Your code here

Hint

Use printf("Postfix expression: %s\n", postfix); to display the result.