Given an infix expression in the form of string str. Convert this infix expression to postfix expression.
	Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands.
	Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands.
	Note: The order of precedence is: ^ greater than * equals to / greater than + equals to -. 
Example 1:
Input: str = "a+b*(c^d-e)^(f+g*h)-i"
Output: abcd^e-fgh*+^*+i-
Explanation:
After converting the infix expression 
into postfix expression, the resultant 
expression will be abcd^e-fgh*+^*+i-
Example 2:
Input: str = "A*(B+C)/D"
Output: ABC+*D/
Explanation:
After converting the infix expression 
into postfix expression, the resultant 
expression will be ABC+*D/
 
Your Task:
This is a function problem. You only need to complete the function infixToPostfix() that takes a string(Infix Expression) as a parameter and returns a string(postfix expression). The printing is done automatically by the driver code.
Expected Time Complexity: O(|str|).
Expected Auxiliary Space: O(|str|).
Constraints:
1 ≤ |str| ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3





class Solution:

    

    #Function to convert an infix expression to a postfix expression.

    def InfixtoPostfix(self, exp):

        #code here

Solutions:
class Solution:

	def check_operand(self, ch):
		return ch.isalpha() or ch.isdigit()

	def InfixtoPostfix(self, exp):
		output = ''
		stack = []
		precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
		for i in exp:
			if self.check_operand(i):
				output += i
			elif not stack:
				stack.append(i)
			elif i == '(':
				stack.append(i)
			elif i == ')':
				while stack and stack[-1] != '(':
					output += stack.pop()
				stack.pop()
			elif stack[-1] == '(' and (i == '+' or '-' or '*' or '/' or '^'):
				stack.append(i)
			elif precedence[i] > precedence[stack[-1]]:
				stack.append(i)
			else:
				while len(stack) != 0 and stack[-1] != '(' and (precedence[i] <= precedence[stack[-1]]):
					output += stack.pop()
				stack.append(i)
		while len(stack) != 0:
			output += stack.pop()
		return output


class Solution:

	def InfixtoPostfix(self, exp):

		def prec(ch):
			if ch == '^':
				return 3
			elif ch == '*' or ch == '/':
				return 2
			elif ch == '+' or ch == '-':
				return 1
			else:
				return 0
		st = []
		res = ''
		for i in exp:
			if i.isalnum():
				res += i
			elif i == '(':
				st.append(i)
			elif i == ')':
				while st[-1] != '(':
					res += st[-1]
					st.pop()
				st.pop()
			else:
				while st and prec(st[-1]) >= prec(i):
					res += st[-1]
					st.pop()
				st.append(i)
		while st:
			res += st[-1]
			st.pop()
		return res


class Stack:

	def __init__(self):
		self.stack = []

	def push(self, element):
		self.stack.append(element)

	def pop(self):
		return self.stack.pop(-1)

	def top(self):
		return self.stack[-1] if len(self.stack) > 0 else None

class Solution:

	def InfixtoPostfix(self, infix):
		infix = infix.replace(' ', '')
		d = {'^': 3, '$': 3, '/': 2, '*': 2, '+': 1, '-': 1}
		postfix = ''
		at = Stack()
		for i in infix:
			if i not in '^$/*+-)(':
				postfix += i
			elif (at.top() == None or at.top() == '(' or i == '(') and i != ')':
				at.push(i)
			elif i == ')':
				while at.top() != '(':
					postfix += at.pop()
				at.pop()
			elif d[at.top()] < d[i]:
				at.push(i)
			else:
				while at.top() != '(' and d[at.top()] >= d[i] and (at.top != None):
					postfix += at.pop()
					if at.top() == None:
						break
				at.push(i)
		while len(at.stack) > 0:
			postfix += at.pop()
		return postfix


from collections import deque

class Solution:

	def priority(self, op):
		if op == '^':
			return 3
		elif op in ['*', '/']:
			return 2
		elif op in ['+', '-']:
			return 1

	def InfixtoPostfix(self, s):
		operands = deque()
		operators = deque()
		for i in s:
			if i == '(':
				operators.append(i)
			elif i == ')':
				while operators[-1] != '(':
					v2 = operands.pop()
					v1 = operands.pop()
					op = operators.pop()
					res = v1 + v2 + op
					operands.append(res)
				operators.pop()
			elif i in ['^', '*', '/', '+', '-']:
				while len(operators) > 0 and operators[-1] != '(' and (self.priority(operators[-1]) >= self.priority(i)):
					v2 = operands.pop()
					v1 = operands.pop()
					op = operators.pop()
					res = v1 + v2 + op
					operands.append(res)
				operators.append(i)
			else:
				operands.append(i)
		while len(operators) > 0:
			v2 = operands.pop()
			v1 = operands.pop()
			op = operators.pop()
			res = v1 + v2 + op
			operands.append(res)
		return operands[-1]


class Solution:

	def InfixtoPostfix(self, exp):
		ans = ''

		def precedence(op):
			if op == '^':
				return 3
			elif op == '*' or op == '/':
				return 2
			elif op == '+' or op == '-':
				return 1
			else:
				return -1
		stack = []
		for i in range(len(exp)):
			op = exp[i]
			if exp[i] == '(':
				stack.append('(')
			elif exp[i] == ')':
				while stack[-1] != '(':
					ans += stack.pop()
				stack.pop()
			elif op == '^' or op == '*' or op == '+' or (op == '-') or (op == '/'):
				while len(stack) and precedence(exp[i]) <= precedence(stack[-1]):
					ans += stack.pop()
				stack.append(exp[i])
			else:
				ans += exp[i]
		while len(stack):
			ans += stack.pop()
		return ans


class Solution(object):

	def __init__(self):
		self.stack = []
		self.result = []

	def precedence(self, char):
		if char == '^':
			return 3
		elif char == '*' or char == '/':
			return 2
		elif char == '+' or char == '-':
			return 1
		else:
			return -1

	def isOperand(self, char):
		return char.isalnum()

	def notGreaterPrecedence(self, char):
		currOperator = self.precedence(char)
		topOperator = self.precedence(self.stack[-1])
		return topOperator >= currOperator

	def InfixtoPostfix(self, infix):
		for char in infix:
			if self.isOperand(char):
				self.result.append(char)
			elif char == '(':
				self.stack.append(char)
			elif char == ')':
				while self.stack and self.stack[-1] != '(':
					self.result.append(self.stack.pop())
				if self.stack:
					self.stack.pop()
			else:
				while self.stack and self.notGreaterPrecedence(char):
					self.result.append(self.stack.pop())
				self.stack.append(char)
		while self.stack:
			self.result.append(self.stack.pop())
		return ''.join(self.result)

	def infixToPrefix(self, infix):
		size = len(infix)
		infix = infix[::-1]
		for index in range(size):
			if infix[index] == '(':
				infix[index] = ')'
			elif infix[index] == ')':
				infix[index] = '('
		postfix = self.InfixtoPostfix(infix)
		prefix = postfix[::-1]
		return prefix


class Solution:

	def InfixtoPostfix(self, exp):
		s = []
		st = ''
		op = ['+', '-', '/', '*', '(', ')', '^']
		precedence = {'-': 1, '+': 1, '*': 2, '/': 2, '^': 3}
		for i in exp:
			if i not in op:
				st += i
			elif i == '(':
				s.append(i)
			elif i == ')':
				while s and s[-1] != '(':
					st += s.pop()
				s.pop()
			else:
				while s and s[-1] != '(' and (precedence[i] <= precedence[s[-1]]):
					st += s.pop()
				s.append(i)
		while s:
			st += s.pop()
		return st


class Solution:

	def InfixtoPostfix(self, exp):
		operators = set(['+', '-', '*', '/', '(', ')', '^'])
		power = {'-': 1, '+': 1, '/': 2, '*': 2, '^': 3}
		stack = []
		ans = ''
		for i in exp:
			if i not in operators:
				ans += i
			elif i == '(':
				stack.append('(')
			elif i == ')':
				while stack and stack[-1] != '(':
					ans += stack.pop()
				stack.pop()
			else:
				while stack and stack[-1] != '(' and (power[i] <= power[stack[-1]]):
					ans += stack.pop()
				stack.append(i)
		while stack:
			ans += stack.pop()
		return ans


from collections import deque

class Solution:

	def hasLowerPrec(self, o1: str, o2: str):
		val = {'+': 0, '-': 0, '*': 1, '/': 1, '^': 2}
		if o2 == '(':
			return False
		elif val[o1] <= val[o2]:
			return True
		else:
			return False

	def checkAssoc(self, o: str):
		val = {'+': 1, '-': 1, '*': 1, '/': 1, '^': 2}
		return val[o]

	def InfixtoPostfix(self, exp):
		s = deque()
		res = ''
		for c in exp:
			if c == '(':
				s.append(c)
			elif c == ')':
				while len(s) != 0 and s[-1] != '(':
					res += s.pop()
				if len(s) != 0 and s[-1] != '(':
					return -1
				else:
					s.pop()
			elif c in ['+', '-', '*', '/', '^']:
				while len(s) != 0 and self.hasLowerPrec(c, s[-1]):
					res += s.pop()
				s.append(c)
			else:
				res += c
		while len(s) != 0:
			res += s.pop()
		return res


class Solution:

	def InfixtoPostfix(self, exp):
		op = '-+*/^'
		bra = {'(', ')'}
		kmap = {}
		order = [1, 1, 2, 2, 3]
		for i in range(len(op)):
			kmap[op[i]] = order[i]
		sta = []
		ans = ''
		for ele in exp:
			if ele in kmap:
				if not sta:
					sta.append(ele)
				else:
					lastele = sta[-1]
					if lastele in bra:
						sta.append(ele)
					elif kmap[lastele] < kmap[ele]:
						sta.append(ele)
					else:
						while sta and sta[-1] != '(' and (kmap[lastele] >= kmap[ele]):
							le = sta.pop()
							ans += le
						sta.append(ele)
			elif ele in bra:
				if ele == '(':
					sta.append(ele)
				else:
					found = False
					while sta and (not found):
						let = sta.pop()
						if let == '(':
							found = True
						else:
							ans += let
			else:
				ans += ele
		while sta:
			ele = sta.pop()
			if ele in kmap:
				ans += ele
		return ans


class Solution:

	def InfixtoPostfix(self, exp):
		res = ''
		stack = []

		def prec(i):
			if i == '^':
				return 3
			elif i == '/' or i == '*':
				return 2
			elif i == '+' or i == '-':
				return 1
			else:
				return -1
		for i in exp:
			if i >= 'a' and i <= 'z' or (i >= 'A' and i <= 'Z') or (i >= '0' and i <= '9'):
				res += i
			elif i == '(':
				stack.append(i)
			elif i == ')':
				while len(stack) != 0 and stack[-1] != '(':
					res += stack.pop()
				if len(stack) != 0:
					stack.pop()
			else:
				while len(stack) != 0 and prec(stack[-1]) >= prec(i):
					res += stack.pop()
				stack.append(i)
		while len(stack) != 0:
			res += stack.pop()
		return res


class Solution:

	def InfixtoPostfix(self, exp):
		operator = {'+': 1, '-': 1, '*': 2, '/': 3, '^': 4}
		stack = []
		postfix = ''
		for i in exp:
			if i not in operator and i not in ['(', ')']:
				postfix += i
			if i == '(':
				stack.append(i)
			if i == ')':
				while stack[-1] != '(':
					postfix += stack.pop()
				stack.pop()
			if i in operator:
				while stack and stack[-1] != '(' and (operator[stack[-1]] >= operator[i]):
					postfix += stack.pop()
				stack.append(i)
		while stack:
			postfix += stack.pop()
		return postfix


class Solution:

	def InfixtoPostfix(self, exp):
		s = ''
		stack = []
		precedence = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1}
		for ele in exp:
			if ele == '(':
				stack.append(ele)
			elif ele == ')':
				top = stack.pop()
				while top != '(':
					s += top
					top = stack.pop()
			elif ele in precedence.keys():
				if len(stack) == 0:
					stack.append(ele)
					continue
				while len(stack) != 0 and stack[-1] != '(' and (precedence[stack[-1]] >= precedence[ele]):
					s += stack.pop()
				stack.append(ele)
			else:
				s += ele
		while len(stack) != 0:
			s += stack.pop()
		return s


class Solution:

	def InfixtoPostfix(self, exp):
		(stack, output) = ([], [])
		mp = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
		for i in exp:
			if i == '(':
				stack.append(i)
			elif i == ')':
				while len(stack) != 0:
					k = stack.pop()
					if k == '(':
						break
					else:
						output.append(k)
			elif i.isdigit() is True or i.isalpha() is True:
				output.append(i)
			else:
				while len(stack) != 0:
					p1 = mp[i]
					top = stack[-1]
					if top not in mp:
						break
					p2 = mp[top]
					if p2 >= p1:
						k = stack.pop()
						output.append(k)
				stack.append(i)
		while len(stack) != 0:
			k = stack.pop()
			output.append(k)
		return ''.join(output)


class Solution:

	def prec(self, c):
		if c == '^':
			return 3
		elif c == '*' or c == '/':
			return 2
		elif c == '+' or c == '-':
			return 1
		else:
			return -1

	def InfixtoPostfix(self, exp):
		res = ''
		st = []
		for c in exp:
			if c.isalpha() or c.isdigit():
				res += c
			elif c == '(':
				st.append('(')
			elif c == ')':
				while st[-1] != '(':
					res += st.pop()
				st.pop()
			else:
				while len(st) and self.prec(c) <= self.prec(st[-1]):
					res += st.pop()
				st.append(c)
		while len(st):
			res += st.pop()
		return res


class Solution:

	def __init__(self):
		self.stack = []
		self.sz = 0

	def push(self, el):
		self.stack.append(el)
		self.sz += 1

	def pop(self):
		self.sz -= 1
		return self.stack.pop()

	def peek(self):
		return self.stack[-1]

	def isEmpty(self):
		return self.stack == []

	def size(self):
		return self.sz

	def InfixtoPostfix(self, exp):
		prec = {'^': 1, '*': 2, '/': 2, '+': 3, '-': 3, '(': 4, ')': 4}
		exp2 = ''
		for i in exp:
			if i not in ['^', '(', ')', '+', '-', '*', '/']:
				exp2 += i
				continue
			if self.isEmpty() is False:
				if i == '(':
					self.push('(')
				elif i == ')':
					while self.peek() != '(':
						exp2 += self.pop()
					self.pop()
				elif prec[i] < prec[self.peek()]:
					self.push(i)
				else:
					while self.isEmpty() is False and prec[i] >= prec[self.peek()]:
						exp2 += self.pop()
					self.push(i)
			else:
				self.push(i)
		while self.isEmpty() is False:
			exp2 += self.pop()
		return exp2


class Solution:

	def is_greater(self, operator1, operator2):
		return self.precedence(operator1) >= self.precedence(operator2)

	def precedence(self, operator):
		symbols = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3, '(': 0, ')': 0}
		return symbols.get(operator, None)

	def is_operand(self, ch):
		return ch not in '+-*/^()'

	def InfixtoPostfix(self, exp):
		st = []
		result = []
		i = 0
		exp = list(exp)
		while i < len(exp):
			if self.is_operand(exp[i]):
				result.append(exp[i])
			elif exp[i] == '(':
				st.append(exp[i])
			elif exp[i] == ')':
				while st[-1] != '(':
					result.append(st.pop())
				st.pop()
			else:
				while st and self.is_greater(st[-1], exp[i]):
					result.append(st.pop())
				st.append(exp[i])
			i += 1
		while st:
			result.append(st.pop())
		return ''.join(result)


class Solution:

	def InfixtoPostfix(self, exp):
		Operators = set(['+', '-', '*', '/', '(', ')', '^'])
		Priority = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
		stack = []
		output = ''
		for char in exp:
			if char not in Operators:
				output += char
			elif char == '(':
				stack.append('(')
			elif char == ')':
				while stack and stack[-1] != '(':
					output += stack.pop()
				stack.pop()
			else:
				while stack and stack[-1] != '(' and (Priority[char] <= Priority[stack[-1]]):
					output += stack.pop()
				stack.append(char)
		while stack:
			output += stack.pop()
		return output


class Solution:

	def InfixtoPostfix(self, exp):
		st = []
		result = []
		symbols = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3, '(': 0, ')': 0}
		i = 0
		exp = list(exp)
		while i < len(exp):
			if exp[i] not in symbols:
				result.append(exp[i])
			else:
				if exp[i] == '(':
					st.append(exp[i])
					i += 1
					continue
				while st and (symbols[exp[i]] <= symbols[st[-1]] or (exp[i] == ')' and st[-1] == '(')):
					op = st.pop()
					if op != '(':
						result.append(op)
					elif exp[i]:
						break
				if exp[i] != ')':
					st.append(exp[i])
			i += 1
		while st:
			result.append(st.pop())
		return ''.join(result)


class Solution:

	def InfixtoPostfix(self, exp):
		stack = []
		st = ''
		for i in exp:
			if i in '^*()/+-':
				if i == '-':
					while len(stack) != 0 and (stack[-1] == '+' or stack[-1] == '-' or stack[-1] == '/' or (stack[-1] == '*') or (stack[-1] == '^')):
						j = stack.pop()
						st += j
					stack.append(i)
				if i == '+':
					while len(stack) != 0 and (stack[-1] == '-' or stack[-1] == '+' or stack[-1] == '/' or (stack[-1] == '*') or (stack[-1] == '^')):
						j = stack.pop()
						st += j
					stack.append(i)
				if i == '*':
					while len(stack) != 0 and (stack[-1] == '/' or stack[-1] == '*' or stack[-1] == '^'):
						j = stack.pop()
						st += j
					stack.append(i)
				if i == '/':
					while len(stack) != 0 and (stack[-1] == '*' or stack[-1] == '/' or stack[-1] == '^'):
						j = stack.pop()
						st += j
					stack.append(i)
				if i == '^':
					while len(stack) != 0 and stack[-1] == '^':
						j = stack.pop()
						st += j
					stack.append(i)
				if i == '(':
					stack.append(i)
				if i == ')':
					while len(stack) != 0 and stack[-1] != '(':
						j = stack.pop()
						st += j
					stack.pop()
			else:
				st += i
		for i in stack:
			j = stack.pop()
			st += j
		return st


class Solution:

	def InfixtoPostfix(self, exp):
		dic = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
		res = ''
		stack = []
		top = -1
		for x in exp:
			if x >= 'a' and x <= 'z' or (x >= 'A' and x <= 'Z') or (x >= '1' and x <= '9'):
				res += x
			elif x == '(':
				stack.append('(')
				top += 1
			elif x == ')':
				while stack[top] != '(':
					y = stack.pop()
					top -= 1
					res += y
				stack.pop()
				top -= 1
			elif top == -1:
				stack.append(x)
				top += 1
			elif dic[stack[top]] < dic[x]:
				stack.append(x)
				top += 1
			else:
				while top >= 0 and dic[stack[top]] >= dic[x]:
					y = stack.pop()
					top -= 1
					res += y
				stack.append(x)
				top += 1
		while top >= 0:
			y = stack.pop()
			top -= 1
			res += y
		return res


class Solution:

	def is_operand(self, ch):
		return ch.isalpha() or ch.isdigit()

	def precedence(self, ch):
		if ch == '+' or ch == '-':
			return 1
		elif ch == '*' or ch == '/':
			return 2
		elif ch == '^':
			return 3
		else:
			return -1

	def InfixtoPostfix(self, exp):
		stack = []
		result = ''
		for ch in exp:
			if self.is_operand(ch):
				result += ch
			elif ch == '(':
				stack.append(ch)
			elif ch == ')':
				while stack and stack[-1] != '(':
					result += stack.pop()
				if stack and stack[-1] == '(':
					stack.pop()
			else:
				while stack and self.precedence(ch) <= self.precedence(stack[-1]):
					result += stack.pop()
				stack.append(ch)
		while stack:
			result += stack.pop()
		return result


class Solution:

	def checkPrecedence(self, op):
		if op == '+' or op == '-':
			return 1
		elif op == '*' or op == '/':
			return 2
		elif op == '^':
			return 3
		elif op == '(':
			return 0

	def InfixtoPostfix(self, exp):
		res = ''
		stack = []
		str_ = exp
		for c in str_:
			if c.isalpha():
				res += c
			elif c.isdigit():
				res += str(c)
			else:
				if len(stack) == 0 or c == '(':
					stack.append(c)
					continue
				if c == ')':
					while stack[-1] != '(':
						res += stack.pop()
					stack.pop()
					continue
				if self.checkPrecedence(stack[-1]) < self.checkPrecedence(c):
					stack.append(c)
				else:
					while len(stack) > 0 and self.checkPrecedence(stack[-1]) >= self.checkPrecedence(c):
						res += stack.pop()
					stack.append(c)
		while len(stack) != 0:
			res += stack.pop()
		return res


class Conversion:

	def __init__(self, capacity):
		self.top = -1
		self.capacity = capacity
		self.array = []
		self.output = []
		self.precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}

	def isEmpty(self):
		return True if self.top == -1 else False

	def peek(self):
		return self.array[-1]

	def pop(self):
		if not self.isEmpty():
			self.top -= 1
			return self.array.pop()
		else:
			return '$'

	def push(self, op):
		self.top += 1
		self.array.append(op)

	def isOperand(self, ch):
		return ch.isalpha() or ch.isnumeric()

	def notGreater(self, i):
		try:
			a = self.precedence[i]
			b = self.precedence[self.peek()]
			return True if a <= b else False
		except KeyError:
			return False

	def infixToPostfix(self, exp):
		for i in exp:
			if self.isOperand(i):
				self.output.append(i)
			elif i == '(':
				self.push(i)
			elif i == ')':
				while not self.isEmpty() and self.peek() != '(':
					a = self.pop()
					self.output.append(a)
				if not self.isEmpty() and self.peek() != '(':
					return -1
				else:
					self.pop()
			else:
				while not self.isEmpty() and self.notGreater(i):
					self.output.append(self.pop())
				self.push(i)
		while not self.isEmpty():
			self.output.append(self.pop())
		return ''.join(self.output)

class Solution:

	def InfixtoPostfix(self, exp):
		obj = Conversion(len(exp))
		return obj.infixToPostfix(exp)


class Solution:

	def __init__(self):
		self.s = ''

	def InfixtoPostfix(self, exp):
		priority = dict()
		priority['+'] = 1
		priority['-'] = 1
		priority['/'] = 2
		priority['*'] = 2
		priority['^'] = 3
		priority['('] = 4
		stack = []
		i = 0
		while i < len(exp):
			if ord(exp[i]) >= 97 and ord(exp[i]) <= 121 or (ord(exp[i]) >= ord('0') and ord(exp[i]) <= ord('9')):
				self.s += exp[i]
			elif exp[i] == '(':
				stack.append(exp[i])
			elif exp[i] in '+-*/^':
				if len(stack) == 0:
					stack.append(exp[i])
				else:
					while len(stack) > 0 and stack[len(stack) - 1] != '(' and (priority[exp[i]] <= priority[stack[len(stack) - 1]]):
						a = stack.pop()
						self.s += a
					stack.append(exp[i])
					if stack[len(stack) - 1] == '(':
						stack.pop()
			elif exp[i] == ')':
				while len(stack) > 0 and stack[len(stack) - 1] != '(':
					self.s += stack.pop()
				stack.pop()
			i += 1
		while len(stack) != 0:
			self.s += stack.pop()
		return self.s


class Solution:

	def __init__(self):
		self.precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}

	def InfixtoPostfix(self, exp):
		postfix = []
		stack = []
		for i in exp:
			if i == '(':
				stack.append('(')
			elif i == ')':
				while stack and stack[-1] != '(':
					postfix.append(stack.pop())
				stack.pop()
			elif i in self.precedence:
				while stack and stack[-1] != '(' and (self.precedence[stack[-1]] >= self.precedence[i]):
					postfix.append(stack.pop())
				stack.append(i)
			else:
				postfix.append(i)
		while stack:
			postfix.append(stack.pop())
		return ''.join(postfix)


class Solution:

	def __init__(self):
		self.precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}

	def InfixtoPostfix(self, exp):
		pf = []
		stack = []
		i = 0
		while i < len(exp):
			if exp[i] == '(':
				paramStack = ['(']
				temp = ''
				i += 1
				while i < len(exp):
					if exp[i] == ')':
						paramStack.pop()
					elif exp[i] == '(':
						paramStack.append('(')
					if not paramStack:
						break
					temp += exp[i]
					i += 1
				op = self.InfixtoPostfix(temp)
				pf.append(op)
			elif exp[i] in self.precedence:
				if stack and self.precedence[stack[-1]] >= self.precedence[exp[i]]:
					while stack:
						pf.append(stack.pop())
				stack.append(exp[i])
			else:
				pf.append(exp[i])
			i += 1
		while stack:
			pf.append(stack.pop())
		return ''.join(pf)


class Solution:

	def precedence(self, n):
		if n == '^':
			return 3
		elif n == '*' or n == '/':
			return 2
		elif n == '+' or n == '-':
			return 1
		else:
			return 0

	def InfixtoPostfix(self, exp):
		s = []
		r = ''
		end = len(exp) - 1 if exp[-1].isalnum() else len(exp)
		for i in range(0, end):
			if exp[i].isalnum():
				r = r + exp[i]
			elif exp[i] == '(':
				s.append(exp[i])
			elif len(s) != 0:
				if exp[i] == ')':
					a = len(s) - 1
					while a >= 0:
						if s[a] == '(':
							s.pop()
							break
						r = r + s.pop()
						a = a - 1
				elif self.precedence(s[-1]) >= self.precedence(exp[i]):
					r = r + s.pop()
					s.append(exp[i])
				else:
					s.append(exp[i])
			else:
				s.append(exp[i])
		if end == len(exp) - 1:
			for i in range(len(s) - 2, -1, -1):
				r = r + s[i]
			r = r + exp[len(exp) - 1] + s[-1]
		elif len(s) != 0:
			for i in range(len(s) - 1, -1, -1):
				r = r + s[i]
		return r


class Solution:

	def InfixtoPostfix(self, exp):
		dict1 = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1, '(': 0, ')': 0}
		stack = []
		final = []
		l = dict1.keys()
		for i in range(len(exp)):
			if exp[i] in l:
				if exp[i] == '(':
					stack.append(exp[i])
					continue
				if exp[i] == ')':
					while stack[-1] != '(':
						final.append(stack.pop())
					stack.pop()
					continue
				if stack == []:
					stack.append(exp[i])
					continue
				if dict1[stack[-1]] >= dict1[exp[i]]:
					while stack != [] and dict1[stack[-1]] >= dict1[exp[i]]:
						final.append(stack.pop())
					stack.append(exp[i])
				else:
					stack.append(exp[i])
			else:
				final.append(exp[i])
		while stack != []:
			final.append(stack.pop())
		return ''.join(final)


class Solution:

	def InfixtoPostfix(self, exp):
		stack = []
		ans_postfix = ''
		for i in exp:
			if i in '+-':
				while len(stack) and stack[-1] != '(':
					ans_postfix += stack.pop(-1)
				stack.append(i)
			elif i in '/*':
				while len(stack) and stack[-1] in '/*^':
					ans_postfix += stack.pop(-1)
				stack.append(i)
			elif i == '^':
				while len(stack) and stack[-1] == '^':
					ans_postfix += stack.pop(-1)
				stack.append(i)
			elif i == '(':
				stack.append(i)
			elif i == ')':
				while stack[-1] != '(':
					ans_postfix += stack.pop(-1)
				stack.pop(-1)
			else:
				ans_postfix += i
		while len(stack):
			ans_postfix += stack.pop(-1)
		return ans_postfix


class Solution:

	def InfixtoPostfix(self, exp):
		op = {'(': 0, '^': 3, '*': 2, '/': 2, '+': 1, '-': 1}
		stack = []
		infix = ''
		for i in exp:
			if i in op.keys():
				if len(stack) == 0:
					stack.append(i)
				elif i == '(':
					stack.append(i)
				elif op[i] > op[stack[-1]]:
					stack.append(i)
				elif op[i] == op[stack[-1]] and i != '^':
					while len(stack) != 0 and op[i] <= op[stack[-1]]:
						infix = infix + stack.pop()
					stack.append(i)
				elif op[i] == op[stack[-1]] and i == '^':
					infix = infix + i
				elif op[i] < op[stack[-1]] and i != '(':
					while len(stack) != 0 and op[i] <= op[stack[-1]]:
						infix = infix + stack.pop()
					stack.append(i)
			elif i == ')':
				while len(stack) != 0 and stack[-1] != '(':
					infix = infix + stack.pop()
				if stack[-1] == '(':
					stack.pop()
			else:
				infix = infix + i
		while len(stack) != 0:
			infix = infix + stack.pop()
		return infix


class Solution:

	def InfixtoPostfix(self, exp):
		stack = []
		operands = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
		precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
		post = ''
		for i in exp:
			if i in operands:
				post += i
			elif len(stack) == 0:
				stack.append(i)
			elif i == '(':
				stack.append(i)
			elif i == ')':
				while len(stack) != 0 and stack[-1] != '(':
					post += stack.pop()
				stack.pop()
			elif stack[-1] == '(' and (i == '+' or '-' or '*' or '/' or '^'):
				stack.append(i)
			elif precedence[i] > precedence[stack[-1]]:
				stack.append(i)
			else:
				while len(stack) != 0 and stack[-1] != '(' and (precedence[i] <= precedence[stack[-1]]):
					post += stack.pop()
				stack.append(i)
		while len(stack) != 0:
			post += stack.pop()
		return post


class Solution:

	def InfixtoPostfix(self, exp):
		stack = []
		prefix = ''
		operator = ['^', '*', '/', '+', '-']
		precedence = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
		for val in exp:
			if val == '(':
				stack.append(val)
			elif val == ')':
				while stack[-1] != '(':
					prefix += stack.pop()
				stack.pop()
			elif val not in operator:
				prefix += val
			else:
				if stack:
					while precedence[stack[-1]] >= precedence[val]:
						prefix += stack.pop()
						if not stack:
							break
				stack.append(val)
		while stack:
			prefix += stack.pop()
		return prefix


class Solution:

	def InfixtoPostfix(self, exp):
		stk = []
		operLevel = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3, '(': 0}
		result = ''
		for elem in exp:
			if elem.isalnum():
				result += elem
			elif elem == '(':
				stk.append(elem)
			elif elem == ')':
				while stk and stk[-1] != '(':
					result += stk.pop()
				stk.pop()
			else:
				while stk and operLevel[elem] <= operLevel[stk[-1]]:
					result += stk.pop()
				stk.append(elem)
		while stk:
			result += stk.pop()
		return result


class Solution:

	def InfixtoPostfix(self, exp):
		prec = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
		post = ''
		st = []
		for i in exp:
			if i == '(':
				st.append(i)
			elif i == ')':
				while st[-1] != '(':
					post += st.pop()
				st.pop()
			elif i not in prec:
				post += i
			else:
				while st and st[-1] != '(' and (prec[i] <= prec[st[-1]]):
					post += st.pop()
				st.append(i)
		while st:
			post += st.pop()
		return post


class Solution:

	def __init__(self):
		self.stack = []
		self.st = ''

	def check(self, s):
		dt = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
		return dt.get(s)

	def InfixtoPostfix(self, exp):
		for symbol in exp:
			if symbol == '(':
				self.stack.append(symbol)
			elif symbol == ')':
				next = ')'
				while next != '(':
					if next != ')':
						self.st += next
					next = self.stack.pop()
			elif symbol == '+' or symbol == '-' or symbol == '*' or (symbol == '/') or (symbol == '^'):
				while len(self.stack) > 0 and self.check(self.stack[-1]) >= self.check(symbol):
					self.st += self.stack.pop()
				self.stack.append(symbol)
			else:
				self.st += symbol
		while len(self.stack) > 0:
			self.st += self.stack.pop()
		return self.st


class Solution:

	def prec(self, c):
		if c == '^':
			return 3
		elif c == '*' or c == '/':
			return 2
		elif c == '+' or c == '-':
			return 1
		else:
			return -1

	def InfixtoPostfix(self, exp):
		st = []
		result = str()
		for ch in exp:
			if ch >= 'a' and ch <= 'z' or (ch >= 'A' and ch <= 'Z') or (ch >= '1' and ch <= '9'):
				result += ch
			elif ch == '(':
				st.append(ch)
			elif ch == ')':
				while st[-1] != '(':
					result += st.pop()
				st.pop()
			else:
				while len(st) != 0 and self.prec(ch) <= self.prec(st[-1]):
					result += st.pop()
				st.append(ch)
		while st:
			result += st.pop()
		return result


class Solution:

	def InfixtoPostfix(self, exp):
		output = []
		operator = []
		pri = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
		for i in exp:
			if i == '(':
				operator.append('(')
			elif i == ')':
				while operator[-1] != '(':
					ele = operator.pop()
					output.append(ele)
				operator.pop()
			elif i in '+-*/^':
				while operator and pri[operator[-1]] >= pri[i]:
					t = operator.pop()
					output.append(t)
				operator.append(i)
			else:
				output.append(i)
		while operator:
			t = operator.pop()
			output.append(t)
		return ''.join(output)


class Solution:

	def InfixtoPostfix(self, exp):
		output = []
		operator = []
		priority = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
		for ch in exp:
			if ch == '(':
				operator.append(ch)
			elif ch == ')':
				while operator[-1] != '(':
					ele = operator.pop()
					output.append(ele)
				operator.pop()
			elif ch == '+' or ch == '-' or ch == '*' or (ch == '/') or (ch == '^'):
				if len(operator) > 0:
					while priority[operator[-1]] >= priority[ch]:
						ele = operator.pop()
						output.append(ele)
						if len(operator) == 0:
							break
				operator.append(ch)
			else:
				output.append(ch)
		while len(operator) != 0:
			ele = operator.pop()
			output.append(ele)
		return ''.join(output)


class Solution:

	def InfixtoPostfix(self, exp):
		stack = []
		top = -1
		postfix = ''
		d = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1, '(': 0}
		for v in exp:
			if v.isdigit() or v.isalpha():
				postfix += v
			elif stack == [] or v == '(':
				stack.append(v)
				top += 1
			elif v == ')':
				while stack[top] != '(' and top != -1:
					postfix += stack[top]
					stack.pop()
					top -= 1
				if top != -1:
					stack.pop()
					top -= 1
			else:
				while top != -1 and d[v] <= d[stack[top]]:
					postfix += stack[top]
					top -= 1
					stack.pop()
				stack.append(v)
				top += 1
		for i in range(len(stack) - 1, -1, -1):
			postfix += stack[i]
		return postfix


class Solution:

	def InfixtoPostfix(self, exp):
		stack = []
		res = []
		k = {'*': 2, '/': 2, '^': 3, '+': 1, '-': 1}
		for i in exp:
			if i == '(':
				stack.append(i)
			if i.isalpha():
				res.append(i)
			if i.isdigit():
				res.append(i)
			elif i in '+-*/^':
				if not stack:
					stack.append(i)
				elif stack[-1] == '(':
					stack.append(i)
				elif k[stack[-1]] >= k[i]:
					while stack and stack[-1] != '(' and (k[stack[-1]] >= k[i]):
						res.append(stack.pop())
					stack.append(i)
				else:
					stack.append(i)
			elif i == ')':
				while stack and stack[-1] != '(':
					res.append(stack.pop())
				stack.pop()
		if stack:
			while stack:
				res.append(stack.pop())
		return ''.join(res)


class Solution:

	def InfixtoPostfix(self, s):
		st = []
		ans = ''
		d = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1, '(': 0}
		for i in s:
			if i.isnumeric():
				ans = ans + i
			elif i.isalpha():
				ans = ans + i
			elif i == '(':
				st.append(i)
			elif i == ')':
				while st[-1] != '(':
					ans = ans + st.pop()
				st.pop()
			elif i in ['^', '*', '/', '+', '-']:
				if len(st) == 0:
					st.append(i)
				elif d[i] > d[st[-1]]:
					st.append(i)
				else:
					while len(st) != 0 and d[i] <= d[st[-1]]:
						y = st.pop()
						ans = ans + y
					st.append(i)
		for i in range(len(st)):
			ans = ans + st[i]
		return ans


class Solution:

	def InfixtoPostfix(self, exp):
		st = exp
		res = ''
		dict = {'+': 1, '-': 1, '*': 2, '/': 2, '**': 3, '^': 3}
		stack = []
		for i in st:
			if i.isalnum():
				res += i
				continue
			if i == '(':
				stack.append(i)
			elif i == ')':
				while stack[-1] != '(':
					res += stack.pop()
				stack.pop()
			elif i in dict:
				while stack and stack[-1] in dict and (dict[stack[-1]] >= dict[i]):
					res += stack.pop()
				stack.append(i)
		while stack:
			res += stack.pop()
		return res


class Solution:

	def __init__(self):
		self.stack = []
		self.rexp = ''
		self.dt = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2, '^': 3}

	def order(self, op):
		return self.dt.get(op)

	def InfixtoPostfix(self, exp):
		for i in exp:
			if i == '(':
				self.stack.append(i)
			elif i == ')':
				while self.stack[-1] != '(':
					ele = self.stack.pop()
					self.rexp += ele
				self.stack.pop()
			elif i == '+' or i == '-' or i == '*' or (i == '/') or (i == '^'):
				if len(self.stack) > 0:
					while self.dt[self.stack[-1]] >= self.dt[i]:
						ele = self.stack.pop()
						self.rexp += ele
						if len(self.stack) == 0:
							break
				self.stack.append(i)
			else:
				self.rexp += i
		if len(self.stack) > 0:
			ele = self.stack.pop()
			self.rexp += ele
		return self.rexp


class Solution:

	def InfixtoPostfix(self, exp):
		stack_exp = ['empty']
		postfix_exp = ''
		precedence = {'^': 6, '*': 4, '/': 4, '+': 2, '-': 2, '(': 0, 'empty': -1}
		for char in exp:
			if char.isalnum():
				postfix_exp += char
				continue
			if char == ')':
				while stack_exp[-1] != '(':
					operation = stack_exp.pop()
					postfix_exp += operation
				stack_exp.pop()
				continue
			if char == '(':
				stack_exp.append(char)
				continue
			while precedence[stack_exp[-1]] >= precedence[char]:
				operation = stack_exp.pop()
				postfix_exp += operation
			stack_exp.append(char)
		for i in range(len(stack_exp)):
			operation = stack_exp.pop()
			if operation != 'empty':
				postfix_exp += operation
		return postfix_exp


class Solution:
	precedence = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1}

	def InfixtoPostfix(self, exp):
		stack = []
		postfix = ''
		for char in exp:
			if char == ')':
				while len(stack) != 0 and stack[-1] != '(':
					postfix += stack.pop()
				if len(stack) > 0:
					stack.pop()
			elif char == '(':
				stack.append(char)
			elif char in Solution.precedence:
				while len(stack) != 0 and stack[-1] != '(' and (Solution.precedence[stack[-1]] >= Solution.precedence[char]):
					postfix += stack.pop()
				stack.append(char)
			else:
				postfix += char
		while len(stack) != 0:
			postfix += stack.pop()
		return postfix


class Solution:

	def InfixtoPostfix(self, exp):
		op = []
		ans = []
		ops = '+-*/^()'
		left = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3, '(': 0}
		right = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3, '(': 4}
		for c in exp:
			if not c in ops:
				ans.append(c)
			elif c == ')':
				while True:
					if op[-1] == '(':
						op.pop()
						break
					s2 = ans[-1]
					ans.pop()
					s1 = ans[-1]
					ans.pop()
					ans.append(s1 + s2 + op[-1])
					op.pop()
					if op[-1] == '(':
						op.pop()
						break
			elif c == '(':
				op.append(c)
			else:
				while len(op) > 0 and left[op[-1]] >= right[c]:
					s2 = ans[-1]
					ans.pop()
					s1 = ans[-1]
					ans.pop()
					ans.append(s1 + s2 + op[-1])
					op.pop()
				op.append(c)
		while len(op) > 0:
			s = op[-1]
			ans.append(s)
			op.pop()
		return ''.join(ans)


class Solution:

	def precedence(self, opr):
		if opr == '^':
			return 3
		elif opr == '*' or opr == '/':
			return 2
		elif opr == '+' or opr == '-':
			return 1
		else:
			return -1

	def InfixtoPostfix(self, exp):
		res = []
		stack = []
		for i in exp:
			if i not in '()^*/+-':
				res.append(i)
			elif i == '(':
				stack.append(i)
			elif i == ')':
				while len(stack) != 0 and stack[-1] != '(':
					res.append(stack.pop())
				stack.pop()
			else:
				while stack and self.precedence(i) <= self.precedence(stack[-1]):
					res.append(stack.pop())
				stack.append(i)
		while stack:
			res.append(stack.pop())
		return ''.join(res)


def preced(ch: str):
	if ch == '^':
		return 3
	elif ch == '*' or ch == '/':
		return 2
	elif ch == '+' or ch == '-':
		return 1
	elif ch == '(':
		return -1
	elif ch == ')':
		return -1
	else:
		return 0

class Solution:

	def InfixtoPostfix(self, exp):
		stack = []
		postfix = []
		for i in exp:
			if preced(i) == 0:
				postfix.append(i)
			elif i == '(':
				stack.append(i)
			elif i == ')':
				while stack[-1] != '(':
					postfix += stack[-1]
					stack.pop()
				stack.pop()
			elif not stack:
				stack.append(i)
			else:
				while stack and preced(i) <= preced(stack[-1]):
					postfix.append(stack[-1])
					stack.pop()
				stack.append(i)
		while stack:
			postfix.append(stack[-1])
			stack.pop()
		return ''.join(postfix)


class Solution:

	def InfixtoPostfix(self, exp):
		st = []
		res = ''
		for i in exp:
			if i in 'abcdefghijklmonpqrstuvwxyz0123456789':
				res += i
			elif i in '+-/*)^(':
				if i == '(':
					st.append('(')
				elif i == ')':
					for j in st[::-1]:
						if j != '(':
							res += st.pop()
						elif j == '(':
							st.pop()
							break
				elif i in '^':
					for j in st[::-1]:
						if j in '^':
							res += st.pop()
						else:
							break
					st.append(i)
				elif i in '/*':
					for j in st[::-1]:
						if j in '/*^':
							res += st.pop()
						else:
							break
					st.append(i)
				elif i in '+-':
					for j in st[::-1]:
						if j in ['+', '-', '^', '*', '/']:
							res += st.pop()
						else:
							break
					st.append(i)
		for k in range(len(st)):
			res += st.pop()
		return res


class Stack:

	def __init__(self, size):
		self.size = size
		self.lst = ['.'] * self.size
		self.top = -1

	def push(self, data):
		self.top += 1
		self.lst[self.top] = data

	def pop(self):
		ele = self.lst[self.top]
		self.lst[self.top] = '.'
		self.top -= 1
		return ele

	def show_top(self):
		return self.lst[self.top]

	def isEmpty(self):
		if self.top == -1:
			return True
		else:
			return False

class Solution:

	def InfixtoPostfix(self, exp):
		st = Stack(len(exp))
		stack_out = {'+': 1, '-': 1, '*': 3, '/': 3, '^': 5, '(': 7, ')': 0}
		stack_in = {'+': 2, '-': 2, '*': 4, '/': 4, '^': 6, '(': 0}
		post = ''
		for i in exp:
			if i in stack_out:
				if st.isEmpty() or stack_out[i] > stack_in[st.show_top()]:
					st.push(i)
				else:
					while not st.isEmpty():
						if stack_in[st.show_top()] > stack_out[i]:
							post = post + st.pop()
						elif stack_out[i] == stack_in[st.show_top()]:
							st.pop()
							break
						else:
							break
					if i != ')':
						st.push(i)
			else:
				post = post + i
		if not st.isEmpty():
			while not st.isEmpty():
				post = post + st.pop()
		return post


class Solution:

	def InfixtoPostfix(self, exp):
		n = exp
		pre = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
		out = ''
		stack = []
		for i in exp:
			if i.isalpha() or i.isnumeric():
				out += i
			elif i == '(':
				stack.append(i)
			elif i == ')':
				while stack and stack[-1] != '(':
					out += stack.pop()
				if not stack:
					return -1
				else:
					stack.pop()
			else:
				while stack and stack[-1] != '(' and (pre[stack[-1]] >= pre[i]):
					out += stack.pop()
				stack.append(i)
		while stack:
			out += stack.pop()
		return out


class Solution:

	def InfixtoPostfix(self, exp):
		pre_d = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1}
		stack = []
		ans = ''
		for i in exp:
			if i in '^*/+-':
				while stack and stack[-1] != '(' and (pre_d[i] <= pre_d[stack[-1]]):
					ans += stack.pop()
				stack.append(i)
			elif i == '(':
				stack.append(i)
			elif i == ')':
				while stack[-1] != '(':
					ans += stack.pop()
				stack.pop()
			else:
				ans += i
		while stack:
			ans += stack.pop()
		return ans


class Solution:

	def InfixtoPostfix(self, exp):
		precedence = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1}
		stack = []
		postfix = ''
		for c in exp:
			if c.isalpha() or c.isdigit():
				postfix += c
			elif c == '(':
				stack.append(c)
			elif c == ')':
				while stack[-1] != '(':
					postfix += stack.pop()
				stack.pop()
			else:
				while stack and stack[-1] != '(' and (precedence[c] <= precedence[stack[-1]]):
					postfix += stack.pop()
				stack.append(c)
		while stack:
			postfix += stack.pop()
		return postfix


class Solution:

	def InfixtoPostfix(self, exp):
		precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '%': 2, '^': 3}
		res = ''
		stack = []
		for c in exp:
			if 96 < ord(c) < 123 or 64 < ord(c) < 91 or '0' <= c <= '9':
				res += c
			elif c == '(':
				stack.append(c)
			elif c == ')':
				while stack[-1] != '(':
					res += str(stack.pop())
				stack.pop()
			else:
				while stack and stack[-1] != '(' and (precedence[c] <= precedence[stack[-1]]):
					res += str(stack.pop())
				stack.append(c)
		while stack:
			res += str(stack.pop())
		return res


class Solution:

	def InfixtoPostfix(self, exp):
		precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '%': 2, '^': 3}
		res = ''
		stack = [0]
		for i in range(len(exp)):
			if 96 < ord(exp[i]) < 123 or 64 < ord(exp[i]) < 91 or '0' <= exp[i] <= '9':
				res += str(exp[i])
			elif exp[i] == '(':
				stack.append(exp[i])
			elif exp[i] == ')':
				while stack[-1] != '(':
					res += str(stack.pop())
				stack.pop()
			elif exp[i] == '+' or exp[i] == '-' or exp[i] == '*' or (exp[i] == '/') or (exp[i] == '%') or (exp[i] == '^'):
				while stack[-1] != 0 and stack[-1] != '(' and (precedence.get(exp[i]) <= precedence.get(stack[-1])):
					res += str(stack.pop())
				stack.append(exp[i])
		while stack[-1] != 0:
			res += str(stack.pop())
		return res


class Solution:

	def InfixtoPostfix(self, A):
		stack = []
		output = []
		precedence = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1}
		for char in A:
			if char.isalpha() or char.isdigit():
				output.append(char)
			elif char in precedence:
				while stack and stack[-1] != '(' and (precedence[char] <= precedence[stack[-1]]):
					output.append(stack.pop())
				stack.append(char)
			elif char == '(':
				stack.append(char)
			elif char == ')':
				while stack and stack[-1] != '(':
					output.append(stack.pop())
				stack.pop()
		while stack:
			output.append(stack.pop())
		return ''.join(output)


class Solution:

	def InfixtoPostfix(self, exp):
		rank = {'-': 1, '+': 1, '/': 2, '*': 3, '^': 4}
		i = 0
		n = len(exp)
		stack = []
		op = []
		res = ''
		while i < n:
			j = i
			if exp[i] not in ('^', '/', '*', '+', '-', '(', ')'):
				stack.append(exp[i])
			elif len(stack) < 2 and exp[i] in ('^', '/', '*', '+', '-'):
				op.append(exp[i])
			elif exp[i] == '(':
				j = i + 1
				balance = 1
				while j < n and balance != 0:
					if exp[j] == '(':
						balance += 1
					elif exp[j] == ')':
						balance -= 1
					j += 1
				stack.append(self.InfixtoPostfix(exp[i + 1:j - 1]))
				j -= 1
			elif exp[i] == ')':
				while op:
					(b, a) = (stack.pop(), stack.pop())
					temp = a + b + op.pop()
					stack.append(temp)
				return stack[0]
			else:
				while len(stack) >= 2 and op and (rank[op[-1]] >= rank[exp[i]]):
					(b, a) = (stack.pop(-1), stack.pop(-1))
					temp = a + b + op.pop(-1)
					stack.append(temp)
				op.append(exp[i])
			i = j + 1
		while op:
			(b, a) = (stack.pop(), stack.pop())
			temp = a + b + op.pop()
			stack.append(temp)
		return ''.join(stack)


class Solution:

	def InfixtoPostfix(self, exp):
		dic = {}
		dic['+'] = 0
		dic['-'] = 0
		dic['*'] = 1
		dic['/'] = 1
		dic['^'] = 2
		dic['('] = 3
		dic[')'] = -1
		stack = []
		operators = []
		count = 0
		for i in range(len(exp)):
			if exp[i] not in ('+', '-', '*', '/', '^', '(', ')'):
				stack.append(exp[i])
			elif len(operators) > 0 and dic[operators[-1]] >= dic[exp[i]] and (operators[-1] != '(') and (exp[i] != ')'):
				while len(operators) > 0 and dic[operators[-1]] >= dic[exp[i]] and (operators[-1] != '(') and (exp[i] != ')'):
					rhs = stack.pop()
					lhs = stack.pop()
					operation = operators.pop()
					stack.append(lhs + rhs + operation)
				operators.append(exp[i])
			elif exp[i] == ')':
				while operators[-1] != '(':
					rhs = stack.pop()
					lhs = stack.pop()
					operation = operators.pop()
					stack.append(lhs + rhs + operation)
				operators.pop()
			else:
				operators.append(exp[i])
		if len(stack) == 1:
			return stack[-1]
		rhs = stack.pop()
		lhs = stack.pop()
		operation = operators.pop()
		return lhs + rhs + operation


class Solution:

	def InfixtoPostfix(self, exp):
		precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3, '(': 4}
		(stack, res) = ([], [])
		for i in exp:
			if i == ')':
				while stack[-1] != '(':
					res.append(stack.pop())
				stack.pop()
			elif i in precedence.keys():
				while stack and stack[-1] != '(' and (precedence[stack[-1]] >= precedence[i]):
					res.append(stack.pop())
				stack.append(i)
			else:
				res.append(i)
		return ''.join(res + stack)


class Solution:

	def InfixtoPostfix(self, exp):
		precedence = [')', '-', '+', '/', '*', '^', '(']
		res = ''
		stack = []
		for i in range(len(exp)):
			if exp[i] >= 'a' and exp[i] <= 'z' or (exp[i] >= '0' and exp[i] <= '9'):
				res = res + exp[i]
			elif len(stack) == 0:
				stack.append(exp[i])
			else:
				a = precedence.index(exp[i])
				b = precedence.index(stack[len(stack) - 1])
				if a == 2 and b == 1 or (a == 4 and b == 3):
					a = b
				if a > b:
					stack.append(exp[i])
				else:
					while b >= a:
						if precedence[a] == ')' and precedence[b] == '(':
							stack.pop()
							break
						if stack[len(stack) - 1] == '(':
							break
						res = res + stack.pop()
						if len(stack) == 0:
							break
						b = precedence.index(stack[len(stack) - 1])
					stack.append(exp[i])
					if stack[len(stack) - 1] == ')':
						stack.pop()
		for i in range(len(stack)):
			a = stack.pop()
			if a != '(' or a != ')':
				res = res + a
		res = res.replace('(', '')
		res = res.replace(')', '')
		return res


class Solution:

	def InfixtoPostfix(self, expr):
		st = []
		ans = ''
		for ch in expr:
			list = [ord(ch) >= ord('a') and ord(ch) <= ord('z'), ord(ch) >= ord('A') and ord(ch) <= ord('Z'), ord('0') <= ord(ch) and ord(ch) <= ord('9')]
			if any(list):
				ans += ch
			elif ch == '(':
				st.append('(')
			elif ch == ')':
				while st[-1] != '(':
					ans += st[-1]
					st.pop()
				st.pop()
			else:
				while len(st) != 0 and self.prec(ch) <= self.prec(st[-1]):
					ans += st[-1]
					st.pop()
				st.append(ch)
		while len(st) != 0:
			ans += st[-1]
			st.pop()
		return ans

	def prec(self, opr):
		if opr == '^':
			return 3
		elif opr == '*' or opr == '/':
			return 2
		elif opr == '+' or opr == '-':
			return 1
		else:
			return -1


class Solution:

	def InfixtoPostfix(self, exp):
		s = ''
		stack = []
		if len(exp) == 0:
			return s
		pnce = {'^': 5, '*': 4, '/': 3, '+': 2, '-': 2}
		for i in exp:
			if i in ''.join(pnce.keys()):
				if len(stack) != 0:
					if stack[-1] == '(':
						stack.append(i)
					elif pnce[stack[-1]] < pnce[i]:
						stack.append(i)
					else:
						while stack and pnce[stack[-1]] >= pnce[i]:
							s = s + stack.pop()
							if len(stack) != 0 and stack[-1] == '(':
								break
						stack.append(i)
				else:
					stack.append(i)
			elif i == '(':
				stack.append(i)
			elif i == ')':
				o = ''
				while o != '(':
					o = stack.pop()
					if o == '(':
						break
					s = s + o
			else:
				s = s + i
		while stack:
			s = s + stack.pop()
		return s


class Solution:

	def InfixtoPostfix(self, exp):
		precedence = {'*': 2, '/': 2, '^': 3, '+': 1, '-': 1, '(': 5, ')': 5}
		tokens = list(exp)
		prefix = []
		operator = []
		for token in tokens:
			if token in precedence:
				if token == '(':
					operator.append('(')
				elif token == ')':
					while operator[-1] != '(':
						prefix.append(operator.pop())
					operator.pop()
				elif len(operator):
					if precedence[token] > precedence[operator[-1]]:
						operator.append(token)
					else:
						while operator and operator[-1] != '(' and (precedence[token] <= precedence[operator[-1]]):
							prefix.append(operator.pop())
						operator.append(token)
				else:
					operator.append(token)
			else:
				prefix.append(token)
		while operator:
			prefix.append(operator.pop())
		return ''.join(prefix)


class Solution:

	def InfixtoPostfix(self, exp):
		d = {'^': 2, '*': 1, '/': 1, '+': 0, '-': 0}
		st = []
		ps = ''
		for i in exp:
			if i.isalnum():
				ps = ps + i
			elif i == '(':
				st.append(i)
			elif i == ')':
				while st[-1] != '(':
					ps = ps + st.pop()
				st.pop()
			else:
				while len(st) > 0 and st[-1] != '(' and (d[st[-1]] >= d[i]):
					ps = ps + st.pop()
				st.append(i)
		while len(st) > 0 and st[-1] != '(':
			ps = ps + st.pop()
		return ps