92 lines
2.8 KiB
Python
92 lines
2.8 KiB
Python
from __future__ import annotations
|
|
|
|
PRECEDENCE = {"^": 4, "*": 3, "/": 3, "+": 2, "-": 2}
|
|
ASSOCIATIVITY = {"^": 1, "*": 0, "/": 0, "+": 0, "-": 0}
|
|
|
|
|
|
class Node:
|
|
def __init__(self, x: Node | str, op: str, y: Node | str | None = None):
|
|
self.precedence = PRECEDENCE[op]
|
|
self.right_associative = ASSOCIATIVITY[op]
|
|
self.op = op
|
|
self.x, self.y = x, y
|
|
|
|
def __str__(self):
|
|
# easy case, Node is unary
|
|
if self.y is None:
|
|
return "%s(%s)" % (self.op, str(self.x))
|
|
|
|
# determine left side string
|
|
str_y = str(self.y)
|
|
if (
|
|
self.y < self
|
|
or (self.y == self and self.right_associative)
|
|
or (str_y[0] == "-" and self.right_associative)
|
|
):
|
|
str_y = "(%s)" % str_y
|
|
|
|
# determine right side string and operator
|
|
str_x = str(self.x)
|
|
str_op = self.op
|
|
if self.op == "+" and not isinstance(self.x, Node) and str_x[0] == "-":
|
|
str_x = str_x[1:]
|
|
str_op = "-"
|
|
elif self.op == "-" and not isinstance(self.x, Node) and str_x[0] == "-":
|
|
str_x = str_x[1:]
|
|
str_op = "+"
|
|
elif self.x < self or (
|
|
self.x == self
|
|
and not self.right_associative
|
|
and getattr(self.x, "op", 1) != getattr(self, "op", 2)
|
|
):
|
|
str_x = "(%s)" % str_x
|
|
|
|
return " ".join([str_y, str_op, str_x])
|
|
|
|
def __repr__(self):
|
|
return "Node(%s,%s,%s)" % (repr(self.x), repr(self.op), repr(self.y))
|
|
|
|
def __lt__(self, other: object) -> bool:
|
|
if isinstance(other, Node):
|
|
return self.precedence < other.precedence
|
|
return self.precedence < PRECEDENCE.get(str(other), 9)
|
|
|
|
def __gt__(self, other: object) -> bool:
|
|
if isinstance(other, Node):
|
|
return self.precedence > other.precedence
|
|
return self.precedence > PRECEDENCE.get(str(other), 9)
|
|
|
|
def __eq__(self, other: object) -> bool:
|
|
if isinstance(other, Node):
|
|
return self.precedence == other.precedence
|
|
return self.precedence > PRECEDENCE.get(str(other), 9)
|
|
|
|
|
|
def rpn_to_infix(input: str, *, VERBOSE: bool = False):
|
|
"""Convert `input` in rpn notation to infix notation."""
|
|
if VERBOSE:
|
|
print("TOKEN STACK")
|
|
|
|
stack: list[Node | str] = []
|
|
for token in input.replace("^", "^").split():
|
|
if token in PRECEDENCE:
|
|
stack.append(Node(stack.pop(), token, stack.pop()))
|
|
else:
|
|
stack.append(token)
|
|
|
|
if VERBOSE:
|
|
print(token + " " * (7 - len(token)) + repr(stack))
|
|
|
|
return str(stack[0])
|
|
|
|
|
|
if __name__ == "__main__":
|
|
EXAMPLES = [
|
|
"3 4 2 * 1 5 - 2 3 ^ ^ / +",
|
|
"1 2 + 3 4 + ^ 5 6 + ^",
|
|
]
|
|
|
|
for example in EXAMPLES:
|
|
print(f"Input: {example}")
|
|
print(f"Result: {rpn_to_infix(example, VERBOSE=True)}")
|
|
print()
|