match.shunting_yard module

Module containing an implementation of Dijkstra’s Shunting Yard Algorithm for converting an infix expression to postfix, also known as Reverse Polish notation (RPN), a mathematical notation in which operators follow their operands.

Expressions written in Reverse Polish can be easily interpreted by utilising a stack, and are more efficient than the infix equivalent as only a single read over the expression is required in order to fully evaluate it, reducing execution time & computer memory access. Also, since the order of operations is determined solely by each operator’s position in the expression, RPN does not use parentheses to specify the precedence of operators. Hence, they are omitted in the output.

References & Further Info:
match.shunting_yard.has_balanced_parens(exp: str) → bool[source]

Checks if the parentheses in the given expression exp are balanced, that is, if each opening parenthesis is matched by a corresponding closing parenthesis.

Example:

>>> has_balanced_parens("(((a * b) + c)")
False
Parameters:exp – The expression to check.
Returns:True if the parentheses are balanced, False otherwise.
match.shunting_yard.shunt(infix: str) → str[source]

Converts a string infix from infix notation to postfix notation.

Example:

>>> shunt("(a|b).c*")
'ab|c*.'
Parameters:infix – An expression written in infix notation.
Returns:The infix expression converted to postfix notation.
Raises:ValueError – If the infix expression has unbalanced parentheses.