Infix to Postfix Conversion Using Stack.

Created On: 09 January 2024
Converting an infix expression to a postfix expression involves rearranging the operators and operands to a postfix format. We can perform this operation using the Stack data structure by traversing the infix expression from left to right. But before moving to the algorithm part, let's quickly understand infix and postfix expressions.

Infix Expression:

An Infix Expression is a mathematical expression where the operators are placed between operands. For example, A + (B * C) is an Infix expression, where the operators (+ and *) are placed between the operands (A, B, and C). In infix notation, parentheses are used to determine the order of operations.

Postfix Expression:
A Postfix expression, also known as Reverse Polish Notation (RPN), is a mathematical expression where the operators follow their operands. For example, ABC*+ is a Postfix expression equivalent to the infix expression A + (B * C). In postfix notation, parentheses are not required since the order of operations is determined explicitly by the arrangement of operands and operators.

Example of Infix to Postfix Conversion.

Let’s convert the infix expression ((A + B) * C - D) / E to postfix.
  1. Expression: ((A + B) * C - D) / E
  2. Stack: (Empty)
  3. Postfix String: (Empty)

Iterating through the expression:
  • Character: ( → Push onto the stack.
  • Character: ( → Push onto the stack.
  • Character: A → Append to postfix string.
  • Character: + → Push onto the stack.
  • Character: B → Append to postfix string.
  • Character: ) → Pop and append operators (+) from the stack to the postfix string.
  • Character: * → Push onto the stack.
  • Character: C → Append to postfix string.
  • Character: - → Push onto the stack.
  • Character: D → Append to postfix string.
  • Character: ) → Pop and append operators (-, *) from the stack to the postfix string.
  • Character: / → Push onto the stack.
  • Character: E → Append to postfix string.
  • Empty the Stack: Pop and append the remaining operators (/) to the postfix string.

Resulting Postfix Expression:
The infix expression ((A + B) * C - D) / E converts to the postfix expression AB+C*DE-/.

Algorithm for Infix to Postfix Conversion.

  1. Initialize an empty stack to hold operators.
  2. Initialize an empty string to store the postfix expression.
  3. Iterate through the infix expression:
    • For each character:
    • If it’s an operand (alphabets or digits), add it to the postfix string.
    • If it’s an operator:
      • 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:
      • Pop and append the top of the stack to the postfix string.
      • Push the current operator onto the stack.
    • If it’s an opening parenthesis ‘(’, push it onto the stack.
    • If it’s a closing parenthesis ‘)’:
      • Pop and append operators from the stack to the postfix string until an opening parenthesis is encountered.
      • Discard the opening parenthesis.
  4. Pop and append any remaining operators from the stack to the postfix string.

Below is the code implementation for the above algorithm:

// C++ program for infix to postfix conversion using stack.
#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;

bool isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

int getPrecedence(char c) {
    if (c == '+' || c == '-')
        return 1;
    if (c == '*' || c == '/')
        return 2;
    return 0;
}

string infixToPostfix(string infix) {
    stack<char> s;
    string postfix = "";
    unordered_map<char, int> precedence;

    precedence['+'] = 1;
    precedence['-'] = 1;
    precedence['*'] = 2;
    precedence['/'] = 2;

    for (char c : infix) {
        if (isalnum(c))
            postfix += c;
        else if (c == '(')
            s.push(c);
        else if (c == ')') {
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            s.pop();
        } else {
            while (!s.empty() && precedence[c] <= precedence[s.top()]) {
                postfix += s.top();
                s.pop();
            }
            s.push(c);
        }
    }

    while (!s.empty()) {
        postfix += s.top();
        s.pop();
    }

    return postfix;
}

int main() {
    string infixExpression = "a+b*c-(d/e+f*g*h)";
    string postfixExpression = infixToPostfix(infixExpression);
    cout << "Infix Expression: " << infixExpression << endl;
    cout << "Postfix Expression: " << postfixExpression << endl;

    return 0;
}

// Java program for infix to postfix conversion using stack
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class InfixToPostfix {
    public static String infixToPostfix(String infix) {
        Stack<Character> stack = new Stack<>();
        StringBuilder postfix = new StringBuilder();
        Map<Character, Integer> precedence = new HashMap<>();

        precedence.put('+', 1);
        precedence.put('-', 1);
        precedence.put('*', 2);
        precedence.put('/', 2);

        for (char c : infix.toCharArray()) {
            if (Character.isLetterOrDigit(c))
                postfix.append(c);
            else if (c == '(')
                stack.push(c);
            else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(')
                    postfix.append(stack.pop());
                stack.pop();
            } else {
                while (!stack.isEmpty() && precedence.getOrDefault(c, 0) <= precedence.getOrDefault(stack.peek(), 0))
                    postfix.append(stack.pop());
                stack.push(c);
            }
        }

        while (!stack.isEmpty())
            postfix.append(stack.pop());

        return postfix.toString();
    }

    public static void main(String[] args) {
        String infixExpression = "a+b*c-(d/e+f*g*h)";
        String postfixExpression = infixToPostfix(infixExpression);
        System.out.println("Infix Expression: " + infixExpression);
        System.out.println("Postfix Expression: " + postfixExpression);
    }
}

# Python code for infix to postfix conversion using stack
def infix_to_postfix(infix):
stack = []
postfix = ""
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}

for c in infix:
    if c.isalnum():
        postfix += c
    elif c == '(':
        stack.append(c)
    elif c == ')':
        while stack and stack[-1] != '(':
            postfix += stack.pop()
        stack.pop()
    else:
        while stack and precedence.get(c, 0) <= precedence.get(stack[-1], 0):
            postfix += stack.pop()
        stack.append(c)

while stack:
    postfix += stack.pop()

return postfix


# Example usage
infix_expression = "a+b*c-(d/e+f*g*h)"
postfix_expression = infix_to_postfix(infix_expression)
print("Infix Expression:", infix_expression)
print("Postfix Expression:", postfix_expression)

// C-Sharp Code for infix to postfix conversion using stack
using System;
using System.Collections.Generic;

public class InfixToPostfix {
    public static string InfixToPostfix(string infix) {
        Stack<char> stack = new Stack<char>();
        System.Text.StringBuilder postfix = new System.Text.StringBuilder();
        Dictionary<char, int> precedence = new Dictionary<char, int> {
            { '+', 1 },
            { '-', 1 },
            { '*', 2 },
            { '/', 2 }
        };

        foreach (char c in infix) {
            if (char.IsLetterOrDigit(c))
                postfix.Append(c);
            else if (c == '(')
                stack.Push(c);
            else if (c == ')') {
                while (stack.Count > 0 && stack.Peek() != '(')
                    postfix.Append(stack.Pop());
                stack.Pop();
            } else {
                while (stack.Count > 0 && precedence.GetValueOrDefault(c, 0) <= precedence.GetValueOrDefault(stack.Peek(), 0))
                    postfix.Append(stack.Pop());
                stack.Push(c);
            }
        }

        while (stack.Count > 0)
            postfix.Append(stack.Pop());

        return postfix.ToString();
    }

    public static void Main() {
        string infixExpression = "a+b*c-(d/e+f*g*h)";
        string postfixExpression = InfixToPostfix(infixExpression);
        Console.WriteLine("Infix Expression: " + infixExpression);
        Console.WriteLine("Postfix Expression: " + postfixExpression);
    }
}
Output:
Infix Expression: a+b*c-(d/e+f*g*h)
Postfix Expression: abc*+de/fg*h*+-
  • Time Complexity: The time complexity of the code is O(N), where N is the length of the input infix expression.
  • Space Complexity: The space complexity of the code is O(N).

⚡ Please share your valuable feedback and suggestion in the comment section below or you can send us an email on our offical email id ✉ algolesson@gmail.com. You can also support our work by buying a cup of coffee ☕ for us.

Similar Posts

No comments:

Post a Comment


CLOSE ADS
CLOSE ADS