You are given a string S of size N that represents the prefix form of a valid mathematical expression. Convert it to its infix form.
Example 1:
Input: 
*-A/BC-/AKL
Output: 
((A-(B/C))*((A/K)-L))
Explanation: 
The above output is its valid infix form.
Your Task:
Complete the function string preToInfix(string pre_exp), which takes a prefix string as input and return its infix form.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
3<=|S|<=10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def preToInfix(self, pre_exp):

        # Code here

Solutions:
class Solution:

	def preToInfix(self, pre_exp):
		stk = []
		i = len(pre_exp) - 1
		while i != -1:
			if pre_exp[i] in ['+', '/', '*', '-', '^', '(', ')']:
				op1 = stk.pop()
				op2 = stk.pop()
				stk.append('(' + op1 + prefix[i] + op2 + ')')
			else:
				stk.append(pre_exp[i])
			i -= 1
		return stk.pop()


class Solution:

	def preToInfix(self, pre_exp):
		s = []
		for i in pre_exp[::-1]:
			if i.isalpha():
				s.append(i)
			else:
				a = s.pop()
				b = s.pop()
				s.append('(' + a + i + b + ')')
		return s[0]


class Solution:

	def preToInfix(self, pre_exp):
		st = []
		for i in range(len(pre_exp) - 1, -1, -1):
			if pre_exp[i].isalnum():
				st.append(pre_exp[i])
			elif len(st) >= 2:
				a = st.pop()
				b = st.pop()
				res = '(' + a + pre_exp[i] + b + ')'
				st.append(res)
		return st[0]


class Solution:

	def preToInfix(self, pre_exp):
		result = ''
		prev = ''
		stack = []
		for i in pre_exp[::-1]:
			if i.isalnum():
				stack.append(i)
			else:
				x = stack.pop()
				y = stack.pop()
				prev = '(' + x + i + y + ')'
				stack.append(prev)
		return stack.pop()


class Solution:

	def preToInfix(self, pre):
		pre = pre[::-1]
		stack = []
		for i in range(len(pre)):
			if pre[i] == '-' or pre[i] == '+' or pre[i] == '*' or (pre[i] == '/'):
				x = stack.pop()
				y = stack.pop()
				stack.append(')' + y + pre[i] + x + '(')
			else:
				stack.append(pre[i])
		ans = stack[0]
		return ans[::-1]


class Solution(object):

	def __init__(self):
		self.stack = []
		self.operatorSet = ('^', '*', '/', '+', '-', '(', ')')

	def isOperator(self, char):
		return char in self.operatorSet

	def preToInfix(self, prefix):
		index = len(prefix) - 1
		while 0 <= index:
			char = prefix[index]
			if not self.isOperator(char):
				self.stack.append(char)
				index -= 1
			else:
				exp = '(' + self.stack.pop() + char + self.stack.pop() + ')'
				self.stack.append(exp)
				index -= 1
		return self.stack.pop()


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		for c in pre_exp:
			if c == '+' or c == '-' or c == '*' or (c == '/'):
				stack.append(c)
			else:
				curr = c
				while len(stack) > 0 and stack[-1] not in ['+', '-', '*', '/']:
					op1 = stack.pop()
					op = stack.pop()
					curr = '(' + op1 + op + curr + ')'
				stack.append(curr)
		return stack[0]


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		n = len(pre_exp)
		for i in range(n - 1, -1, -1):
			if pre_exp[i].isalpha() or pre_exp[i].isdigit():
				stack.append(pre_exp[i])
			else:
				op1 = stack.pop()
				op2 = stack.pop()
				exp = '(' + op1 + pre_exp[i] + op2 + ')'
				stack.append(exp)
		return stack.pop()


class Solution:

	def preToInfix(self, exp):
		exp = exp[::-1]
		stack = []
		for i in exp:
			if i >= 'a' and i <= 'z' or (i >= 'A' and i <= 'Z') or (i >= '0' and i <= '9'):
				stack.append(i)
			else:
				stack.append('(' + stack.pop() + i + stack.pop() + ')')
		return stack.pop()


class Solution:

	def preToInfix(self, pre_exp):
		a = pre_exp[::-1]
		l = []
		for j in a:
			if j.isalpha():
				l.append(j)
			else:
				a = l.pop()
				b = l.pop()
				l.append('(' + a + j + b + ')')
		return l[0]


class Solution:

	def preToInfix(self, pre):
		operator = ['+', '-', '*', '/', '^']
		i = len(pre) - 1
		stack = []
		while i >= 0:
			if pre[i] not in operator:
				stack.append(pre[i])
			if pre[i] in operator:
				exp = '(' + stack.pop() + pre[i] + stack.pop() + ')'
				stack.append(exp)
			i -= 1
		return stack.pop()


class Solution:

	def preToInfix(self, pre_exp):
		count = 0
		stack = []
		for ele in pre_exp[::-1]:
			if ele in ['^', '*', '/', '+', '-']:
				op1 = stack.pop()
				op2 = stack.pop()
				stack.append('(' + op1 + ele + op2 + ')')
			else:
				stack.append(ele)
		return stack.pop()


class Solution:

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

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

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

	def preToInfix(self, exp):
		exp_rev = exp[::-1]
		for i in exp_rev:
			if i in ['^', '+', '-', '*', '/']:
				exp2 = '('
				exp2 += self.pop()
				exp2 += i
				exp2 += self.pop()
				exp2 += ')'
				self.push(exp2)
			else:
				self.push(i)
		return exp2


class Solution:

	def preToInfix(self, pre_exp):
		s1 = []
		s2 = []
		for i in range(len(pre_exp)):
			s1.append(pre_exp[i])
		while len(s1) != 0:
			a = s1.pop()
			if len(a) > 1 or (ord(a) >= ord('A') and ord(a) <= ord('Z')) or (ord(a) >= ord('a') and ord(a) <= ord('z')):
				s2.append(a)
				continue
			if a in '*-/+^':
				op1 = s2.pop()
				op2 = s2.pop()
				exp = '(' + op1 + a + op2 + ')'
				s2.append(exp)
		return s2[0]


class Solution:

	def preToInfix(self, pre_exp):
		n = len(pre_exp) - 1
		st = []
		for i in range(n, -1, -1):
			ch = pre_exp[i]
			if ch in '^/*+-':
				A = st.pop()
				B = st.pop()
				exp = '(' + A + ch + B + ')'
				st.append(exp)
			else:
				st.append(ch)
		return st[-1]


class Solution:

	def preToInfix(self, pre_exp):
		pre_exp = pre_exp[::-1]
		stack = []
		for c in pre_exp:
			if c.isalpha():
				stack.append(c)
			else:
				ex = '(' + stack.pop() + c + stack.pop() + ')'
				stack.append(ex)
		return stack[0]


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		for i in range(len(pre_exp) - 1, -1, -1):
			if pre_exp[i] in ['+', '-', '*', '/']:
				s = '('
				s += stack.pop()
				s += pre_exp[i]
				s += stack.pop()
				s += ')'
				stack.append(s)
			else:
				stack.append(pre_exp[i])
		return stack[-1]


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		op = '^*/+-'
		for i in pre_exp[-1::-1]:
			if i not in op:
				stack.append(i)
			if i in op:
				exp = '(' + stack.pop() + i + stack.pop() + ')'
				stack.append(exp)
		return stack[0]


class Solution:

	def isOperator(self, c):
		if c == '*' or c == '+' or c == '-' or (c == '/') or (c == '^') or (c == '(') or (c == ')'):
			return True
		else:
			return False

	def preToInfix(self, pref_ix):
		stack = []
		i = len(pref_ix) - 1
		while i >= 0:
			if not self.isOperator(pref_ix[i]):
				stack.append(pref_ix[i])
				i -= 1
			else:
				prefix = '(' + stack.pop() + pref_ix[i] + stack.pop() + ')'
				stack.append(prefix)
				i -= 1
		return stack.pop()


class Solution:

	def preToInfix(self, pre_exp):
		lst = list(pre_exp)
		lst.reverse()
		infix = []
		stack = []
		for val in lst:
			if val in ['+', '-', '*', '/', '^']:
				if stack:
					one = stack.pop()
					second = stack.pop()
				stack.append('(' + one + val + second + ')')
			else:
				stack.append(val)
		return stack.pop()


class Solution:

	def preToInfix(self, pre_exp):
		operators = ['^', '*', '/', '+', '-']
		operaAndBraces = ['^', '*', '/', '+', '-', '(', ')']
		stk = []
		for i in reversed(range(len(pre_exp))):
			elem = pre_exp[i]
			if elem not in operaAndBraces:
				stk.append(elem)
			else:
				str = '(' + stk.pop() + elem + stk.pop() + ')'
				stk.append(str)
		return stk.pop()


class Solution:

	def preToInfix(self, s):
		(i, l) = (0, len(s))
		stack = []
		while i < l:
			if len(stack) >= 3 and stack[-3] in '/+-*' and (stack[-1] not in '/+-*') and (stack[-2] not in '/+-*'):
				while len(stack) >= 3 and stack[-3] in '/+-*' and (stack[-1] not in '/+-*') and (stack[-2] not in '/+-*'):
					b = stack.pop()
					a = stack.pop()
					stack.append('(' + a + stack.pop() + b + ')')
			stack.append(s[i])
			i += 1
		while len(stack) >= 3 and stack[-3] in '/+-*' and (stack[-1] not in '/+-*') and (stack[-2] not in '/+-*'):
			b = stack.pop()
			a = stack.pop()
			stack.append('(' + a + stack.pop() + b + ')')
		return stack[-1]


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		for ch in pre_exp[::-1]:
			if ch.isalnum():
				stack.append(ch)
			else:
				stack.append('(' + stack.pop() + ch + stack.pop() + ')')
		return stack.pop()


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		for v in pre_exp[::-1]:
			if v.isalnum():
				stack.append(v)
			else:
				stack.append('(' + stack.pop() + v + stack.pop() + ')')
		return stack[0]


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		top = -1
		infix = ''
		for v in pre_exp[::-1]:
			if v.isdigit() or v.isalnum():
				stack.append(v)
				top += 1
			else:
				A = stack.pop()
				B = stack.pop()
				infix = '(' + A + v + B + ')'
				stack.append(infix)
				top -= 1
		return infix


class Solution:

	def preToInfix(self, pre):
		ops = {'+', '-', '/', '*'}
		pre = pre[::-1]
		stack = []
		for i in range(len(pre)):
			if pre[i] in ops:
				a = stack.pop()
				stack.pop()
				b = stack.pop()
				stack.append('(' + a + pre[i] + b + ')')
			else:
				stack.append('(')
				stack.append(pre[i])
		stack = stack[1]
		return stack


class Solution:

	def preToInfix(self, pre_exp):
		lis = []
		for i in pre_exp[::-1]:
			if i.isalpha():
				lis.append(i)
			else:
				z = lis.pop()
				y = lis.pop()
				lis.append('(' + z + i + y + ')')
		return lis[0]


def evalu(exp, left, right):
	return '(' + left + exp + right + ')'

class Solution:

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

	def preToInfix(self, pre_exp):
		pre_exp = pre_exp[::-1]
		for i in pre_exp:
			if i is '+':
				left = self.stack.pop()
				right = self.stack.pop()
				val = evalu('+', left, right)
				self.stack.append(val)
			elif i is '-':
				left = self.stack.pop()
				right = self.stack.pop()
				val = evalu('-', left, right)
				self.stack.append(val)
			elif i is '*':
				left = self.stack.pop()
				right = self.stack.pop()
				val = evalu('*', left, right)
				self.stack.append(val)
			elif i is '/':
				left = self.stack.pop()
				right = self.stack.pop()
				val = evalu('/', left, right)
				self.stack.append(val)
			else:
				self.stack.append(i)
		return self.stack.pop()


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

	def preToInfix(self, pre_exp):
		stack = []
		for idx in range(len(pre_exp) - 1, -1, -1):
			char = pre_exp[idx]
			if char in Solution.precedence:
				op1 = stack.pop()
				op2 = stack.pop()
				res = '(' + op1 + char + op2 + ')'
				stack.append(res)
			else:
				stack.append(char)
		res = stack[-1]
		return res


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		operators = set(['+', '-', '*', '/', '^'])
		for i in range(len(pre_exp) - 1, -1, -1):
			if pre_exp[i] in operators:
				operand1 = stack.pop()
				operand2 = stack.pop()
				exp = '(' + operand1 + pre_exp[i] + operand2 + ')'
				stack.append(exp)
			else:
				stack.append(pre_exp[i])
		return stack.pop()


class Solution:

	def preToInfix(self, pre_exp):
		l = ['+', '-', '*', '/', '^']
		s = []
		pre_exp = pre_exp[::-1]
		for i in pre_exp:
			if i in l:
				a = s.pop()
				b = s.pop()
				c = '(' + a + i + b + ')'
				s.append(c)
			else:
				s.append(i)
		return ''.join((i for i in s))


class Solution:

	def preToInfix(self, pre_exp):
		(res, stack) = ([], [])
		for i in pre_exp:
			if ord('A') <= ord(i) <= ord('Z') or ord('a') <= ord(i) <= ord('z'):
				res.append(i)
				while stack and stack[-1] == '(':
					res.append(')')
					stack.pop()
				if stack:
					res.append(stack.pop())
			else:
				res.append('(')
				stack.append('(')
				stack.append(i)
		return ''.join(res)


class Solution:

	def preToInfix(self, pre_exp):
		exp = pre_exp[::-1]
		stack = []
		for i in range(len(exp)):
			if exp[i] >= 'a' and exp[i] <= 'z' or (exp[i] >= 'A' and exp[i] <= 'Z'):
				stack.append(exp[i])
			else:
				a = stack.pop()
				b = stack.pop()
				res = '(' + a + exp[i] + b + ')'
				stack.append(res)
		return stack[0]


class Solution:

	def preToInfix(self, arr):
		stack = []
		for i in range(len(arr) - 1, -1, -1):
			if self.isChr(arr[i]):
				stack.append(arr[i])
			if self.isOpr(arr[i]):
				first = stack.pop()
				secnd = stack.pop()
				res = '(' + first + arr[i] + secnd + ')'
				stack.append(res)
		return stack.pop()

	def isChr(self, ch):
		if ch >= 'a' and ch <= 'z' or (ch >= 'A' and ch <= 'Z') or (ch >= '0' and ch <= '9'):
			return 1
		return 0

	def isOpr(self, ch):
		opr = ['+', '-', '*', '/', '^']
		if ch in opr:
			return 1
		return 0


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		s = ''
		for i in pre_exp[::-1]:
			s = ''
			if i not in '^*?()+-/':
				stack.append(i)
			else:
				p = ''
				q = ''
				if stack:
					p = stack.pop()
				if stack:
					q = stack.pop()
				if p or q:
					s = s + '(' + p + i + q + ')'
				else:
					s = s + p + i + q
				stack.append(s)
		return s


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		exp = pre_exp[::-1]
		for i in exp:
			if i in '^*/+-':
				temp = '(' + stack.pop() + i + stack.pop() + ')'
				stack.append(temp)
			else:
				stack.append(i)
		return stack[-1]


class Solution:

	def preToInfix(self, pre_exp):
		pre_exp = pre_exp[::-1]
		st = []
		for i in pre_exp:
			if i in '*+-/^':
				if len(st) >= 2:
					second = st.pop()
					first = st.pop()
					st.append(')' + first + i + second + '(')
			else:
				st.append(i)
		return st.pop()[::-1]


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		operators = set(['+', '-', '*', '/', '^'])
		for i in range(len(pre_exp) - 1, -1, -1):
			if pre_exp[i] in operators:
				op1 = stack.pop()
				op2 = stack.pop()
				exp = '(' + op1 + pre_exp[i] + op2 + ')'
				stack.append(exp)
			else:
				stack.append(pre_exp[i])
		return stack.pop()


class Solution:

	def preToInfix(self, pre_exp):
		ll = []
		for i in range(len(pre_exp) - 1, -1, -1):
			if pre_exp[i] in '*-/+':
				l = ll.pop(-1)
				r = ll.pop(-1)
				dat = '(' + l + pre_exp[i] + r + ')'
				ll.append(dat)
			else:
				ll.append(pre_exp[i])
		return ll[0]


class Solution:

	def preToInfix(self, pre_exp):
		st = []
		for i in pre_exp[::-1]:
			if i.isalnum():
				st.append(i)
			else:
				o1 = st.pop()
				o2 = st.pop()
				inf = '(' + o1 + i + o2 + ')'
				st.append(inf)
		return st.pop()


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		operators = set(['+', '-', '*', '/', '^'])
		for i in pre_exp[::-1]:
			if i in operators:
				op1 = stack.pop()
				op2 = stack.pop()
				stack.append('({}{}{})'.format(op1, i, op2))
			else:
				stack.append(i)
		return stack[-1]


class Solution:

	def is_operator(self, c):
		if c == '+' or c == '-' or c == '*' or (c == '/') or (c == '^'):
			return True
		else:
			return False

	def preToInfix(self, exp):
		exp = exp[::-1]
		stack = []
		for c in exp:
			if self.is_operator(c):
				op1 = stack.pop()
				op2 = stack.pop()
				stack.append('(' + op1 + c + op2 + ')')
			else:
				stack.append(c)
		return stack.pop()


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		i = len(pre_exp) - 1
		list = ['+', '-', '*', '/', '^']
		str = ''
		while i >= 0:
			if pre_exp[i] not in list:
				stack.append(pre_exp[i])
				i -= 1
			else:
				str = '(' + stack.pop() + pre_exp[i] + stack.pop() + ')'
				stack.append(str)
				i -= 1
		temp = stack.pop()
		return temp


class Solution:

	def preToInfix(self, pre_exp):
		pre_exp = pre_exp[::-1]
		stack = []
		for i in pre_exp:
			if i.isalpha():
				stack.append(i)
			else:
				exp = i
				two = stack.pop()
				one = stack.pop()
				new = ')' + one + i + two + '('
				stack.append(new)
		return stack[0][::-1]


class Solution:

	def preToInfix(self, pre_exp):
		s = []
		for i in pre_exp[::-1]:
			if i in ['*', '+', '-', '/']:
				t1 = s.pop()
				t2 = s.pop()
				s.append('(' + t1 + i + t2 + ')')
			else:
				s.append(i)
		return ''.join(s)


class Solution:

	def preToInfix(self, pre_exp):
		pre_exp = pre_exp[::-1]
		a = []
		res = ''
		for i in range(len(pre_exp)):
			if pre_exp[i].isalpha():
				a.append(pre_exp[i])
			else:
				first = a.pop()
				second = a.pop()
				res = '(' + first + pre_exp[i] + second + ')'
				a.append(res)
		return a[-1]


class Solution:

	def preToInfix(self, pre_exp):
		pre_exp = pre_exp[::-1]
		stack = []
		res = ''
		for i in range(len(pre_exp)):
			if pre_exp[i].isalpha():
				stack.append(pre_exp[i])
			else:
				first = stack.pop()
				sec = stack.pop()
				res = '(' + first + pre_exp[i] + sec + ')'
				stack.append(res)
		ans = stack[-1]
		return ans


class Solution:

	def preToInfix(self, pre_exp):
		prefix = list(pre_exp)
		prefix.reverse()
		stack = []
		str = ''
		for i in range(len(prefix)):
			if prefix[i] not in {'+', '*', '-', '/'}:
				stack.append(prefix[i])
			else:
				if stack:
					op1 = stack.pop()
				if stack:
					op2 = stack.pop()
				str += '(' + op1 + prefix[i] + op2 + ')'
				stack.append(str)
				str = ''
		return stack[-1]


class Solution:

	def preToInfix(self, s1):
		str = ''
		st = []
		for i in range(len(s1) - 1, -1, -1):
			if s1[i].isalpha():
				st.append(s1[i])
			else:
				str1 = st.pop()
				str2 = st.pop()
				str = '(' + str1 + s1[i] + str2 + ')'
				st.append(str)
		str = st.pop()
		return str


def is_operand(x):
	return ord(x) >= ord('a') and ord(x) <= ord('z') or (ord(x) >= ord('A') and ord(x) <= ord('Z'))

class Solution:

	def preToInfix(self, pre_exp):
		pre_exp = pre_exp[::-1]
		st = []
		for i in pre_exp:
			if is_operand(i):
				st.append(i)
			else:
				if len(st) < 2:
					raise Exception('invalid Expression')
				s1 = st.pop()
				s2 = st.pop()
				cur = '(' + s1 + i + s2 + ')'
				st.append(cur)
		return ''.join(st)


class Solution:

	def preToInfix(self, pre_exp):
		precedence = {'^': 3, '+': 1, '-': 1, '*': 2, '/': 2}
		st = []
		s = ''
		for i in pre_exp[::-1]:
			if i in precedence.keys():
				x = st.pop()
				y = st.pop()
				st.append('(' + x + i + y + ')')
			else:
				st.append(i)
		string = ''.join(st)
		return string


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		for i in range(len(pre_exp) - 1, -1, -1):
			char = pre_exp[i]
			if char.isalnum():
				stack.append(char)
			elif char in '+-*/^':
				if len(stack) < 2:
					return 'Invalid expression'
				op1 = stack.pop()
				op2 = stack.pop()
				subexp = '(' + op1 + char + op2 + ')'
				stack.append(subexp)
			else:
				return 'Invalid expression'
		if len(stack) != 1:
			return 'Invalid expression'
		return stack.pop()


from collections import deque

class Solution:

	def preToInfix(self, pre_exp):
		stack = deque()
		for i in range(len(pre_exp) - 1, -1, -1):
			if pre_exp[i].isalpha():
				stack.append(pre_exp[i])
			else:
				expr1 = stack.pop()
				expr2 = stack.pop()
				new_expr = '(' + expr1 + pre_exp[i] + expr2 + ')'
				stack.append(new_expr)
		return stack.pop()


class Solution:

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

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

	def pop(self):
		return self.l.pop()

	def preToInfix(self, pre_exp):
		for i in reversed(pre_exp):
			if i == '+':
				a = self.pop()
				b = self.pop()
				self.push('(' + a + '+' + b + ')')
			elif i == '-':
				a = self.pop()
				b = self.pop()
				self.push('(' + a + '-' + b + ')')
			elif i == '*':
				a = self.pop()
				b = self.pop()
				self.push('(' + a + '*' + b + ')')
			elif i == '/':
				a = self.pop()
				b = self.pop()
				self.push('(' + a + '/' + b + ')')
			else:
				self.push(i)
		ss = ''
		for i in self.l:
			ss = ss + '' + i
		return ss


class Solution:

	def preToInfix(self, ex):
		s = []
		ex = ex[::-1]
		for ch in ex:
			if ch.isalnum():
				s += ch
			else:
				o = ''
				o = '(' + s[-1] + ch + s[-2] + ')'
				s.pop()
				s.pop()
				s.append(o)
		return o


from collections import deque

class Solution:

	def preToInfix(self, pre_exp):
		operators = {'*', '-', '^', '/', '+', '%'}
		stack = deque()
		exp = pre_exp
		for i in range(len(exp) - 1, -1, -1):
			symbol = exp[i]
			if symbol in operators:
				subexpr = '(' + str(stack.pop()) + str(symbol) + str(stack.pop()) + ')'
				stack.append(subexpr)
			else:
				stack.append(symbol)
		return stack.pop()


class Solution:

	def preToInfix(self, string):
		stack = []
		operators = ['-', '/', '+', '*']
		reversed_string = string[::-1]
		for char in reversed_string:
			if char not in operators:
				stack.append(char)
			else:
				popped_first_char = stack.pop()
				new_char_str = ''
				popped_second_char = stack.pop()
				new_char_str = '(' + new_char_str + popped_first_char + char + popped_second_char + ')'
				stack.append(new_char_str)
		return stack[0]


class Solution:

	def preToInfix(self, exp):
		exp = exp[::-1]
		stack = []
		ans = ''
		for ch in exp:
			if ch.isalnum():
				stack.append(ch)
			else:
				first = stack.pop()
				second = stack.pop()
				stack.append('(' + first + ch + second + ')')
		return stack[-1]


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		n = len(pre_exp)
		for i in range(n - 1, -1, -1):
			c = pre_exp[i]
			if isOperator(c):
				op1 = stack.pop()
				op2 = stack.pop()
				stack.append('(' + op1 + c + op2 + ')')
			else:
				stack.append(c)
		return stack[0]

def isOperator(c):
	if c == '+' or c == '-' or c == '*' or (c == '/') or (c == '^'):
		return True
	else:
		return False


class Solution:

	def preToInfix(self, pre_exp):
		res = []
		ans = ''
		for i in pre_exp[::-1]:
			if i.isalpha() or i.isnumeric():
				res.append(i)
			else:
				a1 = res.pop()
				a2 = res.pop()
				ans = '(' + a1 + i + a2 + ')'
				res.append(ans)
		return ans


class Solution:

	def isOp(self, c):
		if c == '*' or c == '+' or c == '-' or (c == '/') or (c == '^') or (c == '(') or (c == ')'):
			return True
		else:
			return False

	def preToInfix(self, pre_exp):
		stack = []
		i = len(pre_exp) - 1
		while i >= 0:
			if not self.isOp(pre_exp[i]):
				stack.append(pre_exp[i])
				i -= 1
			else:
				str = '(' + stack.pop() + pre_exp[i] + stack.pop() + ')'
				stack.append(str)
				i -= 1
		return stack.pop()


class Solution:

	def preToInfix(self, pre_exp):
		st = []
		s = ''
		l = len(pre_exp)
		for i in range(-1, -l - 1, -1):
			if pre_exp[i] == '*' or pre_exp[i] == '/' or pre_exp[i] == '+' or (pre_exp[i] == '-'):
				n1 = st.pop()
				n2 = st.pop()
				st.append('@' + n1 + pre_exp[i] + n2 + '#')
			else:
				st.append(pre_exp[i])
		pre = st[0]
		pre = pre.replace('@', '(')
		pre = pre.replace('#', ')')
		res = pre
		return res


class Solution:

	def preToInfix(self, pre):
		stack = []
		for i in range(len(pre) - 1, 0, -1):
			if pre[i].isalpha():
				stack.append(pre[i])
			else:
				first = stack.pop()
				second = stack.pop()
				op = '(' + first + pre[i] + second + ')'
				stack.append(op)
		res = '(' + stack.pop() + pre[0] + stack.pop() + ')'
		return res


class Solution:

	def preToInfix(self, pre_exp):
		Operators = ['+', '-', '*', '/', '(', ')', '^']
		pre_exp = pre_exp[::-1]
		stack = []
		for character in pre_exp:
			if character not in Operators:
				stack.append(character)
			else:
				res = ''
				res += '('
				A = stack.pop()
				B = stack.pop()
				res += A
				res += character
				res += B
				res += ')'
				stack.append(res)
		return stack.pop()


class Solution:

	def preToInfix(self, pre_exp):
		stack = []
		substr = ''
		exp = ''
		operators = ['+', '^', '%', '-', '*', '/']
		for i in range(len(pre_exp) - 1, -1, -1):
			ele = pre_exp[i]
			if ele in operators:
				stack.append('(' + stack.pop() + ele + stack.pop() + ')')
			else:
				stack.append(ele)
		return stack.pop()


class Solution:

	def preToInfix(self, s):

		def isOperator(x):
			return ch in '+-*/^%'
		stack = []
		n = len(s)
		for i in range(n - 1, -1, -1):
			ch = s[i]
			if isOperator(ch):
				op1 = stack.pop()
				op2 = stack.pop()
				temp = '(' + op1 + ch + op2 + ')'
				stack.append(temp)
			else:
				stack.append(ch)
		return stack.pop()


def is_operand(i):
	return i.isalpha()

class Solution:

	def preToInfix(self, pre_exp):
		(s, n) = (pre_exp, len(pre_exp))
		stack = []
		for i in range(n - 1, -1, -1):
			if is_operand(s[i]):
				stack.append(s[i])
			else:
				a = stack.pop()
				b = stack.pop()
				c = '(' + a + s[i] + b + ')'
				stack.append(c)
		return stack[-1]


class Solution:

	def preToInfix(self, exp):
		st = []
		exp = exp[::-1]
		for ch in exp:
			if ch in 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmonpqrstuvwxyz':
				st += [ch]
			else:
				tmp = '(' + st[-1] + ch + st[-2] + ')'
				st.pop()
				st.pop()
				st.append(tmp)
		return st.pop()


class Solution:

	def __init__(self):
		self.top = -1
		self.array = []

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

	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()

	def preToInfix(self, exp):
		i = len(exp) - 1
		while i >= 0:
			if self.isOperand(exp[i]):
				self.push(exp[i])
			else:
				str = '(' + self.pop() + exp[i] + self.pop() + ')'
				self.push(str)
			i -= 1
		return self.pop()


class Solution:

	def preToInfix(self, pre_exp):
		pre_exp = list(pre_exp)
		while len(pre_exp) != 1:
			for x in range(len(pre_exp) - 3, -1, -1):
				sym = pre_exp[x]
				if not sym.isalnum() and len(sym) == 1:
					pre_exp[x] = '(' + pre_exp[x + 1] + pre_exp[x] + pre_exp[x + 2] + ')'
					del pre_exp[x + 1]
					del pre_exp[x + 1]
		return pre_exp[0]


class Solution:

	def preToInfix(self, pre_exp):
		pre_exp = pre_exp[::-1]
		st = []
		operators = set(['-', '+', '*', '/', '^'])
		for i in range(len(pre_exp)):
			if pre_exp[i] in operators:
				operand1 = st.pop()
				operand2 = st.pop()
				new_exp = '(' + operand1 + pre_exp[i] + operand2 + ')'
				st.append(new_exp)
			else:
				st.append(pre_exp[i])
		return st.pop()


class Solution:

	def preToInfix(self, pre_exp):
		operators = ['+', '-', '*', '/', '^']
		pre_exp = pre_exp[::-1]
		stack = []
		for c in pre_exp:
			if c not in operators:
				stack.append(c)
			else:
				exp = '(' + stack.pop() + c + stack.pop() + ')'
				stack.append(exp)
		return stack[-1]