Enter a calculation in prefix notation
- x / 15 - 7 + 1 1 3 + 2 + 1 1

Maximum depth:  6
Number of nodes:  15
Maximum value:  15

Result =  5

Prefix notation with brackets: 
(- (x (/ 15 (- 7 (+ 1 1))) 3) (+ 2 (+ 1 1)))

Infix notation with all brackets: 
(((15 / (7 - (1 + 1))) x 3) - (2 + (1 + 1)))
Infix notation with only necessary brackets: 
15 / (7 - (1 + 1)) x 3 - (2 + 1 + 1)

Diagram:
+-(-)
   +-(x)
   |  +-(/)
   |  |  +- 15
   |  |  +-(-)
   |  |     +- 7
   |  |     +-(+)
   |  |        +- 1
   |  |        +- 1
   |  +- 3
   +-(+)
      +- 2
      +-(+)
         +- 1
         +- 1


Order of operations:
   15 / (7 - (1 + 1)) x 3 - (2 + 1 + 1)
 = 15 / (7 - 2) x 3 - (2 + 1 + 1)
 = 15 / 5 x 3 - (2 + 1 + 1)
 = 3 x 3 - (2 + 1 + 1)
 = 9 - (2 + 1 + 1)
 = 9 - (2 + 2)
 = 9 - 4
 = 5

#!/usr/bin/python

from decimal import Decimal,getcontext

getcontext().prec = 5

#Classe utilisée pour stocker les noeuds de l'arbre
class Node:
    maxValue = 0
    maxDepth = 0
    nodeNumber = 0
    def __init__(self,data,par):
        self.data = data
        self.par = par
        self.right = None
        self.left = None
        if data:
            Node.nodeNumber += 1
        self.isnb = str(data).isdigit()
        if data and self.isnb and self.data > Node.maxValue:
            Node.maxValue = self.data

#Fonction (récursive) pour créer l'arbre
#Paramètres : objet Node, int (parcours de chaine), int (calcul de la profondeur max)
#Renvoie : tuple(Node,int) avec le noeud traité et l'index en cours
def makeTree(n, ind, depth):
    if depth > Node.maxDepth:
        Node.maxDepth = depth
    if ind < len(datas) and not datas[ind].isdigit() and not n.left:
        n.left,ind = makeTree(Node(datas[ind],n),ind + 1,depth + 1)
    if ind < len(datas) and datas[ind].isdigit() and not n.left:
        n.left = Node(int(datas[ind]),n)
        ind += 1
    if ind < len(datas) and datas[ind].isdigit() and not n.right:
        n.right = Node(int(datas[ind]),n)
        ind += 1
    if ind < len(datas) and not datas[ind].isdigit() and not n.right:
        n.right,ind = makeTree(Node(datas[ind],n),ind + 1,depth + 1)
    return n,ind


#Fonction (récursive) pour afficher l'expression préfixe avec parenthèses
#Paramètre : Node (noeud parent pour commencer)
def printBrackets(n):
    if not n.isnb:
        print((not n.par and "(" or " (") + n.data, end = "")
        printBrackets(n.left)
        printBrackets(n.right)
        print(")",end = "")
    else:
        print(" " + str(n.data),end = "")

#Fonction pour juger du besoin des parenthèses 
#Paramètre : Node (noeud à évaluer)
def needBrackets(n):
    if not n.par:
        return False
    if n.data == "-" and not n.right.isnb:
        return True
    if n.par.data in "x/" and n.data in "+-":
        return True
    if n.par.right == n:
        if n.par.data == "/" or (n.par.data == "-" and n.data == "+"):
            return True
    return False

#Fonction (récursive) pour écrire les 2 expressions préfixes
#Paramètres : Node (noeud parent pour commencer), bool (True pour toutes les parenthèses)
def printInfix(n,b):
    if not n.isnb:
        if b or (n.par and needBrackets(n)):
            print("(",end="")
        printInfix(n.left,b)
        print(" ",end="")
    print((n.isnb and n.data < 0 and n.par) and "("+n.data+")" or n.data,end="")
    if not n.isnb:
        print(" ",end="")
        printInfix(n.right,b)
        if b or (n.par and needBrackets(n)):
            print(")",end="")

#Fonction qui renvoie le résultat d'un calcul
#Paramètres : int/float (1er nombre), int/float (deuxième nombre), str (opérateur)
#Renvoie : int avec le résultat de l'opération
def calc(a,b,s):
    if s == "+":
        return a+b
    elif s == "-":
        return a-b
    elif s in "x":
        return a*b
    elif s == "/":
        return Decimal(a)/Decimal(b)

#Fonction (récursive) qui calcul le résultat total
#Paramètre : Node (noeud parent pour commencer)
#Renvoie : int (valeur du noeud en cours)
def calcResult(n):
    if not n.left.isnb and not n.right.isnb:
        return calc(calcResult(n.left),calcResult(n.right),n.data)
    elif not n.left.isnb and n.right.isnb:
        return calc(calcResult(n.left),n.right.data,n.data)
    elif n.left.isnb and not n.right.isnb:
        return calc(n.left.data,calcResult(n.right),n.data)
    else:
        return calc(n.left.data,n.right.data,n.data)

#Fonction (récursive) pour dessiner le schéma de l'arbre
#Paramètres : Node (noeud parent pour commencer), int (nombre d'espaces)
#tableau de bool (évalue le besoin de séparateur)
def printDiag(n,space,sep):
    for i in range(space):
        print(sep[i] and "|  " or "   ",end="")
    if not n.isnb:
        print("+-("+n.data +")")
        space += 1
        if not n.left.isnb:
            sep[space] = True
        printDiag(n.left,space,sep)
        if not n.left.isnb:
            sep[space] = False
        printDiag(n.right,space,sep)
        space -= 1
    else:
        print("+- "+str(n.data))

#Fonction qui écrit le déroulement des opérations en utilisant calcLast en boucle
#Paramètre : Node (noeud parent pour commencer)
def printOrderOfOps(n):
    b = True
    while True:
        print(b and "   " or " = ", end = "")
        printInfix(n,False)
        print()
        if n.isnb:
            break
        n,tmp = calcLast(n,False)
        b = False

#Fonction (récursive) qui calcul le résultat du noeud le plus profond
#Paramètres : Node (noeud parent pour commencer), bool(noeud calculé ou pas à ce tour de boucle)
#Renvoie : tuple(Node,bool) avec le noeud en cours et le booléen cité ci-dessus
def calcLast(n,b):
    if n.left.isnb and n.right.isnb and not b:
        n.data = calc(n.left.data,n.right.data,n.data)
        n.isnb,b = True,True
    elif n.left.isnb and not n.right.isnb:
        n.right,b = calcLast(n.right,b)
    elif not n.left.isnb and n.right.isnb:
        n.left,b = calcLast(n.left,b)
    elif not n.left.isnb and not n.right.isnb:
        n.left,b = calcLast(n.left,b)
        n.right,b = calcLast(n.right,b)
    return n,b

#Fonction qui appelle toutes les fonctions ci-dessus et met le résultat en forme
#Paramètre : Node (noeud parent)
def printResults(n):
    print("\nMaximum depth: ", Node.maxDepth)
    print("Number of nodes: ", Node.nodeNumber)
    print("Maximum value: ", Node.maxValue)
    print("\nResult = ", calcResult(root), end = "\n\n")
    print("Prefix notation with brackets: ")
    printBrackets(root)
    print("\n\nInfix notation with all brackets: ")
    printInfix(root,True)
    print("\nInfix notation with only necessary brackets: ")
    printInfix(root,False)
    sep = [False]*Node.maxDepth
    print("\n\nDiagram:")
    printDiag(root,0,sep)
    print("\n\nOrder of operations:")
    printOrderOfOps(root)

datas = input("\nEnter a calculation in prefix notation\n").rsplit()
root,tmp = makeTree(Node(None,None),0,1)
root,root.par = root.left,None
printResults(root)

from operator import add,sub,truediv as div,mul
class Lexerror(Exception): pass
class Parserror(Exception): pass

def lex(ch):
        lexemes,nb=[],None
        for c in ch:
            if c in "+-/*":                
                lexemes.append(c)            
            elif "0"<= c <="9":
                nb = nb + c if nb else c
            elif c!=" ":
                raise Lexerror
            elif nb: 
                    lexemes.append(int(nb))
                    nb=None            
        if nb: lexemes.append(int(nb))
        return lexemes

def parse(lexemes):
        try:
            unite = lexemes[0]
            del lexemes[0]
        except: raise Parserror    
        if isinstance(unite,str):
            return ("Node",unite,parse(lexemes),parse(lexemes))
        else:
            return ("Leaf",unite)

def foldabr(f): #Attend une fonction rendant deux fonctions pour
    fLeaf,fNode = f() #traiter chacun des cas d'arbres possibles
    def aux(abr):
        if abr[0]=="Leaf":
            return fLeaf(abr[1])
        op,opa1,opa2 = abr[1],aux(abr[2]),aux(abr[3])        
        return fNode(op,opa1,opa2)
    return aux

@foldabr
def evalabr():
    return (lambda v : v), (lambda op,opa1,opa2 : \
        {"+" : add, "-" : sub, "*": mul, "/": div}[op] (opa1,opa2))

@foldabr
def nodes(): #Or leaves...
    return (lambda _ : 1),(lambda op,opa1,opa2: 1+opa1+opa2)

@foldabr
def depth():
    return (lambda _ : 1),(lambda op,opa1,opa2: 1+max(opa1,opa2))

@foldabr
def maxval():
    return (lambda v : v),(lambda op,opa1,opa2: max(opa1,opa2))

@foldabr
def NPbckt():
    return (lambda v : str(v)),(lambda op,opa1,opa2: \
        "("+op+" "+opa1+" "+opa2+")")

@foldabr
def Infixbckt():
    return (lambda v : str(v)),(lambda op,opa1,opa2: \
        "("+opa1+" "+op+" "+opa2+")")

@foldabr
def Infix_():
    def fNode(op,(opa1,p1),(opa2,p2)):
        pop, r = {"+":0,"-":1,"*":2,"/":3}[op], ""
        r+= "("+opa1+")" if pop>1 and p1<2 else opa1        
        r+= " "+op+" "
        r+= "("+opa2+")" if pop>0 and p2<2 or op=="/" and p2<4 else opa2
        return (r,pop)    
    return (lambda v :(str(v),4)),fNode

def Infix(abr): return Infix_(abr)[0]

@foldabr
def diagram():
    def linesadd(add,s): #Surrindente un diagramme s selon une châine add à ajouter
       ligne= s.split("\n")
       return ligne[0]+  ("\n" + "\n".join(map(lambda ch : add+ch[1:],ligne[1:]))\
            if ligne[1:] else "") 
    return (lambda v: "+- "+str(v)),(lambda op,opa1,opa2: \
        "+-("+op+")\n   "+linesadd("   |",opa1)+"\n   "+linesadd("    ",opa2))

def steps(abr):
    def step(abr):        
        if abr[2][0]=="Leaf" and abr[3][0]=="Leaf":
            return ("Leaf",evalabr(abr))
        elif abr[2][0]=="Leaf":
           return ("Node",abr[1],abr[2],step(abr[3])) 
        return ("Node",abr[1],step(abr[2]),abr[3])    
    while abr[0]=="Node":
        print " =",Infix(abr)
        abr=step(abr)
    print " =",Infix(abr)
    
def demo():
    abr = parse(lex(raw_input("Enter a calculation in prefix notation\n")))
    print """\nMaximum depth: %d
Number of nodes: %d
Maximum value: %d

Result = %.2f

Prefix notation with brackets:
%s

Infix notation with all brackets:
%s
Infix notation with only necessary brackets:
%s


Diagram:
%s

Order of operations:
    """ % (depth(abr),nodes(abr),maxval(abr),evalabr(abr),\
           NPbckt(abr),Infixbckt(abr),Infix(abr),diagram(abr))
    steps(abr)

demo()

from operator import add, truediv as div, mul, sub
from decimal import Decimal as D, InvalidOperation

class InputError(Exception): pass

def is_operator(elem):
    return elem in ('*','+','/','-')

def lexer(expression):
    '''Prends en arguments l'entree de l'utilisateur
        Retourne un liste d'opérandes et d'opérateurs '''
    list_ops = [i for i in expression.split(' ') if i]
    for ind, elem in enumerate(list_ops):
        try :
            list_ops[ind]=D(elem)
        except InvalidOperation :
            if not is_operator(elem) :
                raise InputError("Symbole "+ str(elem)+" non supporté")
    return list_ops

def calculate (operateur, operande1, operande2):
    if operateur == '*' : return mul(operande1,operande2)
    if operateur == '+' : return add(operande1,operande2)
    if operateur == '-' : return sub(operande2,operande1)
    if operateur == '/' : return div(operande2,operande1)
    
def process (list_ops):
    ''' Prends la liste des opérateurs et opérandes en arguments,
        retourne le resultat du calcul '''
    pile_op= []
    
    for elem in reversed(list_ops):
        if isinstance(elem,D):
            pile_op.append(elem)
        elif len(pile_op) < 2:
            raise InputError("Expression mal formée")
        else:
            res = calculate(elem, pile_op.pop(), pile_op.pop())
            pile_op.append(res)

    if len(pile_op)==1:
        return pile_op.pop()
    else :
        raise InputError("Pas assez d'opérateurs")

def main():
    print("Calculatrice à notation préfixée")
    while True:
        user_input = input("Saisissez une expression à calculer ('q' pour quitter) : \n")
        if user_input == 'q':
            break
        else :
            try :
                print ( process( lexer(user_input) ) )
            except InputError as I:
                print(I)
    print("Au revoir")

if __name__ == "__main__":
    main()