import sys
from collections import deque


# Utility function to return precedence of the given operator.
# Note that higher is the precedence, lower is its value
def prec(c):

	# Multiplication and division
	if c == '*' or c == '/':
		return 3

	# Addition and subtraction
	if c == '+' or c == '-':
		return 4

	# Bitwise AND
	if c == '&':
		return 8

	# Bitwise XOR (exclusive or)
	if c == '^':
		return 9

	# Bitwise OR (inclusive or)
	if c == '|':
		return 10

	# add more operators if needed
	return sys.maxsize		# for opening bracket '('


# Utility function to check if a given token is an operand
def isOperand(c):
	return ('a' <= c <= 'z') or ('A' <= c <= 'Z') or ('0' <= c <= '9')


# Function to convert an infix expression to a postfix expression.
# This function expects a valid infix expression
def infixToPostfix(infix):

	# base case
	if not infix or not len(infix):
		return True

	# create an empty stack for storing operators
	s = deque()

	# create a string to store the postfix expression
	postfix = ''

	# process the infix expression from left to right
	for c in infix:
		# Case 1. If the current token is an opening bracket '(', push it into
		# the stack
		if c == '(':
			s.append(c)

		# Case 2. If the current token is a closing bracket ')'
		elif c == ')':
			# pop tokens from the stack until the corresponding opening bracket '('
			# is removed. Append each operator at the end of the postfix expression
			while s[-1] != '(':
				postfix += s.pop()
			s.pop()

		# Case 3. If the current token is an operand, append it at the end of the
		# postfix expression
		elif isOperand(c):
			postfix += c

		# Case 4. If the current token is an operator
		else:
			# remove operators from the stack with higher or equal precedence
			# and append them at the end of the postfix expression
			while s and prec(c) >= prec(s[-1]):
				postfix += s.pop()

			# finally, push the current operator on top of the stack
			s.append(c)

	# append any remaining operators in the stack at the end of the postfix expression
	while s:
		postfix += s.pop()

	# return the postfix expression
	return postfix


if __name__ == '__main__':

	infix = 'A+B*C–D*E'
	postfix = infixToPostfix(infix)
	print(postfix)

class Conversion:

	# Constructor to initialize the class variables
	def __init__(self, capacity):
		self.top = -1
		self.capacity = capacity
		
		# This array is used a stack
		self.array = []
		
		# Precedence setting
		self.output = []
		self.precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}

	# Check if the stack is empty
	def isEmpty(self):
		return True if self.top == -1 else False

	# Return the value of the top of the stack
	def peek(self):
		return self.array[-1]

	# Pop the element from the stack
	def pop(self):
		if not self.isEmpty():
			self.top -= 1
			return self.array.pop()
		else:
			return "$"

	# Push the element to the stack
	def push(self, op):
		self.top += 1
		self.array.append(op)

	# A utility function to check is the given character
	# is operand
	def isOperand(self, ch):
		return ch.isalpha()

	# Check if the precedence of operator is strictly
	# less than top of stack or not
	def notGreater(self, i):
		try:
			a = self.precedence[i]
			b = self.precedence[self.peek()]
			return True if a <= b else False
		except KeyError:
			return False

	# The main function that
	# converts given infix expression
	# to postfix expression
	def infixToPostfix(self, exp):

		# Iterate over the expression for conversion
		for i in exp:
			
			# If the character is an operand,
			# add it to output
			if self.isOperand(i):
				self.output.append(i)

			# If the character is an '(', push it to stack
			elif i == '(':
				self.push(i)

			# If the scanned character is an ')', pop and
			# output from the stack until and '(' is found
			elif i == ')':
				while((not self.isEmpty()) and
					self.peek() != '('):
					a = self.pop()
					self.output.append(a)
				if (not self.isEmpty() and self.peek() != '('):
					return -1
				else:
					self.pop()

			# An operator is encountered
			else:
				while(not self.isEmpty() and self.notGreater(i)):
					self.output.append(self.pop())
				self.push(i)

		# Pop all the operator from the stack
		while not self.isEmpty():
			self.output.append(self.pop())

		for ch in self.output:
			print(ch, end="")


# Driver code
if __name__ == '__main__':
	exp = "a+b*(c^d-e)^(f+g*h)-i"
	obj = Conversion(len(exp))

	# Function call
	obj.infixToPostfix(exp)