You are given a string that represents the prefix form of a valid mathematical expression. Convert it to its postfix form.
Example:
Input: 
*-A/BC-/AKL
Output: 
ABC/-AK/L-*
Explanation: 
The above output is its valid postfix form.
Your Task:
Complete the function preToPost(string pre_exp), which takes a prefix string as input and returns its postfix form.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
3<=pre_exp.length()<=100

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def preToPost(self, pre_exp):

        # Code here

Solutions:
class Solution:

	def preToPost(self, pre_exp):
		st = []
		opr = {'^', '*', '/', '+', '-'}
		for i in range(len(pre_exp) - 1, -1, -1):
			if pre_exp[i].isalnum():
				st.append(pre_exp[i])
			else:
				a = st.pop()
				b = st.pop()
				st.append(a + b + pre_exp[i])
		return st[0]


class Solution:

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


class Solution:

	def preToPost(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 + b + i)
		return s[0]


class Solution:

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


class Solution:

	def preToPost(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(x + y + pre[i])
			else:
				stack.append(pre[i])
		return stack[0]


class Solution(object):

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

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

	def preToPost(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() + self.stack.pop() + char
				self.stack.append(exp)
				index -= 1
		return self.stack.pop()


class Solution:

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


class Solution:

	def preToPost(self, pre_exp):
		stack = []
		for c in reversed(pre_exp):
			if c.isalnum():
				stack.append(c)
			elif c in '+-*/^':
				op1 = stack.pop()
				op2 = stack.pop()
				stack.append(op1 + op2 + c)
		return stack[-1]


class Solution:

	def preToPost(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() + stack.pop() + i)
		return stack.pop()


class Solution:

	def preToPost(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 + b + j)
		return l[0]


class Solution:

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


class Solution:

	def preToPost(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 + ')')
		exp = s[0]
		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


class Solution:

	def preToPost(self, pre_exp):
		s1 = []
		s2 = []
		p = dict()
		p['-'] = 1
		p['+'] = 1
		p['*'] = 2
		p['/'] = 2
		p['^'] = 3
		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)
		pre_exp = s2[0]
		stack = []
		s = ''
		for i in pre_exp:
			if i == '(':
				stack.append(i)
			if ord(i) >= ord('A') and ord(i) <= ord('Z') or (ord(i) >= ord('a') and ord(i) <= ord('z')):
				s += i
			if i in '*-+/^':
				while stack[len(stack) - 1] != '(' and p[stack[len(stack) - 1]] >= p[i]:
					s += stack.pop()
				stack.append(i)
			if i == ')':
				while stack[len(stack) - 1] != '(':
					s += stack.pop()
				stack.pop()
		return s


class Solution:

	def preToPost(self, pre_exp):
		s = pre_exp
		st = []
		for c in reversed(s):
			if c.isalpha() or c.isdigit():
				st.append(c)
			else:
				A = st.pop()
				B = st.pop()
				st.append(A + B + c)
		return st[-1]


class Solution:

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


class Solution:

	def preToPost(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() + stack.pop() + i
				stack.append(exp)
		return stack[0]


class Solution:

	def preToPost(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 + second + val)
			else:
				stack.append(val)
		return stack.pop()


class Solution:

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


class Solution:

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


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

	def preToPost(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 + op2 + char
				stack.append(res)
			else:
				stack.append(char)
		return stack.pop()


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

	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

	def preToPost(self, pre_exp):
		return self.InfixtoPostfix(self.preToInfix(pre_exp))


class Solution:

	def preToPost(self, pre_exp):
		operators = set(['+', '-', '*', '/', '^'])
		stack = []
		for c in reversed(pre_exp):
			if c in operators:
				op1 = stack.pop()
				op2 = stack.pop()
				stack.append(op1 + op2 + c)
			else:
				stack.append(c)
		return stack.pop()


class Solution:

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


import sys
sys.setrecursionlimit(10 ** 9)

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def isString(char):
	capital = ord('A') <= ord(char) and ord(char) <= ord('Z')
	small = ord('a') <= ord(char) and ord(char) <= ord('z')
	return capital or small

def postfix(Node):
	if Node == None:
		return ''
	return postfix(Node.left) + postfix(Node.right) + Node.data

class Solution:

	def preToPost(self, pre_exp):
		root = Node(pre_exp[0])
		stack = [root]
		if len(pre_exp) == 1:
			return pre_exp
		for i in range(1, len(pre_exp)):
			new_node = Node(pre_exp[i])
			while len(stack):
				if not stack[-1].left:
					stack[-1].left = new_node
					break
				elif not stack[-1].right:
					stack[-1].right = new_node
					break
				else:
					stack.pop()
			if not isString(pre_exp[i]):
				stack.append(new_node)
		return postfix(root)


class Solution:

	def preToPost(self, pre_exp):

		def InfixtoPostfix(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

		def preToInfix(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]
		return InfixtoPostfix(preToInfix(pre_exp))


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 preToPost(self, pre_exp):
		stack = []
		n = len(pre_exp)
		res = ''
		for i in range(n - 1, -1, -1):
			if self.isOprand(pre_exp[i]):
				stack.append(pre_exp[i])
			elif self.isOprator(pre_exp[i]):
				first = stack.pop()
				second = stack.pop()
				res = first + second + pre_exp[i]
				stack.append(res)
		return res


class Solution:

	def preToPost(self, pre_exp):
		stack = []
		for i in pre_exp[::-1]:
			if i in '+-*^/':
				if len(stack) >= 2:
					operand2 = stack.pop()
					operand1 = stack.pop()
					stack.append(operand2 + operand1 + i)
			else:
				stack.append(i)
		return stack.pop()


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def preToPost(self, pre_exp):
		stack = []
		for c in reversed(pre_exp):
			if c.isalnum():
				stack.append(c)
			else:
				op1 = stack.pop()
				op2 = stack.pop()
				stack.append(op1 + op2 + c)
		return stack[0]


class Solution:

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


class Solution:

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


class Solution:

	def preToPost(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
				op1 = stack.pop()
				op2 = stack.pop()
				subexp = op1 + op2 + char
				stack.append(subexp)
			else:
				return
		if len(stack) != 1:
			return
		return stack.pop()


class Solution:

	def preToPost(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 + op2 + prefix[i]
				stack.append(str)
				str = ''
		return stack[-1]


from collections import deque

class Solution:

	def preToPost(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 + expr2 + pre_exp[i]
				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 preToPost(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 preToPost(self, ex):
		s = []
		o = ''
		ex = ex[::-1]
		for ch in ex:
			if ch.isalnum():
				s.append(ch)
			else:
				o = ''
				o = s[-1] + s[-2] + ch
				s.pop()
				s.pop()
				s.append(o)
		return s[0]


class Solution:

	def preToPost(self, pre_exp):
		return self.InToPost(self.preToIn(pre_exp))

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

	def InToPost(self, pre_exp):
		d = dict()
		d['-'] = 1
		d['+'] = 1
		d['/'] = 2
		d['*'] = 2
		d['^'] = 3
		operand = ''
		precedance_stack = []
		for i in pre_exp:
			if i.isalnum():
				operand += i
			elif i == '(':
				precedance_stack.append(i)
			elif i == ')':
				while len(precedance_stack) > 0 and precedance_stack[-1] != '(':
					operand += precedance_stack.pop()
				precedance_stack.pop()
			else:
				while len(precedance_stack) > 0 and precedance_stack[-1] != '(' and (d[precedance_stack[-1]] >= d[i]):
					ch = precedance_stack.pop()
					operand += ch
				precedance_stack.append(i)
		while len(precedance_stack):
			operand += precedance_stack.pop()
		return operand


class Solution:

	def preToPost(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 + a2 + i
				res.append(ans)
		return ans


class Solution:

	def preToPost(self, pre_exp):
		OPS = '*/-+'
		stack = []
		for c in reversed(pre_exp):
			if c in OPS:
				left = stack.pop()
				right = stack.pop()
				stack.append(left + right + [c])
				continue
			stack.append([c])
		return ''.join(stack[0])


class Solution:

	def preToPost(self, pre_exp):
		st = []
		pre_exp = pre_exp[::-1]
		for i in pre_exp:
			if i == '*' or i == '/' or i == '+' or (i == '-'):
				n2 = st.pop()
				n1 = st.pop()
				st.append(i + n1 + n2)
			else:
				st.append(i)
		st[0] = st[0][::-1]
		return st[0]


class Solution:

	def preToPost(self, pre_exp):

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

		def InfixtoPostfix(exp):
			post = ''
			s = []
			op = ('+', '-', '/', '*', '^')
			Prec = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
			for i in exp:
				if i.isalpha():
					post = post + i
				elif i == '(':
					s.append(i)
				elif i == ')':
					while len(s) != 0 and s[-1] != '(':
						p = s.pop()
						post += p
					if s:
						s.pop()
				elif i in op:
					if len(s) == 0:
						s.append(i)
					else:
						while s and s[-1] != '(' and (Prec[i] <= Prec[s[-1]]):
							p = s.pop()
							post += p
						s.append(i)
			while len(s) != 0:
				p = s.pop()
				post += p
			return post
		res1 = preToInfix(pre_exp)
		res2 = InfixtoPostfix(res1)
		return res2


class Solution:

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


class Solution:

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


class Solution:

	def preToPost(self, pre_exp):
		str = pre_exp[::-1]
		st = []
		for i in str:
			if i.isalnum():
				st.append(i)
			else:
				op1 = st.pop()
				op2 = st.pop()
				result = op1 + op2 + i
				st.append(result)
		return st[0]


class Solution:

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


class Solution:

	def preToPost(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 + operand2 + pre_exp[i]
				st.append(new_exp)
			else:
				st.append(pre_exp[i])
		return st.pop()


class Solution:

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


class Solution:

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


class Solution:

	def preToPost(self, pre_exp):
		st = []
		for i in pre_exp[::-1]:
			if i.isalpha():
				st.append(i)
			else:
				f = st.pop()
				s = st.pop()
				st.append(f + s + i)
		return st[0]


class Solution:

	def preToPost(self, pre_exp):
		ch_list = []
		for g in pre_exp[::-1]:
			if g == '+' or g == '-' or g == '*' or (g == '/') or (g == '^'):
				ele1 = ch_list.pop()
				ele2 = ch_list.pop()
				ch_list.append(ele1 + ele2 + g)
			else:
				ch_list.append(g)
		return ch_list[0]


class Solution:

	def preToPost(self, pre_exp):
		s = []
		operators = '+-*/'
		for i in pre_exp[::-1]:
			if i in operators:
				(op1, op2) = (s.pop(), s.pop())
				s.append(op1 + op2 + i)
			else:
				s.append(i)
		return s[-1]


class Solution:

	def infixToPostfix(self, s):

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

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

	def preToPost(self, pre_exp):
		return self.preToInfix(pre_exp)


class Solution:

	def preToPost(self, pre_exp):
		from collections import deque
		op = ['+', '-', '^', '*', '%', '/']
		res = deque()
		for i in range(1, len(pre_exp) + 1, 1):
			x = pre_exp[-i]
			if x not in op:
				res.append(x)
			else:
				a = res.pop()
				b = res.pop()
				exp = a + b + x
				res.append(exp)
		return ''.join(res)


class Solution:

	def preToPost(self, pre_exp):
		stack = []
		operators = ['+', '-', '*', '/', '^']
		str = ''
		for i in pre_exp[::-1]:
			if i not in operators:
				stack.append(i)
			elif len(stack) > 1:
				a = stack.pop()
				b = stack.pop()
				temp = a + b + i
				stack.append(temp)
		for i in stack:
			str = str + i
		return str


from collections import deque

class Solution:

	def preToPost(self, pre_exp):

		def isOperator(x):
			return x in '+-/*'
		stack = deque()
		length = len(prefix)
		for i in range(length - 1, -1, -1):
			if isOperator(prefix[i]):
				op1 = stack.pop()
				op2 = stack.pop()
				temp = op1 + op2 + prefix[i]
				stack.append(temp)
			else:
				stack.append(prefix[i])
		return stack.pop()