by: Jayson McleodPosted on

In the world of computer science and programming, achieving optimal efficiency and precision reigns supreme. Algorithms hold a pivotal role in realizing these objectives, and among the illustrious algorithms that have demonstrated their enduring value, the Shunting Yard Algorithm shines brightly. Originally conceived by the brilliant mind of Edsger W. Dijkstra during the 1960s, this ingenious methodology furnishes an efficient means to parse mathematical expressions, rendering it an indispensable tool for constructing a wide array of applications, ranging from calculators to compilers.

Within the confines of this exposition, we embark on an expedition to demystify the inner workings of the Shunting Yard Algorithm and delve into the intricacies of its Python implementation. Let us now plunge into the depths of knowledge and uncover the concealed facets of this time-honored algorithm, thereby uncovering how it can elevate your coding pursuits.

The Shunting Yard Algorithm: A Deep Dive

The Shunting Yard Algorithm is a renowned method developed for parsing mathematical expressions. Its origin can be credited to the brilliant computer scientist, Edsger Dijkstra. The intriguing name of this algorithm, “Shunting Yard,” is derived from its mechanism that employs a stack to methodically rearrange the operators and operands. This process mirrors the systematic realignment of train cars in a railway shunting yard.

Overview:

The core essence of this algorithm is its ability to convert infix notation (common arithmetic notation, e.g., “A + B”) into postfix notation (or Reverse Polish Notation, e.g., “A B +”), making the expression easier to evaluate. To achieve this, the algorithm uses two central components: a stack for operators and another for values.

Python Implementation:

To gain a more practical insight into this algorithm, let’s delve into a Python-based implementation:

import re

def is_number(s):
    """
    Determines if a given string represents a number.
    """
    try:
        int(s)
        return True
    except ValueError:
        return False

def is_name(s):
    """
    Determines if a string matches a regular alphanumeric pattern.
    """
    return bool(re.match("\w+", s))

def peek(stack):
    """
    Peeks at the top element of a stack without popping it.
    """
    return stack[-1] if stack else None

def apply_operator(operators, values):
    """
    Applies an operator to the two most recent values in the values stack.
    """
    operator = operators.pop()
    right = values.pop()
    left = values.pop()
    formula = "{0}{1}{2}".format(left, operator, right)
    values.append(eval(formula))

def greater_precedence(op1, op2):
    """
    Determines if the precedence of op1 is greater than op2.
    """
    precedences = {'+' : 0, '-' : 0, '*' : 1, '/' : 1}
    return precedences[op1] > precedences[op2]

def evaluate(expression):
    """
    Evaluates a mathematical expression using the Shunting Yard Algorithm.
    """
    tokens = re.findall("[+/*()-]|\d+", expression)
    values, operators = [], []
    for token in tokens:
        if is_number(token):
            values.append(int(token))
        elif token == '(':
            operators.append(token)
        elif token == ')':
            while peek(operators) and peek(operators) != '(':
                apply_operator(operators, values)
            operators.pop() # Discard the '('
        else:
            while peek(operators) and peek(operators) not in "()" and greater_precedence(peek(operators), token):
                apply_operator(operators, values)
            operators.append(token)
    while peek(operators):
        apply_operator(operators, values)
    return values[0]

# Example demonstration:
def main():
    expression = '((20 - 10 ) * (30 - 20) / 10 + 10 ) * 2'
    print("Shunting Yard Algorithm Result:", evaluate(expression))
    print("Native Python Evaluation:", eval(expression))

if __name__ == '__main__':
    main()

Output:

Shunting Yard Algorithm Result: 40
Native Python Evaluation: 40

In this implementation, several helper functions play a vital role. Functions like is_number and is_name assist in token classification. The peek function enables us to view the top element of a stack without altering its content. The apply_operator function demonstrates the application of it, and greater_precedence determines the hierarchy between two operators.

By running the provided example, one can observe that the Shunting Yard Algorithm’s result and Python’s native evaluation yield identical outputs, affirming the algorithm’s correctness. Also, learn how to effortlessly retrieve the current URL using selenium!

Conclusion

The Shunting Yard Algorithm stands as a testament to the ingenuity in computer science, brilliantly conceptualized by Edsger Dijkstra. Its primary objective of parsing mathematical expressions is elegantly achieved by transforming the commonly used infix notation to the postfix notation, simplifying computational procedures. The Python implementation not only provides a tangible glimpse into the algorithm’s inner workings but also showcases its precision, as it consistently matches results obtained from Python’s native evaluators. Whether one is a novice programmer or an expert, the algorithm offers valuable insights into the realm of data structures and algorithmic problem-solving. As with many classic algorithms, its relevance persists, offering solutions to contemporary challenges and emphasizing the timeless nature of foundational knowledge in the ever-evolving field of computer science.

Leave a Reply