Infix to Postfix Conversion

Infix Expression:

An infix expression is a mathematical expression in which the operators are placed between the operands. This is the standard way we write mathematical expressions. In infix notation, we use parentheses to indicate the order of operations, and the precedence of operators determines the sequence of evaluation. For example:

Infix Expression: 3 + 5 * (2 - 8)

Here, the addition (+), subtraction (-), multiplication (*), and parentheses are part of the infix notation.

Postfix Expression (also known as Reverse Polish Notation - RPN): A postfix expression is a mathematical expression in which the operators come after their operands. Postfix notation eliminates the need for parentheses and follows a more straightforward evaluation process. To evaluate a postfix expression, you can use a stack-based algorithm. For example:

Infix Expression: 3 + 5 * (2 - 8)
Postfix Expression: 3 5 2 8 - * +

In the corresponding postfix expression, you can directly read the order of operations from left to right. For instance, 3 5 2 8 - * + can be evaluated as follows:

3 5 2 8 - *: Subtract 2 from 8, multiply the result by 5, and push it back.
3 * (5 * (2 - 8)): Multiply the result by 3 and push it back.
3 + 5 * (2 - 8): Add 3 to the final result.

Postfix notation is particularly useful in computing environments for its simplicity and ease of evaluation without the need for explicit parentheses or adhering to operator precedence rules.

Examples:

Infix Expression: a + b
Postfix Expression: a b +

Infix Expression: a * (b + c)
Postfix Expression: a b c + *

Infix Expression: a + b * c
Postfix Expression: a b c * +

Infix Expression: (a + b) * c
Postfix Expression: a b + c *

Infix Expression: 
a * b + c
Postfix Expression: a b * c +

Infix Expression: a * (b + c) - d / e
Postfix Expression: a b c + * d e / -


Converting infix expressions to postfix expressions is particularly useful in computer science and programming for several reasons:

Simplified Expression Evaluation:Postfix expressions can be evaluated more easily than infix expressions. You can use a stack-based algorithm to efficiently evaluate the postfix expression, eliminating the need for parentheses and order of operations.

Elimination of Parentheses:In postfix notation, there is no need for parentheses to indicate the order of operations. The position of the operators in the postfix expression inherently represents their precedence.

Simplified Expression Parsing:Parsing postfix expressions is simpler and often more efficient than parsing infix expressions. This is especially beneficial in the implementation of compilers and interpreters.

Ease of Implementation in Stack-Based Processors:Many stack-based processors and virtual machines find it easier to process postfix expressions. The postfix notation naturally fits the stack-based execution model.

Reduced Ambiguity:Postfix expressions are unambiguous, meaning there is no need to consider operator precedence or use parentheses to clarify the order of operations. This can simplify the design of algorithms for expression parsing and evaluation.

Reverse Polish Notation (RPN) Calculator:Postfix notation is also known as Reverse Polish Notation (RPN). RPN calculators use postfix notation, allowing users to enter expressions without parentheses and ensuring unambiguous evaluation.

Expression Conversion:Converting expressions to postfix or prefix form is often a step in the process of simplifying or transforming expressions in computer algebra systems and symbolic mathematics.

Expression Storage and Representation:Postfix expressions can be more compactly stored in memory or transmitted over networks, as they eliminate the need for explicit parentheses and rely on the position of operators.

In summary, converting infix expressions to postfix notation is a valuable technique that simplifies expression evaluation, parsing, and processing, making it especially advantageous in various computing applications.

Converting an infix expression to a postfix expression involves reordering the operators and operands based on their precedence and associativity. Here's a step-by-step algorithm to perform infix to postfix conversion:

Algorithm for Infix to Postfix Conversion:
1.Initialize an empty stack to store operators.
2.Initialize an empty list or string to store the postfix expression.
3.Scan the infix expression from left to right.
4.For each symbol in the infix expression:
  •  If the symbol is an operand (variable or constant), append it to the postfix expression.
  •  If the symbol is an open parenthesis '(', push it onto the stack.
  •  If the symbol is a closing parenthesis ')', pop operators from the stack and append them to the postfix expression until an open parenthesis is encountered. Pop and discard the open parenthesis.
  •  If the symbol is an operator:
           Pop operators from the stack and append them to the postfix expression while the stack is not empty and the precedence of the current operator is less than or equal to the precedence of the operator at the top of the stack. Push the current operator onto the stack.
5.After scanning the entire infix expression, pop any remaining operators from the stack and append them to the postfix expression.

Let's go through an example of infix to postfix conversion using the algorithm, and I'll show you the contents of the stack at each step. We'll use the infix expression "a + b * (c - d)" for this example:

Infix Expression: a + b * (c - d)

Stack Contents and Postfix Expression Construction:

  1. Step 1: Initialize an empty stack and an empty postfix expression.

    • Stack: []
    • Postfix Expression: []

  2. Step 2: Scan the infix expression from left to right.

    • Read 'a' (operand) and append it to the postfix expression.

      • Stack: []
      • Postfix Expression: [a]

    • Read '+' (operator) and push it onto the stack.

      • Stack: [+]
      • Postfix Expression: [a]

    • Read 'b' (operand) and append it to the postfix expression.

      • Stack: [+]
      • Postfix Expression: [a, b]

    • Read '*' (operator) and push it onto the stack.

      • Stack: [+, *]
      • Postfix Expression: [a, b]

    • Read '(' (open parenthesis) and push it onto the stack.

      • Stack: [+, *, (]
      • Postfix Expression: [a, b]

    • Read 'c' (operand) and append it to the postfix expression.

      • Stack: [+, *, (]
      • Postfix Expression: [a, b, c]

    • Read '-' (operator) and push it onto the stack.

      • Stack: [+, *, (, -]
      • Postfix Expression: [a, b, c]

    • Read 'd' (operand) and append it to the postfix expression.

      • Stack: [+, *, (, -]
      • Postfix Expression: [a, b, c, d]

    • Read ')' (close parenthesis). Pop operators from the stack and append them to the postfix expression until an open parenthesis is encountered. Pop and discard the open parenthesis.

      • Stack: [+, *]
      • Postfix Expression: [a, b, c, d, -]

  3. Step 3: After scanning the entire infix expression, pop any remaining operators from the stack and append them to the postfix expression.

    • Pop '*' and append it to the postfix expression.

      • Stack: [+]
      • Postfix Expression: [a, b, c, d, -, *]

    • Pop '+' and append it to the postfix expression.

      • Stack: []
      • Postfix Expression: [a, b, c, d, -, *, +]

  4. The final postfix expression is [a, b, c, d, -, *, +].

This example demonstrates how the stack contents change during the infix to postfix conversion. The stack is used to keep track of operators and ensure correct order in the postfix expression.


Complexity

The time complexity of the infix to postfix conversion algorithm is O(n), where n is the length of the input infix expression. The algorithm processes each symbol in the input expression exactly once.

Let's analyze the key operations in the algorithm:

Scanning the Infix Expression:The algorithm scans each symbol in the infix expression exactly once, leading to a time complexity of O(n), where n is the length of the infix expression.

Operations Inside the Loop:Inside the loop, the operations involve stack manipulations and comparisons based on operator precedence. These operations take constant time for each iteration of the loop.

Final Stack Operations:After scanning the entire infix expression, there might be some remaining operators in the stack. Popping these operators and appending them to the postfix expression takes constant time for each operation.

Therefore, the overall time complexity is dominated by the scanning of the infix expression, resulting in O(n).

The space complexity is also O(n) because, in the worst case, the stack could contain all the operators from the infix expression. The space required for the output postfix expression is also proportional to the length of the input expression.

C Program -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("Stack Overflow.");
        exit(1);
    }
    stack[++top] = item;
}

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

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

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

void infix_to_postfix(char infix[], char postfix[]) {
    int i, j;
    char item;
    char x;

    push('(');
    strcat(infix, ")");
    i = 0;
    j = 0;
    item = infix[i];

    while (item != '\0') {
        if (item == '(') {
            push(item);
        } else if (isdigit(item) || isalpha(item)) {
            postfix[j] = item;
            j++;
        } else if (is_operator(item) == 1) {
            x = pop();
            while (is_operator(x) == 1 && precedence(x) >= precedence(item)) {
                postfix[j] = x;
                j++;
                x = pop();
            }
            push(x);
            push(item);
        } else if (item == ')') {
            x = pop();
            while (x != '(') {
                postfix[j] = x;
                j++;
                x = pop();
            }
        } else {
            printf("Invalid Expression.");
            exit(1);
        }
        i++;
        item = infix[i];
    }
    postfix[j] = '\0';
}

int main() {
    char infix[MAX], postfix[MAX];
    printf("Enter Infix Expression: ");
    scanf("%s",infix);
    infix_to_postfix(infix, postfix);
    printf("Postfix Expression: ");
    puts(postfix);
    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Stack

Image
A stack is a fundamental data structure in computer science and programming that follows the Last-In, First-Out (LIFO) principle . It is named "stack" because it resembles a stack of items, like a stack of plates or books, where you can only add or remove items from the top. Stacks are used for various purposes in programming and are essential in many algorithms and applications. Let's delve into the details of stacks: Key Operations:  A stack typically supports two primary operations: Push: This operation adds an element to the top of the stack. It is analogous to placing an item on top of the stack. Pop: This operation removes and returns the top element of the stack. It is like taking the top item off the stack. Additionally, stacks often provide the following operations: Peek (or Top): This operation retrieves the top element without removing it. It allows you to examine the top item without modifying the stack. IsEmpty: This operation checks if the stack is empty.
Read more

Quick Sort

Quick sort is a popular sorting algorithm that uses a divide-and-conquer strategy to efficiently sort an array or list. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Here's a detailed algorithm for the Quick Sort algorithm: Algorithm: Quick Sort 1.Choose a pivot element from the array. This can be done in various ways, such as selecting the first element, the last element, or a random element. The choice of the pivot can affect the algorithm's performance. 2,Partition the array into two sub-arrays:     Elements less than the pivot (left sub-array).     Elements greater than the pivot (right sub-array). 3.Recursively apply the Quick Sort algorithm to the left and right sub-arrays. 4.Combine the sorted left sub-array, pivot, and sorted right sub-array to obtain the final sorted ar
Read more