Arvutiteaduse instituut
  1. Esileht
  2. Automaadid, keeled ja translaatorid
EN
Logi sisse

Automaadid, keeled ja translaatorid

  • Üldinfo
  • Ajakava
  • Eksami näidised
  • Teemad
    • 1. Soojendus
      • Kordamisülesanded
      • Kahendpuu
      • Kordamine*
      • Kodutöö
    • 2. Regulaaravaldised
    • 3. Automaadid
    • 4. Avaldise struktuur
    • 5. Grammatikad ja lekser
    • 6. Käsitsi parsimine
    • 7. ANTLRiga töötamine
    • 8. Interpretaator
    • 9. Kompilaator
    • 10. Edasi!
  • Süvendus
  • Bitbucket
  • Moodle
  • Zulip
  • Zoom

Harjutus: Kahendpuu

Kirjuta lõpuni järgnevad klassid

Oma lahenduse kontrollimiseks kasuta repos olevaid teste.

Node

package week1.soojendus;

/**
 * Klass on mõeldud kahendpuu tipu esitamiseks. Tüübiparameeter T määrab, millist 
 * tüüpi väärtust saab tipus hoida. Väärtuse küsimiseks on meetod getValue.
 */
public class Node<T> {
	public Node(T value, Node<T> leftChild, Node<T> rightChild) {
		// TODO: täienda konstruktorit
		// Mida võiks siin teha? Kas midagi on äkki kuskil puudu?
	}

	public T getValue() {
		// TODO: kirjuta erindi viskamise asemele enda kood
		throw new UnsupportedOperationException();
	}

	/**
	 * Tagastab vasaku alampuu. Selle puudumisel tagastab null-i.
	 */
	public Node<T> getLeftChild() {
		// TODO: kirjuta erindi viskamise asemele enda kood
		throw new UnsupportedOperationException();
	}

	public Node<T> getRightChild() {
		// TODO: kirjuta erindi viskamise asemele enda kood
		throw new UnsupportedOperationException();
	};

	/**
	 * Tagastab true tippude korral, millel pole ühtegi alampuud.
	 */
	public boolean isLeaf() {
		// TODO: kirjuta erindi viskamise asemele enda kood
		throw new UnsupportedOperationException();
	}


	/**
	 * Meetod peab tagastama true või false vastavalt sellele, kas antud (alam)puus
	 * leidub näidatud väärtus. Võrdlemine toimub meetodi equals alusel.
	 */
	public boolean contains(T value) {
		// TODO: kirjuta erindi viskamise asemele enda kood
		throw new UnsupportedOperationException();
	}

	/** 
	 * toString peab tagastama puu suluesituse.
	 * 
	 * Formaat:
	 * Puu iga tipp on esitatud ümarsulgudes antud kolmikuna, kus esimene
	 * element on tipu väärtus, teine element on vasak alluv ning kolmas on parem alluv.
	 * Kui alluv puudub, siis on sõnes vastaval kohal allkriips.
	 * 
	 * Komponentide vahel peab olema koma ja üks tühik.
	 * 
	 * Näited:
	 * kui t on ühetipuline puu tüübiga Node<Integer>, 
	 * mille tipu väärtus on 3, siis t.toString() peab tagastama
	 * "(3, _, _)"
	 *  
	 *  
	 * Kui t on selline puu:
	 *  	1
	 *     / \
	 *    /   \
	 *   2    -44
	 *    \
	 *     3
	 *  
	 * siis t.toString() peab tagastama
	 * 
	 * "(1, (2, _, (3, _, _)), (-44, _, _))"
	 */
	@Override
	public String toString() {
		// TODO: kirjuta super.toString asemele enda kood
		return super.toString();
	}
}

NodeUtils

package week1.soojendus;

public class NodeUtils {

	/**
	 * Meetod peab tagastama täisarvu, mis näitab mitu korda esineb antud (alam)puus
	 * näidatud väärtus. NB! Võrdlemiseks kasutada meetodit equals!
	 */
	public static <T> int count(Node<T> tree, T value) {
		// TODO: kirjuta erindi viskamise asemele enda kood
		throw new UnsupportedOperationException();
	}


	/**
	 * NB! See on raskem ülesanne. Enne selle üritamist lahenda ja esita teised ülesanded ära!
	 * 
	 * 
	 * See meetod peab võtma suluesituses sõnena antud puu ja tagastama vastava
	 * puu andmestruktuuri. Tippudes oleva väärtuse tüüp on Integer.
	 * 
	 * Sõne formaat on sama, nagu kirjeldatud Node.toString juures.
	 * 
	 * Näited
	 * 
	 * Kui käivitada
	 * 
	 * 		puu = parseIntegerTree("(1, (2, _, (3, _, _)), (3, _, _))");
	 * 
	 * siis puu.getLeft().getRight().getValue() peab tagastama 3
	 * ja   puu.getRight().isLeaf() peab tagastama true
	 * ja   NodeUtils.count(puu, 3) peab tagastama 2
	 * 
	 */
	public static Node<Integer> parseIntegerTree(String s) {
		// TODO: kirjuta erindi viskamise asemele enda kood
		throw new UnsupportedOperationException();
	}
}
  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo