Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 2.11.2020 (L) Vykreslete si svůj první matematický výraz přes MathJax!
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 29. 04. 2021 14:05

auditor
Příspěvky: 139
Reputace:   
 

Infixová notace s minimálními závorkami

Ahoj,

rád bych věděl, jak je možno vytisknout výraz (bez vyhodnocení) v infixové notaci z binárního stromu výrazů s minimálními závorkami. Mám vstup v postfixové notaci, který jsem vložil do binárního stromu. Při průchodu stromem inorder s rekurzí umím získat infovou notaci buď bez závorek anebo s úplnými závorkami. Chybí mně implementace minimálních závorek. Vím, že potřebuji sledovat prioritu předchozího operátoru  s tím, že napravo mě zajímá i rovnost priorit, zatímco nalevo pouze menší priorita. Program mám v pythonu. Minimální závorky zvládnu v seznamu, ale ne na stromu. Děkuji za pomoc.

Offline

  • (téma jako vyřešené označil(a) auditor)

#2 29. 04. 2021 16:01

Stýv
Vrchní cenzor
Příspěvky: 5575
Reputace:   213 
Web
 

Re: Infixová notace s minimálními závorkami

auditor napsal(a):

Vím, že potřebuji sledovat prioritu předchozího operátoru  s tím, že napravo mě zajímá i rovnost priorit, zatímco nalevo pouze menší priorita.

Prijde mi, ze reseni znas; v cem je tedy problem?

Offline

 

#3 29. 04. 2021 18:11

auditor
Příspěvky: 139
Reputace:   
 

Re: Infixová notace s minimálními závorkami

↑ Stýv:

Problém je v implementaci. Mám funkci strom, která postaví strom aritmetického výrazu. Pak mám funkci infix, která tiskne výraz pomocí rekurze.

Nevím, jak mám udržovat předchůdce mezi funkcemi. Momentálně se mně nedaří odlišit předchůdce od aktuálního operátoru. Předchůdce mám odkazem z aktuálního operátoru.

Dále nevím, jestli mám umístit podmínky na prioritu operátorů ve funkci infix před příkazy vložení pravé a levé závorky nebo v jiném místě.

Offline

 

#4 01. 05. 2021 10:29

Stýv
Vrchní cenzor
Příspěvky: 5575
Reputace:   213 
Web
 

Re: Infixová notace s minimálními závorkami

Tomu popisu moc nerozumim, muzes sem dat nejakej kod, treba s plnym uzavorkovanim?

Offline

 

#5 01. 05. 2021 18:36

auditor
Příspěvky: 139
Reputace:   
 

Re: Infixová notace s minimálními závorkami

↑ Stýv:

class Vrchol:
       
    def __init__(self , hodnota):
        self.hodnota = hodnota
        self.levy = None
        self.pravy = None

def strom(p):
    zasobnik = []
    for i in range(len(p)):
        if not operator(p[i]):
            t = Vrchol(p[i])
            zasobnik.append(t)
        else:
            t = Vrchol(p[i])
            t1 = zasobnik.pop()
            t2 = zasobnik.pop()
            t.pravy = t1
            t.levy = t2
            zasobnik.append(t)
    t = zasobnik.pop()
    return t

def infix(t):
    if t != None:
        if t.levy == None and t.pravy == None:
            print(t.hodnota, end='')
        else:
                print('(', end='')
                infix(t.levy)
                print(t.hodnota, end='')
                infix(t.pravy)
                print(')', end='')

def operator(c):
    if (c == '+' or c == '-' or c == '*' or c == '/'):
        return True
    else:
        return False

def priorita(g):
    if (g == '+'or g == '-'):
        return 0
    else:
        return 1

p = []
p = input().split()
r = strom(p)
infix(r)

Offline

 

#6 02. 05. 2021 01:00

Stýv
Vrchní cenzor
Příspěvky: 5575
Reputace:   213 
Web
 

Re: Infixová notace s minimálními závorkami

Jo uz vidim, s cim mas problem. Ty delas zavorky kolem prave vyhodnocovaneho vyrazu, takze nepoznas, jestli jsou vlastne potreba. Kdyz misto toho budes delat zavorky kolem tech dvou synu, tak to pujde poznat snadno.

Offline

 

#7 02. 05. 2021 07:04

auditor
Příspěvky: 139
Reputace:   
 

Re: Infixová notace s minimálními závorkami

↑ Stýv:

Přiznám se, že nevím, jak to udělat. Vyzkoušel jsem několik variant funkce infix, ale žádná bohužel nevedla k cíli.

Příklad:

def infix(t):
    if t.levy != None:
        if (t.levy.levy == None and t.levy.pravy == None):
            print(t.levy.hodnota, end='')
        elif operator(t.hodnota) < operator(t.levy.hodnota):
            print('(', end='')
            infix(t.levy.levy)
            print(t.levy.hodnota, end='')
            infix(t.levy.pravy)
            print(')', end='')
        else:
            infix(t.levy.levy)
            print(t.levy.hodnota, end='')
            infix(t.levy.pravy)
    if t.pravy != None:
        if (t.pravy.levy == None and t.pravy.pravy == None):
            print(t.pravy.hodnota, end='')
        elif operator(t.hodnota) < operator(t.pravy.hodnota) or operator(t.hodnota) == operator(t.pravy.hodnota):
            print('(', end='')
            infix(t.pravy.levy)
            print(t.pravy.hodnota, end='')
            infix(t.pravy.pravy)
            print(')', end='')
        else:
            infix(t.pravy.levy)
            print(t.pravy.hodnota, end='')
            infix(t.pravy.pravy)

Offline

 

#8 02. 05. 2021 10:24

Stýv
Vrchní cenzor
Příspěvky: 5575
Reputace:   213 
Web
 

Re: Infixová notace s minimálními závorkami

Proc se zanorujes o dve patra niz? A kde pouzivas prioritu operatoru?

Offline

 

#9 02. 05. 2021 10:47 — Editoval auditor (02. 05. 2021 11:40)

auditor
Příspěvky: 139
Reputace:   
 

Re: Infixová notace s minimálními závorkami

Řídil jsem se doporučením, že mám dělat závorky kolem synů, což chápu jako závorky kolem t.levy.hodnota a t.pravy.hodnota. Prioritu operátorů řeším společně s předchozím bodem v částech elif.
Měl jsem za to, že jsem postoupil pouze o jedno patro níž z t na t.levy / t.pravy, což mně umožnilo rozlišit rozdílné priority operátorů pro levou a pravou stranu.

Offline

 

#10 02. 05. 2021 12:07

Stýv
Vrchní cenzor
Příspěvky: 5575
Reputace:   213 
Web
 

Re: Infixová notace s minimálními závorkami

Zavorky mas delat kolem infix(t.levy) a infix(t.pravy), tj. stacilo pridat dva radky, kdyz opomineme ty podminky. A pokud jde o ty podminky, tak si je po sobe precti. Funkci priorita jsi vubec nepouzil.

Offline

 

#11 02. 05. 2021 12:47

auditor
Příspěvky: 139
Reputace:   
 

Re: Infixová notace s minimálními závorkami

↑ Stýv:

Děkuji moc. Upravil jsem. Závorky jsem dal kolem infix(t.levy) a infix(t.pravy) a v podmínkách používám funkci priorita. Bohužel stále nefunguje.

def infix(t):
    if t != None:
        if t.levy == None and t.pravy == None:
            print(t.hodnota, end='')
        else:
            if priorita(t.hodnota) < priorita(t.levy.hodnota):
                print('(', end='')
                infix(t.levy)
                print(')', end='')
            else:
                infix(t.levy)

            print(t.hodnota, end='')
           
            if priorita(t.hodnota) < priorita(t.pravy.hodnota) or priorita(t.hodnota) == priorita(t.pravy.hodnota):
                print('(', end='')
                infix(t.pravy)
                print(')', end='')
            else:
                infix(t.pravy)

Offline

 

#12 02. 05. 2021 14:24

Stýv
Vrchní cenzor
Příspěvky: 5575
Reputace:   213 
Web
 

Re: Infixová notace s minimálními závorkami

Prijde mi, ze to porovnani mas obracene. Takovyhle veci by sis ale mel debugovat sam.

Offline

 

#13 02. 05. 2021 14:40

auditor
Příspěvky: 139
Reputace:   
 

Re: Infixová notace s minimálními závorkami

↑ Stýv:

Děkuji moc.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson