#Use stack, Time O(n), Space O(m), n is expression length, m is operator number in expression
def preToPostStack(exp) :
    s = []
    length = len(exp)
    for  i in range(length-1, -1, -1) :
        if isOp(exp[i])==False :
            s.append(exp[i])        
        else :	
            op1 = s.pop()
            op2 = s.pop()
            temp = op1 + op2 + exp[i]
            s.append(temp)
    return s[len(s) - 1]

#Use recursion, Time O(n), Space O(n+m), n is expression length, m is operator number 
def preToPostRec(exp) : 
    op = exp.pop(0);    
    op1 = preToPostRec(exp) if  isOp(exp[0][0]) else exp.pop(0)
    op2 = preToPostRec(exp) if  isOp(exp[0][0]) else exp.pop(0)
    res = []
    res.append(op1)
    res.append(op2)
    res.append(op)
    return res

#Check whether the char is operator, Time O(1), Space O(1)
def isOp(op): 
    if op == '+' or op == '-' or op == '*' or op  == '/' :
        return True
    else :
        return False

#convert list to string, Time O(n), Space O(n), n is list length
def convert(res):
    r = ""
    for i in res:
        if isinstance(i, list):
            r += convert(i)
        else:
            r += i
    return r


s = "+*AB/CD"; #A*B + C/D
print("postfix(stack): " + preToPostStack(s))
res = preToPostRec(list(s))
r = convert(res)
print("postfix(rec): " + r)