#APS Lab 2/5

Модифициран XML код Problem 2 (0 / 0)

Даден е некој модифициран XML код. Модифицираниот XML код ги користи симболите '[' и ']', за отварање и затворање на таг, соодветно, наместо стандардните '

' и '>'. Треба да се провери дали сите тагови во кодот се правилно вгнездени (дали кодот е валиден) т.е. дали секој отворен таг има соодветен затворен таг со истото име на соодветното место во кодот. За поедноставување, дадено е дека секој отворен таг мора да има свој затворен таг и дека таговите немаат атрибути.

На влез е даден бројот на редови во кодот и самиот XML со секој таг во посебен ред, а на излез треба да се испечати 1 или 0 за валиден или невалиден код, соодветно.

Објаснување: Во модифицираниот XML код секој отворен таг е во облик [imeNaTag], а соодветниот затворен таг е во облик [/imeNaTag].

Пример за правилно вгнездени тагови во XML e:

[tag1]
[tag2]
Podatok
[/tag2]
[/tag1]

Пример за неправилно вгнездени тагови во XML e:

[tag1]
[tag2]
Podatok
[/tag1]
[/tag2]

Име на класата (Java): CheckXML


====================================================================================================================================

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.NoSuchElementException;

public class CheckXML {

    static class SLLNode<E> {
        protected E element;
        protected SLLNode<E> succ;

        public SLLNode(E elem, SLLNode<E> succ) {
            this.element = elem;
            this.succ = succ;
        }

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


    static interface Stack<E> {

        // Elementi na stekot se objekti od proizvolen tip.

        // Metodi za pristap:

        public boolean isEmpty ();
        // Vrakja true ako i samo ako stekot e prazen.

        public E peek ();
        // Go vrakja elementot na vrvot od stekot.

        // Metodi za transformacija:

        public void clear ();
        // Go prazni stekot.

        public void push (E x);
        // Go dodava x na vrvot na stekot.

        public E pop ();
        // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
    }

    static class LinkedStack<E> implements Stack<E> {

        //Stekot e pretstaven na sledniot nacin: top e link do prviot jazol
        // na ednostrano-povrzanata lista koja sodrzi gi elementite na stekot .
        private SLLNode<E> top;

        public LinkedStack () {
            // Konstrukcija na nov, prazen stek.
            top = null;
        }

        public boolean isEmpty () {
            // Vrakja true ako i samo ako stekot e prazen.
            return (top == null);
        }

        public E peek () {
            // Go vrakja elementot na vrvot od stekot.
            if (top == null)
                throw new NoSuchElementException();
            return top.element;
        }

        public void clear () {
            // Go prazni stekot.
            top = null;
        }

        public void push (E x) {
            // Go dodava x na vrvot na stekot.
            top = new SLLNode<E>(x, top);
        }

        public E pop () {
            // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
            if (top == null)
                throw new NoSuchElementException();
            E topElem = top.element;
            top = top.succ;
            return topElem;
        }

    }

    public static int checkValidity(String[] redovi){

        LinkedStack<String> stek = new LinkedStack<String>();
        for(int i = 0; i < redovi.length; i++){

            if(redovi[i].charAt(0) == '['){
                // dali e zatvaracki - pop
                if(redovi[i].charAt(1) == '/'){
                    String el = stek.pop();
                    boolean b = redovi[i].endsWith(el.substring(1));
                    if ( b == false){
                        return 0;
                    }
                }else{
                    stek.push(redovi[i]);
                }
            }


        }

        return 1;
    }


    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int n = Integer.parseInt(s);
        String [] redovi = new String[n];

        for(int i=0;i<n;i++)
            redovi[i] = br.readLine();

        int valid = checkValidity(redovi);

        // Vasiot kod tuka
        // Moze da koristite dopolnitelni funkcii ako vi se potrebni

        System.out.println(valid);

        br.close();
    }
}