




def 			lowerCamelCase_		(       UpperCamelCase__				:      List[Any]      )     ->       Optional[int]:





				"""simple docstring"""


				__lowerCamelCase		       =    []
				__lowerCamelCase		       =    []
				__lowerCamelCase		       =    {
				    '^': 3,
				    '*': 2,
				    '/': 2,
				    '%': 2,
				    '+': 1,
				    '-': 1,
				}  # Priority of each operator
				__lowerCamelCase		       =    len(UpperCamelCase__      ) if (len(UpperCamelCase__      ) > 7) else 7

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

				for x in infix:
								if x.isalpha() or x.isdigit():
												post_fix.append(UpperCamelCase__      )  # if x is Alphabet / Digit, add it to Postfix
								elif x == "(":
												stack.append(UpperCamelCase__      )  # 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(UpperCamelCase__      ) == 0:
																stack.append(UpperCamelCase__      )  # If stack is empty, push x to stack
												else:  # while priority of x is not > priority of element in the stack
																while len(UpperCamelCase__      ) > 0 and priority[x] <= priority[stack[-1]]:
																				post_fix.append(stack.pop()      )  # pop stack & add to Postfix
																stack.append(UpperCamelCase__      )  # push x to stack

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

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

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







def 			lowerCamelCase_		(       UpperCamelCase__				:      Union[str, Any]      )     ->       Tuple:





				"""simple docstring"""


				__lowerCamelCase		       =    list(infix[::-1]      )  # reverse the infix equation

				for i in range(len(UpperCamelCase__      )      ):
								if infix[i] == "(":
												__lowerCamelCase		       =    ')'  # change "(" to ")"
								elif infix[i] == ")":
												__lowerCamelCase		       =    '('  # change ")" to "("

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


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








class     __lowerCAmelCase :

			"""simple docstring"""







			def __init__(      self							)    ->      Any:



							'''simple docstring'''
							__lowerCamelCase		       =    0
							__lowerCamelCase		       =    0
							__lowerCamelCase		       =    {}


			def       lowercase_    (      self			,						lowerCamelCase__							)    ->      Tuple:



							'''simple docstring'''
							if vertex not in self.adjacency:
											__lowerCamelCase		       =    {}
											self.num_vertices += 1


			def       lowercase_    (      self			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__							)    ->      str:



							'''simple docstring'''
							self.add_vertex(lowerCamelCase__							)
							self.add_vertex(lowerCamelCase__							)

							if head == tail:
											return

							__lowerCamelCase		       =    weight
							__lowerCamelCase		       =    weight


			def       lowercase_    (      self							)    ->      List[str]:



							'''simple docstring'''
							__lowerCamelCase		       =    self.get_edges()
							for edge in edges:
											__lowerCamelCase       ,						__lowerCamelCase       ,						__lowerCamelCase		       =    edge
											edges.remove((tail, head, weight)							)
							for i in range(len(lowerCamelCase__							)							):
											__lowerCamelCase		       =    list(edges[i]							)

							edges.sort(key=lambda lowerCamelCase__							: e[2]							)
							for i in range(len(lowerCamelCase__							) - 1							):
											if edges[i][2] >= edges[i + 1][2]:
															__lowerCamelCase		       =    edges[i][2] + 1
							for edge in edges:
											__lowerCamelCase       ,						__lowerCamelCase       ,						__lowerCamelCase		       =    edge
											__lowerCamelCase		       =    weight
											__lowerCamelCase		       =    weight


			def __str__(      self							)    ->      Union[str, Any]:



							'''simple docstring'''
							__lowerCamelCase		       =    ''
							for tail in self.adjacency:
											for head in self.adjacency[tail]:
															__lowerCamelCase		       =    self.adjacency[head][tail]
															string += f"""{head} -> {tail} == {weight}\n"""
							return string.rstrip('\n'							)


			def       lowercase_    (      self							)    ->      Optional[Any]:



							'''simple docstring'''
							__lowerCamelCase		       =    []
							for tail in self.adjacency:
											for head in self.adjacency[tail]:
															output.append((tail, head, self.adjacency[head][tail])							)
							return output


			def       lowercase_    (      self							)    ->      List[Any]:



							'''simple docstring'''
							return self.adjacency.keys()


			@staticmethod
			def       lowercase_    (      lowerCamelCase__=None			,						lowerCamelCase__=None							)    ->      str:



							'''simple docstring'''
							__lowerCamelCase		       =    Graph()
							if vertices is None:
											__lowerCamelCase		       =    []
							if edges is None:
											__lowerCamelCase		       =    []
							for vertex in vertices:
											g.add_vertex(lowerCamelCase__							)
							for edge in edges:
											g.add_edge(*lowerCamelCase__							)
							return g







			class     __lowerCAmelCase :

						"""simple docstring"""







						def __init__(      self							)    ->      Tuple:



										'''simple docstring'''
										__lowerCamelCase		       =    {}
										__lowerCamelCase		       =    {}


						def __len__(      self							)    ->      Tuple:



										'''simple docstring'''
										return len(self.parent							)


						def       lowercase_    (      self			,						lowerCamelCase__							)    ->      List[Any]:



										'''simple docstring'''
										if item in self.parent:
														return self.find(lowerCamelCase__							)

										__lowerCamelCase		       =    item
										__lowerCamelCase		       =    0
										return item


						def       lowercase_    (      self			,						lowerCamelCase__							)    ->      List[str]:



										'''simple docstring'''
										if item not in self.parent:
														return self.make_set(lowerCamelCase__							)
										if item != self.parent[item]:
														__lowerCamelCase		       =    self.find(self.parent[item]							)
										return self.parent[item]






						def       lowercase_    (      self			,						lowerCamelCase__			,						lowerCamelCase__							)    ->      int:



										'''simple docstring'''
										__lowerCamelCase		       =    self.find(lowerCamelCase__							)
										__lowerCamelCase		       =    self.find(lowerCamelCase__							)

										if roota == roota:
														return roota

										if self.rank[roota] > self.rank[roota]:
														__lowerCamelCase		       =    roota
														return roota

										if self.rank[roota] < self.rank[roota]:
														__lowerCamelCase		       =    roota
														return roota

										if self.rank[roota] == self.rank[roota]:
														self.rank[roota] += 1
														__lowerCamelCase		       =    roota
														return roota
										return None




			@staticmethod
			def       lowercase_    (      lowerCamelCase__							)    ->      str:



							'''simple docstring'''
							__lowerCamelCase		       =    graph.num_vertices

							__lowerCamelCase		       =    Graph.UnionFind()
							__lowerCamelCase		       =    []
							while num_components > 1:
											__lowerCamelCase		       =    {}
											for vertex in graph.get_vertices():
															__lowerCamelCase		       =    -1

											__lowerCamelCase		       =    graph.get_edges()
											for edge in edges:
															__lowerCamelCase       ,						__lowerCamelCase       ,						__lowerCamelCase		       =    edge
															edges.remove((tail, head, weight)							)
											for edge in edges:
															__lowerCamelCase       ,						__lowerCamelCase       ,						__lowerCamelCase		       =    edge
															__lowerCamelCase		       =    union_find.find(lowerCamelCase__							)
															__lowerCamelCase		       =    union_find.find(lowerCamelCase__							)
															if seta != seta:
																			if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
																							__lowerCamelCase		       =    [head, tail, weight]

																			if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
																							__lowerCamelCase		       =    [head, tail, weight]
											for vertex in cheap_edge:
															if cheap_edge[vertex] != -1:
																			__lowerCamelCase       ,						__lowerCamelCase       ,						__lowerCamelCase		       =    cheap_edge[vertex]
																			if union_find.find(lowerCamelCase__							) != union_find.find(lowerCamelCase__							):
																							union_find.union(lowerCamelCase__			,						lowerCamelCase__							)
																							mst_edges.append(cheap_edge[vertex]							)
																							__lowerCamelCase		       =    num_components - 1
							__lowerCamelCase		       =    Graph.build(edges=lowerCamelCase__							)
							return mst


