Keresés


Toplista

Toplista
  • betöltés...

Magántanár kereső

Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!

Algoritmusok, Infix, PostFix

242
Csatoltam képet.
Jelenleg 1 felhasználó nézi ezt a kérdést.
0
Felsőoktatás / Informatika

Válaszok

1
1. A leírónyelvvel hadilábon állok, ezért Python kóddal próbállak kisegíteni.
2. A mellékelt folyamatábra alapján nem lehet megoldani, ezért a https://hu.wikipedia.org/wiki/Shunting-yard_algoritmus használtam.
3. A feladat zagyválja a megnevezéseket, ugyanis a posztfix és a lengyel forma nem ugyanaz, ezért a példák alapján arra tippeltem, hogy posztfixet akarnak.
    infix: 3 + 4
    prefix == lengyel forma: + 3 4
    posztfix == fordított lengyel forma: 3 4 +



import re

class HaziFeladat:
    elsobbseg = {':=': 0, '+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    nemkommutativ = ['^']

    def __init__(self, infix):
        self.infix = infix

    def felbont(self):
        self.tagolt = re.findall(r'\d+(?:\.\d+)?|:=|[+\-*/^()|\w+]', self.infix)
        for nr, darab in enumerate(self.tagolt):
            try:
                self.tagolt[nr] = float(darab)
            except (ValueError, TypeError):
                pass

        return self.tagolt

    def atalakit(self):
        self.posztfix = []
        verem = []

        for elem in self.tagolt:
            if type(elem) is float or elem.isalpha():
                self.posztfix.append(elem)
            elif elem == '(':
                verem.append(elem)
            elif elem == ')':
                while verem and verem[-1] != '(':
                    self.posztfix.append(verem.pop())

                if verem and verem[-1] == '(':
                    verem.pop()
            else:
                while verem and verem[-1] != '(' and HaziFeladat.elsobbseg[verem[-1]] >= HaziFeladat.elsobbseg[elem] and not (verem[-1] == elem and elem in HaziFeladat.nemkommutativ):
                    self.posztfix.append(verem.pop())

                verem.append(elem)

        while verem:
            self.posztfix.append(verem.pop())

        return self.posztfix

    def kiertekel(self, valtozo = {}):
        verem = []
        eredmeny = None
       
        for elem in self.posztfix:
            if type(elem) is float:
                verem.append(elem)
            elif elem in valtozo:
                verem.append(valtozo[elem])
            elif elem.isalpha():
                verem.append(elem)
            elif elem == '+':
                verem.append(verem.pop() + verem.pop())
            elif elem == '-':
                top = verem.pop()
                verem.append(verem.pop() - top)
            elif elem == '*':
                verem.append(verem.pop() * verem.pop())
            elif elem == '/':
                top = verem.pop()
                verem.append(verem.pop() / top)
            elif elem == '^':
                top = verem.pop()
                verem.append(verem.pop() ** top)
            elif elem == ':=':
                top = verem.pop()
                eredmeny = valtozo[verem.pop()] = top
               
        return eredmeny if eredmeny != None else verem[-1] if verem else None



teszt_lista = [
    {
        'infix': '(56+47)*2',
        'posztfix': '56 47 + 2 *',
        'eredmeny': 206,
    },
    {
        'infix': 'm*n+(p-q)+r',
        'posztfix': 'm n * p q - + r +',
        'valtozo': {'m': 3, 'n': 4, 'p': 5, 'q': 6, 'r': 7},
        'eredmeny': 18,
    },
    {
        'infix': 'x:=((a+b-1)*c+5)+u/v*z^k^2+8',
        'posztfix': 'x a b + 1 - c * 5 + u v / z k 2 ^ ^ * + 8 + :=',
        'valtozo': {'a': 3, 'b': 4, 'c': 5, 'k': 1, 'u': 6, 'v': 7, 'z': 8},
        'eredmeny': 49.85714285714285714280,
    },
]
   
for teszt in teszt_lista:
    print('infix: ', teszt['infix'])
    hf = HaziFeladat(teszt['infix'])
    print('tagolt: ', hf.felbont())
    print('posztfix: ', hf.atalakit())
    if 'valtozo' in teszt:
        print('eredmeny: ', hf.kiertekel(teszt['valtozo']))
    else:
        print('eredmeny: ', hf.kiertekel())
Módosítva: 2 éve
1