Source code for match.shunting_yard
"""
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:**
* Computerphile - `Reverse Polish Notation and The Stack
<https://www.youtube.com/watch?v=7ha78yWRDlE>`_
* Wikipedia - `Reverse Polish notation
<https://en.wikipedia.org/wiki/Reverse_Polish_notation>`_
"""
[docs]def shunt(infix: str) -> str:
"""
Converts a string `infix` from infix notation to postfix notation.
**Example:**
::
>>> shunt("(a|b).c*")
'ab|c*.'
:param infix: An expression written in infix notation.
:return: The infix expression converted to postfix notation.
:raises ValueError: If the infix expression has unbalanced parentheses.
"""
# Make sure any brackets in the infix expression are balanced
if not has_balanced_parens(infix):
raise ValueError("`infix` has unbalanced parentheses")
opers = [] # Operator stack
postfix = [] # Output list
# Dictionary of operator precedence
prec = {
'*': 100,
'+': 100,
'?': 100,
'.': 80,
'|': 60,
'(': 40,
')': 20
}
infix = list(infix)[::-1] # Convert infix string to a stack/list
while infix:
c = infix.pop()
if c in prec:
if c == '(':
opers.append(c)
elif c == ')':
# Keep popping until an open bracket is found
while opers[-1] != '(':
postfix.append(opers.pop())
del opers[-1] # Delete the open bracket
else:
# Push any operators with higher precedence to the output
while opers and prec[c] < prec[opers[-1]]:
postfix.append(opers.pop())
opers.append(c)
else:
postfix.append(c) # Push operand to the output
postfix.extend(opers[::-1]) # Append all the remaining operators
return ''.join(postfix) # Return output list as a string
[docs]def has_balanced_parens(exp: str) -> bool:
"""
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
:param exp: The expression to check.
:return: `True` if the parentheses are balanced, `False` otherwise.
"""
# Use a stack to determine if the expression is balanced.
# Ref: https://youtu.be/HJOnJU77EUs?t=75 [1:15 - 2:47]
paren_stack = []
for e in exp:
if e == '(':
paren_stack.append(e)
elif e == ')':
try:
paren_stack.pop()
except IndexError:
return False
return len(paren_stack) == 0 # Only `True` if `paren_stack` is empty