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

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def postToPre(self, post_exp):

        # Code here

Solutions:
class Solution:

	def postToPre(self, post_exp):
		st = []
		opr = {'^', '*', '/', '+', '-'}
		for ch in post_exp:
			if ch not in opr:
				st.append(ch)
			elif len(st) >= 2:
				a = st.pop()
				b = st.pop()
				st.append(ch + b + a)
		return st[0]


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution(object):

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

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

	def postToPre(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 = char + operand2 + operand1
				self.stack.append(exp)
		return self.stack.pop()


class Solution:

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


class Solution:

	def postToPre(self, post_exp):
		stack = []
		for char in post_exp:
			if char.isalnum():
				stack.append(char)
			else:
				operand1 = ''
				operand2 = ''
				if len(stack) > 0:
					operand2 = stack.pop()
				if len(stack) > 0:
					operand1 = stack.pop()
				new_string = char + operand1 + operand2
				stack.append(new_string)
		return stack[-1]


class Solution:

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


class Solution:

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


class Solution:

	def postToPre(self, post_exp):

		def isOperator(x):
			if x == '+':
				return True
			if x == '-':
				return True
			if x == '/':
				return True
			if x == '*':
				return True
			return False
		s = []
		length = len(post_exp)
		for i in range(length):
			if isOperator(post_exp[i]):
				op1 = s[-1]
				s.pop()
				op2 = s[-1]
				s.pop()
				temp = post_exp[i] + op2 + op1
				s.append(temp)
			else:
				s.append(post_exp[i])
		ans = ''
		for i in s:
			ans += i
		return ans


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def postToPre(self, post_exp):
		stack = []
		op = '^*/+-'
		for i in post_exp:
			if i not in op:
				stack.append(i)
			if i in op:
				a = ''
				b = ''
				if len(stack) != 0:
					a = stack.pop()
				if len(stack) != 0:
					b = stack.pop()
				exp = i + b + a
				stack.append(exp)
		return stack[0]


class Solution:

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


class Solution:

	def postToPre(self, post):
		stack = []
		ops = {'+', '*', '-', '/'}
		for i in post:
			if i in ops:
				a = stack.pop()
				b = stack.pop()
				stack.append(i + b + a)
			else:
				stack.append(i)
		stack = stack[0]
		return stack


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

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


class Solution:

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


import sys
sys.setrecursionlimit(10 ** 9)

class Node:

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

def letter(c):
	capital = ord('A') <= ord(c) <= ord('Z')
	small = ord('a') <= ord(c) <= ord('z')
	return capital or small

def preorder(root):
	if root == None:
		return ''
	return root.data + preorder(root.left) + preorder(root.right)

class Solution:

	def postToPre(self, post_exp):
		root = Node(post_exp[-1])
		stack = [root]
		if len(post_exp) == 1:
			return post_exp
		for i in range(len(post_exp) - 2, -1, -1):
			new_node = Node(post_exp[i])
			while True:
				if not stack[-1].right:
					stack[-1].right = new_node
					break
				elif not stack[-1].left:
					stack[-1].left = new_node
					break
				else:
					stack.pop()
			if not letter(post_exp[i]):
				stack.append(new_node)
		return preorder(root)


class Solution:

	def postToPre(self, post_exp):
		l = ['+', '-', '*', '/', '^']
		s = []
		for i in range(len(post_exp)):
			if post_exp[i] in l:
				a = s[-1]
				s.pop()
				b = s[-1]
				s.pop()
				t = post_exp[i] + b + a
				s.append(t)
			else:
				s.append(post_exp[i])
		return ''.join((i for i in s))


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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def postToPre(self, post_exp):
		stack = []
		for i in post_exp:
			if i.isalpha():
				stack.append(i)
				continue
			else:
				exp = i
				two = stack.pop()
				one = stack.pop()
				new = exp + one + two
				stack.append(new)
		return stack[0]


class Solution:

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


class Solution:

	def postToPre(self, post_exp):
		stack = []
		prefix = ''
		operators = set(['+', '-', '*', '/', '^'])
		for i in post_exp:
			if i in operators:
				op2 = stack.pop()
				op1 = stack.pop()
				prefix = i + op1 + op2
				stack.append(prefix)
			else:
				stack.append(i)
		return stack.pop()


class Solution:

	def postToPre(self, post_exp):
		stack = []
		prefix = ''
		operators = set(['+', '-', '*', '/'])
		for i in post_exp:
			if i in operators:
				operand2 = stack.pop()
				operand1 = stack.pop()
				prefix = i + operand1 + operand2
				stack.append(prefix)
			else:
				stack.append(i)
		return stack.pop()


class Solution:

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


class Solution:

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


class Solution:

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

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

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

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


class Solution:

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


class Solution:

	def postToPre(self, post_exp):
		stack = []
		OPS = '*/-+'
		for c in post_exp:
			if c in OPS:
				right = stack.pop()
				left = stack.pop()
				result = [c] + left + right
			else:
				result = [c]
			stack.append(result)
		return ''.join(stack[0])


class Solution:

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


class Solution:

	def postToPre(self, post_exp):

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

		def InfixtoPrefix(exp):
			pre = ''
			s = []
			op = ('+', '-', '/', '*', '^')
			Prec = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
			exp = exp[::-1]
			for i in exp:
				if i.isalpha():
					pre += i
				elif i == ')':
					s.append(i)
				elif i == '(':
					while len(s) != 0 and s[-1] != ')':
						p = s.pop()
						pre += 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()
							pre += p
						s.append(i)
			while len(s) != 0:
				p = s.pop()
				pre += p
			pre = pre[::-1]
			return pre
		res1 = postToInfix(post_exp)
		res2 = InfixtoPrefix(res1)
		return res2


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def postToPre(self, post_exp):
		stack = []
		str = ''
		for i in post_exp:
			if i.isalpha():
				stack.append(i)
			else:
				a = stack.pop()
				b = stack.pop()
				temp = i + b + a
				stack.append(temp)
		for i in stack:
			str = str + i
		return str


class Solution:

	def postToPre(self, post_exp):
		from queue import LifoQueue

		def processPre(st, op):
			op2 = st.get()
			op1 = st.get()
			st.put(op + op1 + op2)
		n = len(post_exp)
		inSt = LifoQueue(maxsize=n)
		preSt = LifoQueue(maxsize=n)
		valSt = LifoQueue(maxsize=n)
		for i in post_exp:
			if i == '+' or i == '-' or i == '*' or (i == '/'):
				processPre(preSt, i)
			else:
				preSt.put(i)
		return preSt.get()


from collections import deque

class Solution:

	def postToPre(self, post_exp):

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