infix to postfix conversion Algorithm

The infix to postfix conversion algorithm is a widely used technique in computer science to transform an infix expression into an equivalent postfix expression, also known as Reverse Polish Notation (RPN). Infix notation is the standard arithmetic and logical expression format where operators are written between the operands, such as A+B or A*B. On the other hand, postfix notation places the operators after the operands, like AB+ or AB*. The postfix notation is advantageous as it eliminates the need for parentheses and follows a clear precedence order, making it easier for computers to evaluate expressions. The infix to postfix conversion helps in simplifying complex expressions and reducing the computation overhead for the system. The algorithm for the infix to postfix conversion utilizes a stack data structure to store and manage the operators during the conversion process. The algorithm scans the input infix expression from left to right, considering one character at a time. If the character is an operand, it is directly appended to the postfix expression. If the character is an operator or a parenthesis, the stack comes into play. When an operator is encountered, the algorithm compares its precedence with the operators already present in the stack. If the current operator has a higher precedence, it is pushed onto the stack; otherwise, the operators with equal or higher precedence are popped from the stack and appended to the postfix expression until a lower precedence operator or an open parenthesis is found. For parentheses, the open parenthesis is pushed onto the stack, and when a closing parenthesis is encountered, the operators are popped and appended to the postfix expression until the corresponding open parenthesis is found. Once the entire infix expression is scanned, any remaining operators in the stack are popped and appended to the postfix expression. The resulting postfix expression can then be evaluated using a stack-based algorithm or interpreted by programming languages and calculators.
import string

from .stack import Stack

__author__ = "Omkar Pathak"


def is_operand(char):
    return char in string.ascii_letters or char in string.digits


def precedence(char):
    """ Return integer value representing an operator's precedence, or
    order of operation.

    https://en.wikipedia.org/wiki/Order_of_operations
    """
    dictionary = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
    return dictionary.get(char, -1)


def infix_to_postfix(expression):
    """ Convert infix notation to postfix notation using the Shunting-yard
    algorithm.

    https://en.wikipedia.org/wiki/Shunting-yard_algorithm
    https://en.wikipedia.org/wiki/Infix_notation
    https://en.wikipedia.org/wiki/Reverse_Polish_notation
    """
    stack = Stack(len(expression))
    postfix = []
    for char in expression:
        if is_operand(char):
            postfix.append(char)
        elif char not in {"(", ")"}:
            while not stack.is_empty() and precedence(char) <= precedence(stack.peek()):
                postfix.append(stack.pop())
            stack.push(char)
        elif char == "(":
            stack.push(char)
        elif char == ")":
            while not stack.is_empty() and stack.peek() != "(":
                postfix.append(stack.pop())
            # Pop '(' from stack. If there is no '(', there is a mismatched
            # parentheses.
            if stack.peek() != "(":
                raise ValueError("Mismatched parentheses")
            stack.pop()
    while not stack.is_empty():
        postfix.append(stack.pop())
    return " ".join(postfix)


if __name__ == "__main__":
    expression = "a+b*(c^d-e)^(f+g*h)-i"

    print("Infix to Postfix Notation demonstration:\n")
    print("Infix notation: " + expression)
    print("Postfix notation: " + infix_to_postfix(expression))

LANGUAGE:

DARK MODE: