You are given a string that represents the postfix form of a valid mathematical expression. Convert it to its infix form.
Example:
Input:
ab*c+ 
Output: 
((a*b)+c)
Explanation: 
The above output is its valid infix form.
Your Task:
Complete the function string postToInfix(string post_exp), which takes a postfix string as input and returns its infix form.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
3<=post_exp.length()<=10^{4}

Difficulty: MEDIUM
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Starter code:
#User function Template for python3



class Solution:

    def postToInfix(self, postfix):

        # Code here

Solutions:
class Solution:

	def postToInfix(self, postfix):
		stk = []
		for i in postfix:
			if i in ['*', '/', '-', '+', '^']:
				op1 = stk.pop()
				op2 = stk.pop()
				stk.append('(' + op2 + i + op1 + ')')
			else:
				stk.append(i)
		return stk.pop()


class Solution:

	def postToInfix(self, postfix):
		st = []
		opr = {'^', '*', '/', '+', '-'}
		for char in postfix:
			if char.isalnum():
				st.append(char)
			else:
				a = st.pop()
				b = st.pop()
				st.append('(' + b + char + a + ')')
		return st[0]


class Solution:

	def postToInfix(self, postfix):
		stack = []
		operators = {'^', '*', '/', '+', '-'}
		for char in postfix:
			if not char in operators:
				stack.append(char)
			else:
				beta = stack.pop()
				alpha = stack.pop()
				stack.append('(' + alpha + char + beta + ')')
		return stack[0]


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for i in postfix:
			if i.isalnum():
				stack.append(i)
			else:
				x = stack.pop()
				y = stack.pop()
				stack.append('(' + y + i + x + ')')
		return stack.pop()


class Solution:

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


class Solution(object):

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

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

	def postToInfix(self, postfix):
		size = len(postfix)
		for index in range(size):
			char = postfix[index]
			if not self.isOperator(char):
				self.stack.append(char)
			else:
				operand1 = self.stack.pop()
				operand2 = self.stack.pop()
				exp = '(' + operand2 + char + operand1 + ')'
				self.stack.append(exp)
		return self.stack.pop()


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for i in postfix:
			if i not in ('*', '-', '+', '^', '/'):
				stack.append(i)
			else:
				a = stack.pop()
				b = stack.pop()
				stack.append('(' + b + i + a + ')')
		return stack[0]


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for c in postfix:
			if c == '+' or c == '-' or c == '*' or (c == '/'):
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append('(' + op1 + c + op2 + ')')
			else:
				stack.append(c)
		return stack[0]


class Solution:

	def postToInfix(self, postfix):
		x = []
		s = postfix
		for i in range(len(s)):
			if s[i].isalpha():
				x.append(s[i])
			else:
				a = x.pop()
				b = x.pop()
				r = '(' + b + s[i] + a + ')'
				x.append(r)
		return x[0]


class Solution:

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


class Solution:

	def postToInfix(self, exp):
		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:
				A = stack.pop()
				B = stack.pop()
				stack.append('(' + B + i + A + ')')
		return stack.pop()


class Solution:

	def postToInfix(self, postfix):
		op = {'-', '+', '*', '/', '^'}
		sta = []
		for ele in postfix:
			if not sta:
				sta.append(ele)
			elif ele in op:
				se = sta.pop()
				fe = sta.pop()
				ans = '(' + fe + ele + se + ')'
				sta.append(ans)
			else:
				sta.append(ele)
		return sta[-1]


class Solution:

	def postToInfix(self, postfix):
		stack = []
		operator = ['+', '-', '*', '/', '^']
		for i in postfix:
			if i not in operator:
				stack.append(i)
			if i in operator:
				exp = '(' + stack[-2] + i + stack[-1] + ')'
				stack.pop()
				stack.pop()
				stack.append(exp)
		return stack.pop()


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for ele in postfix:
			if ele in ['^', '*', '/', '+', '-']:
				op1 = stack.pop()
				op2 = stack.pop()
				stack.append('(' + op2 + ele + op1 + ')')
			else:
				stack.append(ele)
		return stack.pop()


class Solution:

	def postToInfix(self, exp):
		stack = []
		for i in exp:
			if i.isalpha():
				stack.append(i)
			else:
				val1 = stack.pop()
				val2 = stack.pop()
				stack.append('(' + val2 + i + val1 + ')')
		return stack[0]


class Solution:

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

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

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

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


from collections import deque

class Solution:

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


class Solution:

	def postToInfix(self, postfix):
		st = []
		for ch in postfix:
			if ch in '^/*+-':
				A = st.pop()
				B = st.pop()
				exp = '(' + B + ch + A + ')'
				st.append(exp)
			else:
				st.append(ch)
		return st[-1]


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for i in postfix:
			if i in ['+', '-', '*', '/']:
				temp = stack.pop()
				s = '(' + stack.pop() + i + temp + ')'
				stack.append(s)
			else:
				stack.append(i)
		return stack[0]


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for val in postfix:
			if val in ['+', '-', '*', '/', '^']:
				if stack:
					second = stack.pop()
					one = stack.pop()
				stack.append('(' + one + val + second + ')')
			else:
				stack.append(val)
		return stack.pop()


class Solution:

	def postToInfix(self, postfix):
		stk = []
		for elem in postfix:
			if elem.isalpha():
				stk.insert(0, elem)
			else:
				op1 = stk.pop(0)
				op2 = stk.pop(0)
				str = '(' + op2 + elem + op1 + ')'
				stk.insert(0, str)
		return stk[-1]


class Solution:

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


class Solution:

	def postToInfix(self, p):
		from queue import deque
		d = deque()
		z = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
		for i in range(len(p)):
			if p[i] in z:
				d += [p[i]]
			else:
				A = d.pop()
				B = d.pop()
				k = '(' + B + p[i] + A + ')'
				d += [k]
		return d[0]


class Solution:

	def postToInfix(self, x):
		stack = []
		for i in x:
			if i.isalpha() or i.isdigit():
				stack.append(i)
			elif i in '*/-+^':
				a = stack.pop()
				b = stack.pop()
				stack.append('(' + b + i + a + ')')
		return stack.pop()


class Solution:

	def postToInfix(self, postfix):
		st = []
		for i in range(0, len(postfix)):
			s = ''
			if postfix[i] == '*' or postfix[i] == '+' or postfix[i] == '-' or (postfix[i] == '/') or (postfix[i] == '^'):
				a = st[-1]
				st.pop()
				b = st[-1]
				st.pop()
				s = '(' + b + postfix[i] + a + ')'
				st.append(s)
			else:
				st.append(postfix[i])
		return s


class Solution:

	def postToInfix(self, postfix):
		stack = []
		A = ''
		B = ''
		s = ''
		for i in postfix:
			if i not in '*/^()+-':
				stack.append(i)
			else:
				op = i
				A = stack.pop()
				B = stack.pop()
				stack.append('(' + B + op + A + ')')
		return stack[0]


class Solution:

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


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

	def postToInfix(self, postfix):
		stack = []
		infix = ''
		for char in postfix:
			if char in Solution.precedence:
				op2 = stack.pop()
				op1 = stack.pop()
				res = '(' + op1 + char + op2 + ')'
				stack.append(res)
			else:
				stack.append(char)
		return stack.pop()


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

class Solution:

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

	def postToInfix(self, postfix):
		for i in postfix:
			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:

	def postToInfix(self, postfix):
		stack = []
		operators = set(['+', '-', '*', '/', '^'])
		for char in postfix:
			if char not in operators:
				stack.append(char)
			else:
				operand2 = stack.pop()
				operand1 = stack.pop()
				exp = '(' + operand1 + char + operand2 + ')'
				stack.append(exp)
		return stack.pop()


class Solution:

	def postToInfix(self, postfix):
		s = []
		for i in postfix:
			if i.isalpha():
				s.append(i)
			else:
				(r, l) = (s.pop(), s.pop())
				s.append('(' + l + i + r + ')')
		return s[0]


class Solution:

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


class Solution:

	def postToInfix(self, postfix):
		stack = []
		s = ''
		for i in postfix:
			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 + '(' + q + i + p + ')'
				else:
					s = s + q + i + p
				stack.append(s)
		return s


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for i in postfix:
			if i in '^*/+-':
				o2 = stack.pop()
				o1 = stack.pop()
				temp = '(' + o1 + i + o2 + ')'
				stack.append(temp)
			else:
				stack.append(i)
		return stack[-1]


class Solution:

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

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

	def postToInfix(self, postfix):
		res = ''
		stack = []
		n = len(postfix)
		for i in range(n):
			if self.isOprand(postfix[i]):
				stack.append(postfix[i])
			elif self.isOprator(postfix[i]):
				A = stack.pop()
				B = stack.pop()
				res = '(' + B + postfix[i] + A + ')'
				stack.append(res)
		return res


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for i in postfix:
			if i in '+-/*^':
				if len(stack) >= 2:
					b = stack.pop()
					a = stack.pop()
					stack.append('(' + a + i + b + ')')
			else:
				stack.append(i)
		return stack.pop()


def isOperand(x):
	return x >= 'a' and x <= 'z' or (x >= 'A' and x <= 'Z') or (x >= '0' and x <= '9')

class Solution:

	def postToInfix(self, postfix):
		s = []
		for i in postfix:
			if isOperand(i):
				s.insert(0, i)
			else:
				op1 = s[0]
				s.pop(0)
				op2 = s[0]
				s.pop(0)
				s.insert(0, '(' + op2 + i + op1 + ')')
		return s[0]


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for ch in postfix:
			if ch.isalnum():
				stack.append(ch)
			else:
				op2 = stack.pop()
				op1 = stack.pop()
				exp = '(' + op1 + ch + op2 + ')'
				stack.append(exp)
		return stack[-1]


class Solution:

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


class Solution:

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


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for i in range(len(postfix)):
			if postfix[i] == '+' or postfix[i] == '-' or postfix[i] == '*' or (postfix[i] == '/'):
				str = ')' + stack.pop() + postfix[i] + stack.pop() + '('
				stack.append(str)
			else:
				stack.append(postfix[i])
		str = stack.pop()
		return str[::-1]


class Solution:

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

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


class Solution:

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


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for i in postfix:
			if i in ['*', '+', '-', '/']:
				t1 = stack.pop()
				t2 = stack.pop()
				stack.append('(' + t2 + i + t1 + ')')
			else:
				stack.append(i)
		return ''.join(stack)


class Solution:

	def postToInfix(self, postfix):
		l = ['+', '*', '-', '/']
		a = []
		res = ''
		for i in range(len(postfix)):
			if postfix[i] not in l:
				a.append(postfix[i])
			else:
				first = a.pop()
				second = a.pop()
				res = '(' + second + postfix[i] + first + ')'
				a.append(res)
		return a[-1]


class Solution:

	def postToInfix(self, postfix):
		stack = []
		res = ''
		for i in postfix:
			if i.isalpha():
				stack.append(i)
			else:
				first = stack.pop()
				second = stack.pop()
				res = '(' + second + i + first + ')'
				stack.append(res)
		return stack[-1]


class Solution:

	def postToInfix(self, postfix):
		stack = []
		res = ''
		for i in range(len(postfix)):
			if postfix[i].isalpha():
				stack.append(postfix[i])
			else:
				first = stack.pop()
				second = stack.pop()
				res = '(' + second + postfix[i] + first + ')'
				stack.append(res)
		ans = ''.join(stack)
		return ans


class Solution:

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


class Solution:

	def postToInfix(self, exp):
		st = []
		str = ''
		for s1 in exp:
			if s1.isalpha():
				st.append(s1)
			else:
				str2 = st.pop()
				str1 = st.pop()
				str = '(' + str1 + s1 + 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 postToInfix(self, postfix):
		st = []
		for i in postfix:
			if is_operand(i):
				st.append(i)
			else:
				if len(st) < 2:
					raise Exception('invalid expression')
				s1 = st.pop()
				s2 = st.pop()
				cur = '(' + s2 + i + s1 + ')'
				st.append(cur)
		return ''.join(st)


class Solution:

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


from collections import deque

class Solution:

	def postToInfix(self, postfix):
		stack = deque()
		for k in postfix:
			if k.isalpha():
				stack.append(k)
			else:
				expr1 = stack.pop()
				expr2 = stack.pop()
				new_expr = '(' + expr2 + k + expr1 + ')'
				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 postToInfix(self, postfix):
		for i in postfix:
			if i == '+':
				a = self.pop()
				b = self.pop()
				self.push('(' + b + '+' + a + ')')
			elif i == '-':
				a = self.pop()
				b = self.pop()
				self.push('(' + b + '-' + a + ')')
			elif i == '*':
				a = self.pop()
				b = self.pop()
				self.push('(' + b + '*' + a + ')')
			elif i == '/':
				a = self.pop()
				b = self.pop()
				self.push('(' + b + '/' + a + ')')
			else:
				self.push(i)
		ss = ''
		for i in self.l:
			ss = ss + '' + i
		return ss


class Solution:

	def postToInfix(self, ex):
		st = []
		s = ''
		for ch in ex:
			s = ''
			if ch.isalnum():
				st.append(ch)
			else:
				s += '('
				s += str(st[-2])
				s += ch
				s += str(st[-1])
				s += ')'
				st.pop()
				st.pop()
				st.append(s)
		s1 = ''
		for i in range(len(st)):
			s1 += st[i]
		return s1


from collections import deque

class Solution:

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


class Solution:

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


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for char in postfix:
			if char.isalpha():
				stack.append(char)
			else:
				op2 = stack.pop()
				op1 = stack.pop()
				exp = '(' + op1 + char + op2 + ')'
				stack.append(exp)
		return stack[0]


class Solution:

	def postToInfix(self, postfix):
		ans = ''
		res = []
		for i in postfix:
			if i.isalpha() or i.isnumeric():
				res.append(i)
			else:
				a1 = res.pop()
				a2 = res.pop()
				ans = '(' + a2 + i + a1 + ')'
				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 postToInfix(self, postfix):
		stack = []
		for i in postfix:
			if not self.isOp(i):
				stack.insert(0, i)
			else:
				op1 = stack[0]
				stack.pop(0)
				op2 = stack[0]
				stack.pop(0)
				str = '(' + op2 + i + op1 + ')'
				stack.insert(0, str)
		return stack[0]


class Solution:

	def postToInfix(self, postfix):
		st = []
		s = ''
		for i in postfix:
			if i == '*' or i == '/' or i == '+' or (i == '-'):
				n2 = st.pop()
				n1 = st.pop()
				st.append('@' + n1 + i + n2 + '#')
			else:
				st.append(i)
		i = st[0]
		i = i.replace('@', '(')
		i = i.replace('#', ')')
		res = i
		return res


class Solution:

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


class Solution:

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


class Solution:

	def postToInfix(self, postfix):
		stack = []
		operators = ['*', '^', '%', '+', '/', '-']
		for i in range(len(postfix)):
			symbol = postfix[i]
			if symbol in operators:
				a = stack.pop()
				b = stack.pop()
				stack.append('(' + b + symbol + a + ')')
			else:
				stack.append(symbol)
		return stack[0]


class Solution:

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

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

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

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

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

	def postToInfix(self, postfix):
		for i in postfix:
			if self.isOperand(i):
				self.push(i)
			else:
				op1 = self.pop()
				str = '(' + self.pop() + i + op1 + ')'
				self.push(str)
		return self.pop()


class Solution:

	def postToInfix(self, postfix):
		if not postfix:
			return ''
		st = []
		for ch in postfix:
			if ch in 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz':
				st += [ch]
			else:
				tmp = '(' + st[-2] + ch + st[-1] + ')'
				st.pop()
				st.pop()
				st.append(tmp)
		return st.pop()


class Solution:

	def postToInfix(self, postfix):
		st = []
		for i in postfix:
			if i.isalnum():
				st.append(i)
			else:
				op1 = st.pop()
				op2 = st.pop()
				result = '(' + op2 + i + op1 + ')'
				st.append(result)
		return st[0]


class Solution:

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


class Solution:

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


class Solution:

	def postToInfix(self, postfix):
		stack = []
		for i in postfix:
			if i.isalpha():
				stack.append(i)
			else:
				s = stack.pop()
				x = stack.pop()
				stack.append('(' + x + i + s + ')')
		return stack.pop()


class Solution:

	def postToInfix(self, postfix):
		s = []
		for i in postfix:
			if i.isalpha():
				s.append(i)
			else:
				op1 = s.pop()
				op2 = s.pop()
				t = '(' + op2 + i + op1 + ')'
				s.append(t)
		return s[0]