precedence = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2}


def infix2postfix(infix: str) -> str:
	ops = []
	postfix = []

	for c in infix:
		if c.isdigit():
			postfix.append(c)
		elif c == '(':
			ops.append(c)
		elif c == ')':
			while ops and ops[-1] != '(':
				postfix.append(ops.pop())
			ops.pop()
		else:
			while ops and precedence[ops[-1]] >= precedence[c]:
				postfix.append(ops.pop())
			ops.append(c)

	while ops:
		postfix.append(ops.pop())

	return ''.join(postfix)

def cal_postfix(postfix: str) -> int:
	stack = []

	for c in postfix:
		if c.isdigit():
			stack.append(int(c))
		else:
			b = stack.pop()
			a = stack.pop()
			stack.append(cal_op(c, a, b))  # 根据c属于什么op(+-/*)计算

	return stack.pop()

def infix2prefix(infix: str) -> str:
	infix = [{"(": ")", ")": "("}.get(c, c) for c in infix[::-1]]

	ops = []
	prefix = []

	for c in infix:
		if c.isdigit():
			prefix.append(c)
		elif c == '(':
			ops.append(c)
		elif c == ')':
			while ops and ops[-1] != '(':
				prefix.append(ops.pop())
			ops.pop()
		else:
			# 注意反转后是右结合，因此是>而不是>=
			while ops and precedence[ops[-1]] > precedence[c]:
				prefix.append(ops.pop())
			ops.append(c)

	while ops:
		prefix.append(ops.pop())

	return ''.join(reversed(prefix))

def cal_prefix(prefix: str) -> int:
	stack = []

	for c in reversed(postfix):
		if c.isdigit():
			stack.append(int(c))
		else:
			a = stack.pop()
			b = stack.pop()
			stack.append(cal_op(c, a, b))

	return stack.pop()

class CircularQueue:
	def __init__(self, size: int):
		self.size = size
		self.queue = [None] * size
		self.front = 0
		self.rear = 0

	def is_empty(self):
		return self.front == self.rear

	def is_full(self):
		return self.front == self._next(self.rear)

	def enqueue(self, item: Any):
		self.queue[self.rear] = item
		self.rear = self._next(self.rear)

	def dequeue(self) -> Any:
		item = self.peek()
		self.front = self._next(self.front)
		return item

	def peek(self) -> Any:
		return self.queue(self.front)

	def _next(self, x):
		return (x + 1) % self.size