infix to postfix conversion in c

Infix to Postfix Conversion in C

by

Introduction

This article delves into the Infix to Postfix Conversion in C, elucidating the algorithm behind this transformation and providing a comprehensive C program to execute the conversion.

This understanding is not just crucial for academic purposes but also has real-world applications in calculator software and compilers.

Also Read: Insert and Delete Element in Array in C Using Switch Case

In the realm of computer science and mathematics, notation plays a pivotal role in representing and processing expressions. Among the most prevalent notations are infix, prefix, and postfix.

The infix notation is what we regularly encounter in mathematics, where operators are positioned between the operands (e.g., A + B).

However, in certain computational environments and for specific algorithms, the postfix notation, also known as Reverse Polish Notation (RPN), proves to be more efficient. In postfix, operators follow their operands (e.g., A B +).

What is Stack?

A stack is a linear data structure that follows a particular order in which operations are performed. The order is based on the Last In First Out (LIFO) principle.

Also Read: C Program To Read Two Files Simultaneously

This means that the last element added to the stack will be the first element to be removed. It can be visualized as a collection of items stacked on top of each other, much like a stack of plates.

You can only add (push) or remove (pop) a plate from the top. The stack has two primary operations:

  1. Push: To add an element to the top of the stack.
  2. Pop: To remove the top element from the stack.

In the context of the “Infix to Postfix Conversion in C”, a stack plays a fundamental role. The stack assists in holding operators and ensuring they are placed in the correct order in the postfix expression.

Also Read: Armstrong Number in C Programming

Beyond its application in the conversion of notations, stacks are utilized in various algorithms and processes, such as backtracking, memory management, and even in the functioning of the “Undo” operation in many software applications.

Step-by-Step Simulation of Infix to Postfix Conversion in C

Let’s simplify the explanation for the Infix to Postfix Conversion in C with a step-by-step breakdown.

Infix Expression:

(A + B) * (C - D)

For our simulation, we’ll maintain two primary entities:

  1. Stack: To temporarily hold operators and parentheses.
  2. Postfix List: Our output, which will be the resultant postfix expression.

Also Read: C Program to Find the Inverse of 2×2 Matrix

Simulation:

Initial State:

  • Stack: Empty
  • Postfix List: Empty
  1. Scanned: (
    • Action: Push to stack.
    • Stack: (
    • Postfix List: Empty
  1. Scanned: A
    • Action: Add to postfix list.
    • Stack: (
    • Postfix List: A
  1. Scanned: +
    • Action: Push to stack.
    • Stack: ( +
    • Postfix List: A
  1. Scanned: B
    • Action: Add to postfix list.
    • Stack: ( +
    • Postfix List: A B
  1. Scanned: )
    • Action: Pop and add to postfix until (.
    • Stack: Empty
    • Postfix List: A B +
  1. Scanned: *
    • Action: Push to stack.
    • Stack: *
    • Postfix List: A B +
  1. Scanned: (
    • Action: Push to stack.
    • Stack: * (
    • Postfix List: A B +
  1. Scanned: C
    • Action: Add to postfix list.
    • Stack: * (
    • Postfix List: A B + C
  1. Scanned: -
    • Action: Push to stack.
    • Stack: * ( -
    • Postfix List: A B + C
  1. Scanned: D
  • Action: Add to postfix list.
  • Stack: * ( -
  • Postfix List: A B + C D
  1. Scanned: )
  • Action: Pop and add to postfix until (.
  • Stack: *
  • Postfix List: A B + C D -
  1. End of Expression:
  • Action: Pop and add remaining stack content to postfix.
  • Stack: Empty
  • Postfix List: A B + C D - *

Final Postfix Expression:

A B + C D - *

This is the simplified simulation of “Infix to Postfix Conversion in C”. After each step, you can clearly see the current state of both the stack and the postfix list, giving you insight into the conversion process.

Also Read: C Program to Copy the Contents of One File into Another File

Step-by-Step Guide to Implementing Infix to Postfix Conversion in C

Here are simple steps to write the “Infix to Postfix Conversion in C” program:

  1. Include Necessary Headers:
    • Start with including necessary headers like stdio.h and stdlib.h.
  2. Define Data Structures:
    • Create a stack data structure to handle operators and parentheses. This usually involves defining a structure for the stack and providing utility functions like push(), pop(), isEmpty(), and top().
  3. Determine Operator Precedence:
    • Define a function, let’s call it precedence(), that takes an operator as input and returns a numerical value representing its precedence. For example, * and / could have a higher value than + and -.
  4. Character Handling Functions:
    • Define helper functions to identify the type of character: isOperator(), isOperand(), and so forth.
  5. Infix to Postfix Conversion:
    • Scan the infix expression from left to right.
    • For each scanned character:
      • If it’s an operand, append it to the postfix expression.
      • If it’s an open parenthesis, push it onto the stack.
      • If it’s a closing parenthesis, pop from the stack and append to the postfix expression until you encounter an open parenthesis.
      • If it’s an operator, pop and append operators from the stack to the postfix expression until you encounter an operator with lower precedence or the stack is empty. Then, push the scanned operator onto the stack.
    • After scanning the entire infix expression, pop and append any remaining operators from the stack to the postfix expression.
  6. Main Function:
    • Prompt the user to enter an infix expression.
    • Call the Infix to Postfix conversion function.
    • Display the resultant postfix expression.

Following these steps should guide you in writing a basic yet effective program for the Infix to Postfix Conversion in C. Remember, practice and understanding of the underlying algorithm will make the implementation smoother.

Also Read: Getchar and Putchar Function in C with Example

C program for the Infix to Postfix Conversion

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

#define MAX 100

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

void push(char item) {
    if (top >= MAX - 1) {
        printf("\nStack Overflow.");
    } else {
        top++;
        stack[top] = item;
    }
}

char pop() {
    char item;

    if (top < 0) {
        printf("Stack Underflow.");
        exit(1);
    } else {
        item = stack[top];
        top--;
        return(item);
    }
}

int isOperator(char symbol) {
    if (symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol == '-') {
        return 1;
    }
    return 0;
}

int precedence(char symbol) {
    switch (symbol) {
        case '^': return 3;
        case '*':
        case '/': return 2;
        case '+':
        case '-': return 1;
        default: return 0;
    }
}

void infixToPostfix(char infix[], char postfix[]) {
    int i, j = 0;
    char x, y;

    for (i = 0; infix[i] != '\0'; i++) {
        x = infix[i];

        if (isalnum(x)) {
            postfix[j++] = x;
        } else if (x == '(') {
            push(x);
        } else if (x == ')') {
            while ((y = pop()) != '(') {
                postfix[j++] = y;
            }
        } else if (isOperator(x)) {
            while (precedence(stack[top]) >= precedence(x)) {
                postfix[j++] = pop();
            }
            push(x);
        }
    }

    while (top != -1) {
        postfix[j++] = pop();
    }
    postfix[j] = '\0';
}

int main() {
    char infix[MAX], postfix[MAX];

    printf("Enter Infix expression: ");
    gets(infix);

    infixToPostfix(infix, postfix);

    printf("Postfix Expression: %s", postfix);

    return 0;
}

Explanation

Let’s break down the above c program.

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

These are the library headers. Think of them as toolboxes. Each provides specific tools (functions) that we will use in our program.

#define MAX 100

We’re setting a constant named MAX to 100. This helps us decide the maximum size of our stack and expressions.

char stack[MAX];
int top = -1;
  • stack[MAX]: Here, we’re creating a “stack” which can hold up to 100 characters.
  • top = -1: The top helps us keep track of the topmost item in our stack. Setting it to -1 means our stack is currently empty.
void push(char item) { ... }

This function, named push, adds items to our stack. If the stack is full, it warns us. Otherwise, it adds the given item to the top.

char pop() { ... }

pop is a function that removes the topmost item from our stack and returns it. If there’s nothing to remove (i.e., the stack is empty), it gives a warning.

int isOperator(char symbol) { ... }

This function checks if a character is an operator (like +, -, *, etc.). It returns 1 (true) if it is, otherwise 0 (false).

int precedence(char symbol) { ... }

This function assigns a priority level to operators. Some operators need to come before others in our final result, and this function helps us determine that order.

void infixToPostfix(char infix[], char postfix[]) { ... }

Here’s the main function that does the conversion:

  1. It looks at each character in our input (infix expression).
  2. If the character is a number or a letter, it adds it directly to the output.
  3. If it’s a left bracket, it pushes it onto the stack.
  4. If it’s a right bracket, it keeps popping and adding to the output until it finds the matching left bracket.
  5. If it’s an operator, it pops the operators with higher or equal priority from the stack and pushes the current one.
int main() { ... }

This is the starting point of our program:

  1. It asks the user to type an infix expression.
  2. It calls the infixToPostfix function to convert the given expression.
  3. Finally, it displays the converted expression.

Also Read: C Program to Find the Sum of Cubes of Elements in an Array

And there you have it! This program is like a little machine where you feed in a regular mathematical expression, and it rearranges it in a different format, using a stack to keep things in order. The stack acts like a temporary holding area for operators and brackets, ensuring the correct order in the final expression.

Conclusion

Understanding the intricacies of converting infix expressions to postfix is not just an academic exercise; it offers insights into how computers process information efficiently. The use of a stack, as demonstrated in our C program, showcases the power of data structures in simplifying complex operations. By transforming an infix notation, which is more human-readable, to a postfix one, we’re aligning mathematical expressions to a format that machines find more straightforward to evaluate. Whether you’re a budding programmer or a curious individual, mastering such concepts paves the way for deeper dives into computer science and algorithmic thinking. As we continue our journey into the digital age, such foundational knowledge empowers us to craft solutions that harmoniously blend human intuition with computational efficiency.