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

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more