



from __future__ import annotations

import sys
from collections import deque
from typing import Generic, TypeVar

lowerCAmelCase__					  =  TypeVar('''T''')

class 				snake_case__(Generic[T]      ):

     """simple docstring"""






     lowercase_								=		4_2  # Cache store of keys
     lowercase_								=		4_2  # References of the keys in cache
     lowercase_								=		1_0  # Maximum capacity of cache







     def __init__(							self :     List[Any]				,       SCREAMING_SNAKE_CASE :     int					):
         lowercase__					:   List[str]													=					deque()
         lowercase__					:   List[str]													=					set()
         if not n:
             lowercase__					:   List[str]													=					sys.maxsize
         elif n < 0:
             raise ValueError("n should be an integer greater than 0."					)
         else:
             lowercase__					:   List[Any]													=					n







     def 			snake_case					(							self :     List[str]				,       SCREAMING_SNAKE_CASE :     T					):
         if x not in self.key_reference:
             if len(self.dq_store					) == LRUCache._MAX_CAPACITY:
                 lowercase__					:   List[Any]													=					self.dq_store.pop()
                 self.key_reference.remove(SCREAMING_SNAKE_CASE					)
         else:
             self.dq_store.remove(SCREAMING_SNAKE_CASE					)

         self.dq_store.appendleft(SCREAMING_SNAKE_CASE					)
         self.key_reference.add(SCREAMING_SNAKE_CASE					)







     def 			snake_case					(							self :     Any					):
         for k in self.dq_store:
             print(SCREAMING_SNAKE_CASE					)







     def __repr__(							self :     Union[str, Any]					):
         return f"""LRUCache({self._MAX_CAPACITY}) => {list(self.dq_store					)}"""


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    lowerCAmelCase__					  =  LRUCache(4)
    lru_cache.refer('''A''')
    lru_cache.refer(2)
    lru_cache.refer(3)
    lru_cache.refer('''A''')
    lru_cache.refer(4)
    lru_cache.refer(5)
    lru_cache.display()

    print(lru_cache)
    assert str(lru_cache) == "LRUCache(4) => [5, 4, 'A', 3]"









def  __lowerCamelCase (       lowerCamelCase__						):

				"""simple docstring"""


				lowercase__					:   Union[str, Any]													=					[]
				lowercase__					:   Tuple													=					[]
				lowercase__					:   Any													=					{
				    "^": 3,
				    "*": 2,
				    "/": 2,
				    "%": 2,
				    "+": 1,
				    "-": 1,
				}  # Priority of each operator
				lowercase__					:   Any													=					len(lowerCamelCase__						) if (len(lowerCamelCase__						) > 7) else 7

				# Print table header for output
				print(
				    "Symbol".center(8						)					,			"Stack".center(lowerCamelCase__						)					,			"Postfix".center(lowerCamelCase__						)					,			sep=" | "					,			)
				print("-" * (print_width * 3 + 7)						)

				for x in infix:
								if x.isalpha() or x.isdigit():
												post_fix.append(lowerCamelCase__						)  # if x is Alphabet / Digit, add it to Postfix
								elif x == "(":
												stack.append(lowerCamelCase__						)  # if x is "(" push to Stack
								elif x == ")":  # if x is ")" pop stack until "(" is encountered
												while stack[-1] != "(":
																post_fix.append(stack.pop()						)  # Pop stack & add the content to Postfix
												stack.pop()
								else:
												if len(lowerCamelCase__						) == 0:
																stack.append(lowerCamelCase__						)  # If stack is empty, push x to stack
												else:  # while priority of x is not > priority of element in the stack
																while len(lowerCamelCase__						) > 0 and priority[x] <= priority[stack[-1]]:
																				post_fix.append(stack.pop()						)  # pop stack & add to Postfix
																stack.append(lowerCamelCase__						)  # push x to stack

								print(
								    x.center(8						)					,			("".join(lowerCamelCase__						)).ljust(lowerCamelCase__						)					,			("".join(lowerCamelCase__						)).ljust(lowerCamelCase__						)					,			sep=" | "					,			)  # Output in tabular format

				while len(lowerCamelCase__						) > 0:  # while stack is not empty
								post_fix.append(stack.pop()						)  # pop stack & add to Postfix
								print(
								    " ".center(8						)					,			("".join(lowerCamelCase__						)).ljust(lowerCamelCase__						)					,			("".join(lowerCamelCase__						)).ljust(lowerCamelCase__						)					,			sep=" | "					,			)  # Output in tabular format

				return "".join(lowerCamelCase__						)  # return Postfix as str


def  __lowerCamelCase (       lowerCamelCase__						):

				"""simple docstring"""


				lowercase__					:   Optional[int]													=					list(infix[::-1]						)  # reverse the infix equation

				for i in range(len(lowerCamelCase__						)						):
								if infix[i] == "(":
												lowercase__					:   Tuple													=					")"  # change "(" to ")"
								elif infix[i] == ")":
												lowercase__					:   Optional[Any]													=					"("  # change ")" to "("

				return (infix_2_postfix("".join(lowerCamelCase__						)						))[
				    ::-1
				]  # call infix_2_postfix on Infix, return reverse of Postfix


if __name__ == "__main__":
				lowerCAmelCase__					  =  input('''\nEnter an Infix Equation = ''')  # Input an Infix equation
				lowerCAmelCase__					  =  ''''''.join(Infix.split())  # Remove spaces from the input
				print('''\n\t''', Infix, '''(Infix) -> ''', infix_2_prefix(Infix), '''(Prefix)''')




