Riešenia (skupina E, 3. týždeň)

public class SpajanyZoznam {

        private static class Uzol {
                int hodnota;
                Uzol dalsi;
        }

        private Uzol prvy = null;
        private int pocetUzlov;
        private Uzol posledny = null;

        public void pridajNaZaciatok(int hodnota) {
                /*
                 * Uzol pridavany = new Uzol(); pridavany.hodnota = hodnota;
                 * pridavany.dalsi = prvy; prvy = pridavany;
                 */

                Uzol pridavany = new Uzol();
                pridavany.hodnota = hodnota;
                pridavany.dalsi = prvy;
                prvy = pridavany;

                if (pocetUzlov++ == 0)
                        posledny = pridavany;
        }

        @Override
        public String toString() {
                String vysledok = "[";
                Uzol aktualny = prvy;
                while (aktualny != null) {
                        if (aktualny != prvy)
                                vysledok += ", ";

                        vysledok += aktualny.hodnota;
                        aktualny = aktualny.dalsi;
                }

                return vysledok + "]";
        }

        public int sucet() {
                // Referencia na uzol zoznamu, na ktorom sa prave nachadzame
                Uzol aktualny = prvy;
                // Premenna, v ktorej akumulujeme sucet
                int vysledok = 0;
                // Kym sme na nejakom uzle ...
                while (aktualny != null) {
                        // Priratame hodnotu uzla
                        vysledok += aktualny.hodnota;
                        // Presunieme sa na dalsi uzol v zozname
                        aktualny = aktualny.dalsi;
                }

                return vysledok;
        }

        private Uzol vratITy(int index) {
                if (index < 0 || index >= pocetUzlov)
                        return null;
                if (index == pocetUzlov - 1)
                        return posledny;

                Uzol aktualny = prvy;
                // index
                int idx = 0;
                // Kym sme na nejakom uzle ...
                while (aktualny != null) {

                        if (idx++ == index)
                                return aktualny;
                        aktualny = aktualny.dalsi;
                }

                return null;

                /*
                 * // Referencia na uzol zoznamu, na ktorom sa prave nachadzame Uzol
                 * aktualny = prvy; // index int idx = 0; // Kym sme na nejakom uzle ...
                 * while (aktualny != null) {
                 *
                 * if(idx++==index)return aktualny; aktualny =aktualny.dalsi; }
                 *
                 * return null;
                 */
        }

        public int get(int index) {
                Uzol u = vratITy(index);
                if (u == null)
                        throw new IndexOutOfBoundsException("Index: " + index);

                return u.hodnota;
        }

        public void set(int index, int value) {
                Uzol u = vratITy(index);
                if (u == null)
                        throw new IndexOutOfBoundsException("Index: " + index);

                u.hodnota = value;
        }

        public void add(int value) {
                if (posledny == null)
                        pridajNaZaciatok(value);
                else {
                        Uzol novy = new Uzol();
                        novy.hodnota = value;
                        posledny.dalsi = novy;

                        posledny = novy;
                        pocetUzlov++;
                }

                /*
                 * if (prvy == null) { pridajNaZaciatok(value); } else { Uzol aktualny =
                 * prvy; while (aktualny.dalsi != null) { aktualny =aktualny.dalsi; }
                 *
                 * Uzol novy = new Uzol(); novy.hodnota = value; aktualny.dalsi = novy;
                 * }
                 */
        }

        public void add(int index, int value) {
                if (index == 0)
                        pridajNaZaciatok(value);
                else {
                        Uzol u = vratITy(index - 1);
                        if (u == null)
                                throw new IndexOutOfBoundsException("Index: " + index);

                        Uzol novy = new Uzol();
                        novy.hodnota = value;
                        novy.dalsi = u.dalsi;
                        u.dalsi = novy;

                        if (pocetUzlov++ == index)
                                posledny = novy;
                }

                /*
                 * if (index == 0) pridajNaZaciatok(value); else { Uzol u =
                 * vratITy(index - 1); if (u == null) throw new
                 * IndexOutOfBoundsException("Index: " + index);
                 *
                 * Uzol novy = new Uzol(); novy.hodnota = value; novy.dalsi = u.dalsi;
                 * u.dalsi = novy; }
                 */
        }

        public void remove(int index) {
                if (pocetUzlov <= 0)
                        return;
                if (index < 0 || index >= pocetUzlov)
                        throw new IndexOutOfBoundsException("Index: " + index);

                if (index == 0) {
                        prvy = prvy.dalsi;
                        if (pocetUzlov == 1)
                                posledny = null;
                } else {
                        Uzol u = vratITy(index - 1);
                        if (u.dalsi.dalsi == null) {
                                posledny = u;
                        }
                        u.dalsi = u.dalsi.dalsi;
                }

                pocetUzlov--;
                /*
                 * if (index == 0 && prvy == null) throw new
                 * IndexOutOfBoundsException("Index: " + index); else if (index == 0)
                 * prvy = prvy.dalsi; else { Uzol u = vratITy(index - 1); if (u == null
                 * || u.dalsi == null) throw new IndexOutOfBoundsException("Index: " +
                 * index);
                 *
                 * u.dalsi = u.dalsi.dalsi; }
                 */
        }

        public int getPosledny() {
                return posledny.hodnota;
        }
}

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Zasobnik {

        public static boolean spravneOzatvorkovany(String vyraz) {
                Stack<Character> zasobnik = new Stack<Character>();

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

                        switch (znak) {
                        case '(':
                        case '[':
                        case '{':
                                zasobnik.push(znak);
                                break;

                        case ')':
                                if (zasobnik.isEmpty() || zasobnik.pop() != '(')
                                        return false;
                                break;

                        case ']':
                                if (zasobnik.isEmpty() || zasobnik.pop() != '[')
                                        return false;
                                break;

                        case '}':
                                if (zasobnik.isEmpty() || zasobnik.pop() != '{')
                                        return false;
                                break;

                        default:
                                break;
                        }
                }

                return zasobnik.isEmpty();
        }

        public static boolean spravneOzatvorkovany(String vyraz, Map<Character, Character> sady) {
                // kluce su zatvaracie zatvorky
                // hodnoty su otvaracie zatvorky
                Stack<Character> zasobnik = new Stack<Character>();

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

                        if (sady.containsValue(znak))
                                zasobnik.push(znak);
                        else if (sady.containsKey(znak))
                                if (zasobnik.isEmpty() || zasobnik.pop() != sady.get(znak))
                                        return false;
                }

                return zasobnik.isEmpty();
        }

        public static void main(String[] args) {
                String vyraz = "[({} {} {/  <  >  \\})]< / ([{}]) \\ >";
                Map<Character, Character> sady = new HashMap<Character, Character>();
                sady.put(')', '(');
                sady.put(']', '[');
                sady.put('}', '{');
                sady.put('>', '<');
                sady.put('\\', '/');

                System.out.println(spravneOzatvorkovany(vyraz, sady));
        }
}

import java.util.HashMap;
import java.util.Locale;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class Postfix {

        private Map<Character, Integer> operatory = new HashMap<Character, Integer>();

        public Postfix() {
                operatory.put('+', -2);
                operatory.put('-', -2);
                operatory.put('*', -3);
                operatory.put('/', -3);
                operatory.put('^', 4);
        }

        private boolean jeOperator(char op) {
                return operatory.containsKey(op);
        }

        private int porovnajPrioritu(char op1, char op2) {
                int pr1 = Math.abs(operatory.get(op1));
                int pr2 = Math.abs(operatory.get(op2));

                return pr1 - pr2;
        }

        private boolean jeLavoAsociativny(char op) {
                return operatory.get(op) < 0;
        }

        private double vyhodnot(double arg1, double arg2, char op) {
                switch (op) {
                case '+':
                        return arg1 + arg2;
                case '-':
                        return arg1 - arg2;
                case '*':
                        return arg1 * arg2;
                case '/':
                        return arg1 / arg2;
                case '^':
                        return Math.pow(arg1, arg2);

                default:
                        throw new RuntimeException("Nepoznam operator!");
                }
        }

        private String infixNaPostfix(String vyraz) {
                StringBuilder sb = new StringBuilder();
                Stack<Character> opStack = new Stack<Character>();
                Scanner s = new Scanner(vyraz);
                s.useLocale(Locale.US);

                while (s.hasNext()) {
                        String t = s.next();
                        char op = t.charAt(0);

                        if (jeOperator(op)) {
                                if (!opStack.isEmpty() && jeOperator(opStack.peek())) {
                                        boolean podmienkaL = jeLavoAsociativny(op)
                                                        && porovnajPrioritu(op, opStack.peek()) <= 0;
                                        boolean podmienkaR = !jeLavoAsociativny(op)
                                                        && porovnajPrioritu(op, opStack.peek()) < 0;

                                        if (podmienkaL || podmienkaR) {
                                                sb.append(opStack.pop() + " ");
                                        }
                                }

                                opStack.push(op);
                        } else if (op == '(') {
                                opStack.push(op);
                        } else if (op == ')') {
                                while (!opStack.isEmpty() && opStack.peek() != '(')
                                        sb.append(opStack.pop() + " ");
                                opStack.pop(); // vyhodit '('
                        } else {
                                sb.append(t + " ");
                        }
                }

                while (!opStack.isEmpty())
                        sb.append(opStack.pop() + " ");

                return sb.toString();
        }

        public double vyhodnotInfix(String vyraz) {
                String postfix = infixNaPostfix(vyraz);
                return vyhodnotPostfix(postfix);
        }

        public double vyhodnotPostfix(String vyraz) {
                Scanner s = new Scanner(vyraz);
                s.useLocale(Locale.US);
                Stack<Double> zasobnik = new Stack<Double>();

                while (s.hasNext()) {
                        String cast = s.next();
                        if (jeOperator(cast.charAt(0))) {
                                double arg2 = zasobnik.pop();
                                double arg1 = zasobnik.pop();
                                zasobnik.push(vyhodnot(arg1, arg2, cast.charAt(0)));
                        } else {
                                zasobnik.push(Double.parseDouble(cast));
                        }
                }

                return zasobnik.pop();
        }

        public static void main(String[] args) {
                String vyraz = "( 1 + 5 ) * 8 - 7 * ( 5 + 2 )";

                Postfix p = new Postfix();
                System.out.println(p.vyhodnotInfix(vyraz));
        }
}