Informatika2-2016/Gyakorlat12Megold
A MathWikiből
Tartalomjegyzék |
Feladatok
A feladatok megoldásához szükség lesz az előadáson használt kódra. Az előadás anyagát innen lehet letölteni.
Bevezető
Másoljuk be a bináris fa definícióját. Ezen az osztályon fogunk dolgozni.
- Írjunk egy count(self) metódust, ami megszámolja a fa elemeinek a számát!
- Írjunk egy sum(self) metódust, ami a fa összes csúcsában lévő értékeket összegzi!
- Írjunk egy height(self) metódust, ami megmondja, hogy milyen magas a fa!
- Írjunk egy is_list(self) metódust, ami megmondja, hogy a bináris fa listává fajult-e. Egy bináris fa akkor fajult listává, ha minden csúcsának legfeljebb egy gyereke van.
class Node(object): def __init__(self, data): self.data = data self.left = None self.right = None def insert(self, data): if self.data > data: if self.left is None: self.left = Node(data) else: self.left.insert(data) else: if self.right is None: self.right = Node(data) else: self.right.insert(data) def count(self): s = 1 if self.left is not None: s += self.left.count() if self.right is not None: s += self.right.count() return s def sum(self): s = self.data if self.left is not None: s += self.left.sum() if self.right is not None: s += self.right.sum() return s def height(self): l = 1 r = 1 if self.left is not None: l += self.left.height() if self.right is not None: r += self.right.height() if l > r: return l else: return r def is_list(self): if self.left is not None and self.right is not None: return False if self.left is not None: return self.left.is_list() if self.right is not None: return self.right.is_list() return True
Számológép
Az előadáson mutatott számológép-kezdeményt feljesztjük tovább. Kezdjük új fájlba. Először hozzunk létre egy üres Node osztályt!
- Írjuk meg a konstruktort a következőképp. A bemenet egy sztring, ezt kell értelmeznünk. Egyelőre a bemeneti sztring nem tartalmazhat zárójelet, sem negatív számokat.
- Ha a sztring egy szám, akkor egyszerűen eltároljuk a self.data változóban mint számot.
- Ha nem szám (azaz a négy alapművelet egyike szerepel a sztringben), akkor szétvágjuk a sztringet két részre a legalacsonyabb precedenciaszintű művelet mentén. Mivel zárójeleket nem engedünk meg, a legalacsonyabb szintű művelet az első + vagy - jel, ha nincs ilyen, akkor pedig az első * vagy /. A self.data értéke a műveleti jel lesz mint karakter, a bal, illetve a jobb gyereke pedig a sztring két széthasított része alapján épüljön fel!
- Számoljuk ki egy ilyen műveletsor értékét!
class Node(object): def __init__(self, kappa): i = -1 if kappa.find("+") != -1: i = kappa.find("+") elif kappa.find("-") != -1: i = kappa.find("-") elif kappa.find("*") != -1: i = kappa.find("*") elif kappa.find("/") != -1: i = kappa.find("/") if i != -1: self.data = kappa[i] self.left = Node(kappa[:i]) self.right = Node(kappa[i + 1:]) else: self.data = float(kappa) self.left = None self.right = None def calculate(self): if self.data == "+": return self.left.calculate() + self.right.calculate() elif self.data == "-": return self.left.calculate() - self.right.calculate() elif self.data == "*": return self.left.calculate() * self.right.calculate() elif self.data == "/": return self.left.calculate() / self.right.calculate() else: return self.data
Egy kis állapotgép
- Adott egy sztring. Cseréljük le azokat a karaktereket $ jelre, amelyek zárójelek között vannak (a zárójeleket is beleértve)! Figyelem, a zárójelek lehetnek egymásba ágyazva is, tehát, ha a bemeneti sztring (xc)aa(c(b)), akkor a kimenet $$$$aa$$$$$$ legyen!
def zarojel_csere(kappa): s = "" level = 0 for c in kappa: if c == "(": level += 1 if level > 0: s += "$" else: s += c if c == ")": level -= 1 return s