Riešenia (skupina A, 4. týždeň)

import java.util.*;

public class Osoba {
        /**
         * Meno osoby
         */
        private String meno;
        /**
         * Zoznam deti osoby
         */
        private List<Osoba> deti = new ArrayList<Osoba>();

        /**
         * Konstruktor osoby v strome potomkov
         * @param meno meno osoby
         */
        public Osoba(String meno) {
                this.meno = meno;
        }

        /**
         * Prida osobe dieta
         * @param dieta referencia na pridavane dieta
         */
        public void pridajDieta(Osoba dieta) {
                deti.add(dieta);
        }

        /**
         * Vrati celkovy pocet potomkov osoby
         */
        public int pocetPotomkov() {
                int pocetPotomkovDeti = 0;
                for (Osoba dieta: deti)
                        pocetPotomkovDeti += dieta.pocetPotomkov();

                return pocetPotomkovDeti + deti.size();
        }

        /**
         * Vypise rodostrom osoby
         */
        public void vypisRodostrom() {
                System.out.println(meno);
                for (Osoba dieta: deti)
                        dieta.vypisRodostrom();
        }

        public void pridajDoZoznamu(List<Osoba> zoznam) {
                for (Osoba dieta: deti)
                        dieta.pridajDoZoznamu(zoznam);

                zoznam.add(this);
        }

        /**
         * Main s vytvorenim stromu potomkov pre Janka
         */
        public static void main(String[] args) {
                Osoba janko = new Osoba("Janko");
                Osoba jozko = new Osoba("Jozko");
                Osoba maria = new Osoba("Maria");
                Osoba karol = new Osoba("Karol");
                Osoba lucia = new Osoba("Lucia");
                Osoba petra = new Osoba("Petra");
                janko.pridajDieta(jozko);
                janko.pridajDieta(maria);
                janko.pridajDieta(karol);
                karol.pridajDieta(lucia);
                karol.pridajDieta(petra);
                janko.vypisRodostrom();
        }
}

/**
 * Trieda reprezentujuca uzol binarneho stromu
 */
public class Uzol {
        /**
         * Hodnota ulozena v uzle stromu
         */
        private int hodnota;

        /**
         * Referencia na laveho syna uzla (koren laveho podstromu)
         */
        private Uzol lavy;

        /**
         * Referencia na praveho syna uzla (koren praveho podstromu)
         */
        private Uzol pravy;

        /**
         * Konstruktor uzla binarneho stromu
         *
         * @param hodnota
         * @param lavy
         * @param pravy
         */
        public Uzol(int hodnota, Uzol lavy, Uzol pravy) {
                this.hodnota = hodnota;
                this.lavy = lavy;
                this.pravy = pravy;
        }

        /**
         * Vypise obsah uzlov stromu, ktoreho korenom je tento vrchol. Realizuje
         * preorder prechod.
         */
        public void vypis() {
                // Vypiseme hodnotu
                System.out.println(hodnota);

                // Ak je lavy syn, poziadame ho o vypis hodnot laveho podstromu
                if (lavy != null)
                        lavy.vypis();

                // Ak je pravy syn, poziadame ho o vypis hodnot praveho podstromu
                if (pravy != null)
                        pravy.vypis();
        }

        /**
         * Vrati maximum v strome, ktoreho je tento uzol korenom
         */
        public int maximum() {
                // Predpokladame, ze maximum je hodnota v tomto uzle
                int vysledok = hodnota;

                // Ak je lavy syn, vyberieme bud maximum z laveho podstromu
                // alebo hodnotu v tomto uzle - podla toho, co je vacsie
                if (lavy != null)
                        vysledok = Math.max(vysledok, lavy.maximum());

                // Ak je pravy syn, skusime, ci maximum v pravom podstrome nie je
                // vacsie
                if (pravy != null)
                        vysledok = Math.max(vysledok, pravy.maximum());

                return vysledok;
        }

        /**
         * Zisti, ci sa zadana hodnota nachadza v strome, ktoreho je tento uzol
         * korenom
         *
         * @param hladany
         *            hladana hodnota
         */
        public boolean obsahuje(int hladany) {
                // Ak je hladana hodnota v tomto uzle, koncime ihned
                if (hodnota == hladany)
                        return true;

                // Ak je lavy syn, skusime, ci hladana hodnota nie je v podstrome,
                // ktoreho je lavy syn korenom
                if (lavy != null)
                        if (lavy.obsahuje(hladany))
                                return true;

                // Ak je pravy syn, skusime, ci hladana hodnota nie je v podstrome,
                // ktoreho je pravy syn korenom
                if (pravy != null)
                        if (pravy.obsahuje(hladany))
                                return true;

                return false;
        }

        public int getHodnota() {
                return hodnota;
        }

        public void setHodnota(int hodnota) {
                this.hodnota = hodnota;
        }

        public int sucet() {
                int vysledok = hodnota;
                if (lavy != null) {
                        vysledok += lavy.sucet();
                }
                if (pravy != null) {
                        vysledok += pravy.sucet();
                }
                return vysledok;
        }

        public int vyska() {
                int vysledok = 0;
                if (lavy != null) {
                        vysledok = Math.max(vysledok, lavy.vyska() + 1);
                }
                if (pravy != null) {
                        vysledok = Math.max(vysledok, pravy.vyska() + 1);
                }

                return vysledok;
        }

        public static void main(String[] args) {
                Uzol koren = new Uzol(5, new Uzol(2, new Uzol(8, null, null), null),
                                new Uzol(9, null, null));
                koren.vypis();
                System.out.println("Maximum je " + koren.maximum());
        }
}

/**
 * Trieda reprezentujuca aritmeticky vyraz
 */
public class Vyraz {

        /**
         * Rozhranie, ktore implementuju vsetky uzly aritmetickeho stromu
         */
        private interface Clen {
                @Override
                public String toString();
                public String postfix();
        }

        /**
         * Trieda implementujuca uzol stromu aritmetickeho stromu, ktory
         * reprezentuje binarnu operaciu
         */
        private static class BinarnaOperacia implements Clen {
                private char operator;
                private Clen lavyPodvyraz;
                private Clen pravyPodvyraz;

                public BinarnaOperacia(char operator, Clen lavy, Clen pravy) {
                        this.operator = operator;
                        this.lavyPodvyraz = lavy;
                        this.pravyPodvyraz = pravy;
                }

                @Override
                public String toString() {
                        return "(" + lavyPodvyraz.toString() + operator
                                        + pravyPodvyraz.toString() + ")";
                }

                                @Override
                                public String postfix() {
                                    return lavyPodvyraz.postfix() + " " + pravyPodvyraz.postfix() + operator;
                                }
        }

        /**
         * Trieda implementujuca uzol aritmetickeho stromu, ktory reprezentuje
         * konstantu
         */
        private static class Hodnota implements Clen {
                private double hodnota;

                public Hodnota(double hodnota) {
                        this.hodnota = hodnota;
                }

                @Override
                public String toString() {
                        return Double.toString(hodnota);
                }

                                @Override
                                public String postfix() {
                                    return Double.toString(hodnota);
                                }
        }

        /**
         * Symboly operacii od najnizsej priority po najvyssiu
         */
        private static final String SYMBOLY_OPERACII = "+-*/";

        /**
         * Prevedie zadany vyraz do aritmetickeho stromu
         *
         * @param vyraz
         *            vyraz, ktory sa ma parsovat
         * @return referencia na koren aritmetickeho stromu
         */
        private static Clen prevedNaStrom(String vyraz) {
                // Odstranime zbytocne medzery
                vyraz = vyraz.trim();

                // Najdeme operator s najnizsou prioritou, ktory nie je v zatvorkach
                int operatorIdx = Integer.MAX_VALUE;
                int operatorPoz = -1;
                int pocitadloZatvoriek = 0;

                for (int i = 0; i < vyraz.length(); i++) {
                        char znak = vyraz.charAt(i);

                        if (znak == '(')
                                pocitadloZatvoriek++;

                        if (znak == ')')
                                pocitadloZatvoriek--;

                        int priorita = SYMBOLY_OPERACII.indexOf(znak);
                        if ((priorita != -1) && (pocitadloZatvoriek == 0) && (i > 0)) {
                                if (priorita < operatorIdx) {
                                        operatorIdx = priorita;
                                        operatorPoz = i;
                                }
                        }
                }

                // Rozdelime vyraz na podvyrazy
                if (operatorPoz != -1) {
                        return new BinarnaOperacia(SYMBOLY_OPERACII.charAt(operatorIdx),
                                        prevedNaStrom(vyraz.substring(0, operatorPoz)),
                                        prevedNaStrom(vyraz.substring(operatorPoz + 1)));
                }

                // Poznamka: Ak sme nenasli operator, tak je to alebo konstanta, alebo
                // cely vyraz je ozatvorkovany

                // Ak je cely vyraz ozatvorkovany, tak nechame rozparsovat jeho vnutornu
                // cast
                if ((vyraz.charAt(0) == '(')
                                && (vyraz.charAt(vyraz.length() - 1) == ')'))
                        return prevedNaStrom(vyraz.substring(1, vyraz.length() - 1));

                // Ak sme tu, tak to musi byt cislo
                try {
                        return new Hodnota(Double.parseDouble(vyraz));
                } catch (NumberFormatException e) {
                        throw new RuntimeException(
                                        "Zadany vyraz nie je korektny aritmeticky vyraz");
                }
        }

        /**
         * Koren aritmetickeho stromu vyrazu
         */
        private Clen koren;

        /**
         * Skontruuje novy aritmeticky vyraz
         *
         * @param vyraz
         *            retazec s aritmetickym vyrazom
         */
        public Vyraz(String vyraz) {
                koren = prevedNaStrom(vyraz);
        }

        @Override
        public String toString() {
                return koren.toString();
        }

        public String postfix() {
                return koren.postfix();
        }

        public static void main(String[] args) {
                Vyraz v = new Vyraz("(-3)+6/2+3*2");
                System.out.println(v.postfix());
        }
}

import java.util.*;

public class Osoba {
        /**
         * Meno osoby
         */
        private String meno;
        /**
         * Zoznam deti osoby
         */
        private List<Osoba> deti = new ArrayList<Osoba>();

        /**
         * Konstruktor osoby v strome potomkov
         * @param meno meno osoby
         */
        public Osoba(String meno) {
                this.meno = meno;
        }

        /**
         * Prida osobe dieta
         * @param dieta referencia na pridavane dieta
         */
        public void pridajDieta(Osoba dieta) {
                deti.add(dieta);
        }

        /**
         * Vrati celkovy pocet potomkov osoby
         */
        public int pocetPotomkov() {
                int pocetPotomkovDeti = 0;
                for (Osoba dieta: deti)
                        pocetPotomkovDeti += dieta.pocetPotomkov();

                return pocetPotomkovDeti + deti.size();
        }

        /**
         * Vypise rodostrom osoby
         */
        public void vypisRodostrom() {
                System.out.println(meno);
                for (Osoba dieta: deti)
                        dieta.vypisRodostrom();
        }

        public void pridajDoZoznamu(List<Osoba> zoznam) {
                /*
                for (Osoba dieta: deti) {
                        zoznam.add(dieta);
                        dieta.pridajDoZoznamu(zoznam);
                }
                */
                zoznam.add(this);
                for (Osoba dieta: deti)
                        dieta.pridajDoZoznamu(zoznam);
        }

        /**
         * Main s vytvorenim stromu potomkov pre Janka
         */
        public static void main(String[] args) {
                Osoba janko = new Osoba("Janko");
                Osoba jozko = new Osoba("Jozko");
                Osoba maria = new Osoba("Maria");
                Osoba karol = new Osoba("Karol");
                Osoba lucia = new Osoba("Lucia");
                Osoba petra = new Osoba("Petra");
                janko.pridajDieta(jozko);
                janko.pridajDieta(maria);
                janko.pridajDieta(karol);
                karol.pridajDieta(lucia);
                karol.pridajDieta(petra);
                janko.vypisRodostrom();
        }
}

/**
 * Trieda reprezentujuca uzol binarneho stromu
 */
public class Uzol {
        /**
         * Hodnota ulozena v uzle stromu
         */
        private int hodnota;

        /**
         * Referencia na laveho syna uzla (koren laveho podstromu)
         */
        private Uzol lavy;

        /**
         * Referencia na praveho syna uzla (koren praveho podstromu)
         */
        private Uzol pravy;

        /**
         * Konstruktor uzla binarneho stromu
         *
         * @param hodnota
         * @param lavy
         * @param pravy
         */
        public Uzol(int hodnota, Uzol lavy, Uzol pravy) {
                this.hodnota = hodnota;
                this.lavy = lavy;
                this.pravy = pravy;
        }

        /**
         * Vypise obsah uzlov stromu, ktoreho korenom je tento vrchol. Realizuje
         * preorder prechod.
         */
        public void vypis() {
                // Vypiseme hodnotu
                System.out.println(hodnota);

                // Ak je lavy syn, poziadame ho o vypis hodnot laveho podstromu
                if (lavy != null)
                        lavy.vypis();

                // Ak je pravy syn, poziadame ho o vypis hodnot praveho podstromu
                if (pravy != null)
                        pravy.vypis();
        }

        /**
         * Vrati maximum v strome, ktoreho je tento uzol korenom
         */
        public int maximum() {
                // Predpokladame, ze maximum je hodnota v tomto uzle
                int vysledok = hodnota;

                // Ak je lavy syn, vyberieme bud maximum z laveho podstromu
                // alebo hodnotu v tomto uzle - podla toho, co je vacsie
                if (lavy != null)
                        vysledok = Math.max(vysledok, lavy.maximum());

                // Ak je pravy syn, skusime, ci maximum v pravom podstrome nie je
                // vacsie
                if (pravy != null)
                        vysledok = Math.max(vysledok, pravy.maximum());

                return vysledok;
        }

        /**
         * Zisti, ci sa zadana hodnota nachadza v strome, ktoreho je tento uzol
         * korenom
         *
         * @param hladany
         *            hladana hodnota
         */
        public boolean obsahuje(int hladany) {
                // Ak je hladana hodnota v tomto uzle, koncime ihned
                if (hodnota == hladany)
                        return true;

                // Ak je lavy syn, skusime, ci hladana hodnota nie je v podstrome,
                // ktoreho je lavy syn korenom
                if (lavy != null)
                        if (lavy.obsahuje(hladany))
                                return true;

                // Ak je pravy syn, skusime, ci hladana hodnota nie je v podstrome,
                // ktoreho je pravy syn korenom
                if (pravy != null)
                        if (pravy.obsahuje(hladany))
                                return true;

                return false;
        }

        public int getHodnota() {
                return hodnota;
        }

        public void setHodnota(int hodnota) {
                this.hodnota = hodnota;
        }

        public int sucet() {
                int vysledok = hodnota;
                if (lavy != null)
                        vysledok += lavy.sucet();
                if (pravy != null)
                        vysledok += pravy.sucet();

                return vysledok;
        }

        public Integer sucet(int uroven) {
                if (uroven == 0) {
                        return hodnota;
                }
                Integer vysledokLavy = null;
                Integer vysledokPravy = null;

                if (lavy != null)
                        vysledokLavy = lavy.sucet(uroven--);
                if (pravy != null)
                        vysledokPravy = pravy.sucet(uroven - 1);

                if (vysledokLavy == null && vysledokPravy == null)
                        return null;

                Integer vysledok = new Integer(0);

                if (vysledokLavy != null)
                        vysledok += vysledokLavy;

                if (vysledokPravy != null)
                        vysledok += vysledokPravy;

                return vysledok;
        }

        public Integer sucet2(int uroven) {
                if (uroven == 0) {
                        return hodnota;
                }

                int vysledok = 0;
                boolean mamVysledok = false;

                if (lavy != null) {
                        Integer odSyna = lavy.sucet2(uroven - 1);
                        if (odSyna != null) {
                                vysledok += odSyna;
                                mamVysledok = true;
                        }
                }

                if (pravy != null) {
                        Integer odSyna = pravy.sucet2(uroven - 1);
                        if (odSyna != null) {
                                vysledok += odSyna;
                                mamVysledok = true;
                        }
                }

                return mamVysledok ? vysledok : null;
        }

        public static void main(String[] args) {
                Uzol koren = new Uzol(5, new Uzol(2, new Uzol(8, null, null), null),
                                new Uzol(9, null, null));
                koren.vypis();
                System.out.println("Maximum je " + koren.maximum());
        }
}

/**
 * Trieda reprezentujuca aritmeticky vyraz
 */
public class Vyraz {

        /**
         * Rozhranie, ktore implementuju vsetky uzly aritmetickeho stromu
         */
        private interface Clen {
                @Override
                public String toString();

                public double vyhodnot();

                public String postfix();
        }

        /**
         * Trieda implementujuca uzol stromu aritmetickeho stromu, ktory
         * reprezentuje binarnu operaciu
         */
        private static class BinarnaOperacia implements Clen {
                private char operator;
                private Clen lavyPodvyraz;
                private Clen pravyPodvyraz;

                public BinarnaOperacia(char operator, Clen lavy, Clen pravy) {
                        this.operator = operator;
                        this.lavyPodvyraz = lavy;
                        this.pravyPodvyraz = pravy;
                }

                @Override
                public String toString() {
                        return "(" + lavyPodvyraz.toString() + operator
                                        + pravyPodvyraz.toString() + ")";
                }

                @Override
                public double vyhodnot() {
                        double lh = lavyPodvyraz.vyhodnot();
                        double ph = pravyPodvyraz.vyhodnot();
                        switch (operator) {
                        case '+':
                                return lh + ph;
                        case '-':
                                return lh - ph;
                        case '*':
                                return lh * ph;
                        case '/':
                                return lh / ph;
                        }

                        return Double.NaN;
                }

                @Override
                public String postfix() {
                        return lavyPodvyraz.postfix() + " " + pravyPodvyraz.postfix()
                                        + operator;
                }
        }

        /**
         * Trieda implementujuca uzol aritmetickeho stromu, ktory reprezentuje
         * konstantu
         */
        private static class Hodnota implements Clen {
                private double hodnota;

                public Hodnota(double hodnota) {
                        this.hodnota = hodnota;
                }

                @Override
                public String toString() {
                        return Double.toString(hodnota);
                }

                @Override
                public double vyhodnot() {
                        return hodnota;
                }

                @Override
                public String postfix() {
                        return Double.toString(hodnota);
                }
        }

        /**
         * Symboly operacii od najnizsej priority po najvyssiu
         */
        private static final String SYMBOLY_OPERACII = "+-*/";

        /**
         * Prevedie zadany vyraz do aritmetickeho stromu
         *
         * @param vyraz
         *            vyraz, ktory sa ma parsovat
         * @return referencia na koren aritmetickeho stromu
         */
        private static Clen prevedNaStrom(String vyraz) {
                // Odstranime zbytocne medzery
                vyraz = vyraz.trim();

                // Najdeme operator s najnizsou prioritou, ktory nie je v zatvorkach
                int operatorIdx = Integer.MAX_VALUE;
                int operatorPoz = -1;
                int pocitadloZatvoriek = 0;

                for (int i = 0; i < vyraz.length(); i++) {
                        char znak = vyraz.charAt(i);

                        if (znak == '(')
                                pocitadloZatvoriek++;

                        if (znak == ')')
                                pocitadloZatvoriek--;

                        int priorita = SYMBOLY_OPERACII.indexOf(znak);
                        if ((priorita != -1) && (pocitadloZatvoriek == 0) && (i > 0)) {
                                if (priorita < operatorIdx) {
                                        operatorIdx = priorita;
                                        operatorPoz = i;
                                }
                        }
                }

                // Rozdelime vyraz na podvyrazy
                if (operatorPoz != -1) {
                        return new BinarnaOperacia(SYMBOLY_OPERACII.charAt(operatorIdx),
                                        prevedNaStrom(vyraz.substring(0, operatorPoz)),
                                        prevedNaStrom(vyraz.substring(operatorPoz + 1)));
                }

                // Poznamka: Ak sme nenasli operator, tak je to alebo konstanta, alebo
                // cely vyraz je ozatvorkovany

                // Ak je cely vyraz ozatvorkovany, tak nechame rozparsovat jeho vnutornu
                // cast
                if ((vyraz.charAt(0) == '(')
                                && (vyraz.charAt(vyraz.length() - 1) == ')'))
                        return prevedNaStrom(vyraz.substring(1, vyraz.length() - 1));

                // Ak sme tu, tak to musi byt cislo
                try {
                        return new Hodnota(Double.parseDouble(vyraz));
                } catch (NumberFormatException e) {
                        throw new RuntimeException(
                                        "Zadany vyraz nie je korektny aritmeticky vyraz");
                }
        }

        /**
         * Koren aritmetickeho stromu vyrazu
         */
        private Clen koren;

        /**
         * Skontruuje novy aritmeticky vyraz
         *
         * @param vyraz
         *            retazec s aritmetickym vyrazom
         */
        public Vyraz(String vyraz) {
                koren = prevedNaStrom(vyraz);
        }

        @Override
        public String toString() {
                return koren.toString();
        }

        public double vyhodnot() {
                return koren.vyhodnot();
        }

        public String postfix() {
                return koren.postfix();
        }

        public static void main(String[] args) {
                Vyraz v = new Vyraz("(-3)+6/2+3*2");
                System.out.println(v);
        }
}