infix_to_postfix_conversion.py

"""
https://en.wikipedia.org/wiki/Infix_notation
https://en.wikipedia.org/wiki/Reverse_Polish_notation
https://en.wikipedia.org/wiki/Shunting-yard_algorithm
"""

fromtypingimportLiteral

from .balanced_parenthesesimportbalanced_parentheses
from .stackimportStack

PRECEDENCES: dict[str, int] = {
"+": 1,
"-": 1,
"*": 2,
"/": 2,
"^": 3,
}
ASSOCIATIVITIES: dict[str, Literal["LR", "RL"]] = {
"+": "LR",
"-": "LR",
"*": "LR",
"/": "LR",
"^": "RL",
}


defprecedence(char: str) ->int:
"""
 Return integer value representing an operator's precedence, or
 order of operation.
 https://en.wikipedia.org/wiki/Order_of_operations
 """
returnPRECEDENCES.get(char, -1)


defassociativity(char: str) ->Literal["LR", "RL"]:
"""
 Return the associativity of the operator `char`.
 https://en.wikipedia.org/wiki/Operator_associativity
 """
returnASSOCIATIVITIES[char]


definfix_to_postfix(expression_str: str) ->str:
"""
 >>> infix_to_postfix("(1*(2+3)+4))")
 Traceback (most recent call last):
 ...
 ValueError: Mismatched parentheses
 >>> infix_to_postfix("")
 ''
 >>> infix_to_postfix("3+2")
 '3 2 +'
 >>> infix_to_postfix("(3+4)*5-6")
 '3 4 + 5 * 6 -'
 >>> infix_to_postfix("(1+2)*3/4-5")
 '1 2 + 3 * 4 / 5 -'
 >>> infix_to_postfix("a+b*c+(d*e+f)*g")
 'a b c * + d e * f + g * +'
 >>> infix_to_postfix("x^y/(5*z)+2")
 'x y ^ 5 z * / 2 +'
 >>> infix_to_postfix("2^3^2")
 '2 3 2 ^ ^'
 """
ifnotbalanced_parentheses(expression_str):
raiseValueError("Mismatched parentheses")
stack: Stack[str] =Stack()
postfix= []
forcharinexpression_str:
ifchar.isalpha() orchar.isdigit():
postfix.append(char)
elifchar=="(":
stack.push(char)
elifchar==")":
whilenotstack.is_empty() andstack.peek() !="(":
postfix.append(stack.pop())
stack.pop()
else:
whileTrue:
ifstack.is_empty():
stack.push(char)
break

char_precedence=precedence(char)
tos_precedence=precedence(stack.peek())

ifchar_precedence>tos_precedence:
stack.push(char)
break
ifchar_precedence<tos_precedence:
postfix.append(stack.pop())
continue
# Precedences are equal
ifassociativity(char) =="RL":
stack.push(char)
break
postfix.append(stack.pop())

whilenotstack.is_empty():
postfix.append(stack.pop())
return" ".join(postfix)


if__name__=="__main__":
fromdoctestimporttestmod

testmod()
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))