Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Стек, теги XML  [new]
utlikk
Member

Откуда:
Сообщений: 2
Задание такое:
.
Написать программу, проверяющую правильно ли в файле XML вложены и закрыты теги с ипользованием стека как вспомогательной системы. Программа проверяет только некоторые теги, их список записан в текстовом файле с синтаксисом, используемом во внешнем представлении объекта класса Properties.
.
txt файл с Properties такой:
count=3
e1=YEAR
e2=PRICE
e3=CD
.
Подскажите в какую сторону двигаться, что можно тут попробовать, потому что не хватает значний языка для реализации такой задачи.
Моя идея такая: создать два стека - левый, в который ложим открывающиеся теги, и правый для закрывающихся, а потом их сравниваем, при не правильно составленном XML документе получим предупреждение типа в таком то месте ошибка.

К сообщению приложен файл (test1fail.xml - 5Kb) cкачать
26 мар 20, 09:42    [22106135]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
utlikk
Member

Откуда:
Сообщений: 2
Предположительный код:

class ReadProperties {

       public static void main(final String[] args) throws IOException {
        final Properties props = new Properties();
        props.load(new FileReader("test1.txt"));
        System.out.println(props);

        final int count = Integer.parseInt(props.getProperty("count"));
        System.out.println("count=" + count);

        for (int i = 1; i <= count; i++) {
                final String propertyName = "e" + i;
                final String markUp = props.getProperty(propertyName);
                System.out.println("markUp=" + markUp);
        }

        Stack<String> left = new Stack<>();
        Stack<String> right = new Stack<>();
        String s;

        FileReader reader = new FileReader("test1fail.xml");
        while (reader.ready()){
            String data = reader.toString();
        int licz = 0;
        for(int a = 0; a <= data.length()+1 ; a++){

            s = String.valueOf(data.charAt(a));

            switch (s) {
                case "<YEAR>":
                case "<CD>":
                case "<PRICE>":
                    left.push(s);
                    break;
                case "</YEAR>":
                case "</CD>":
                case "</PRICE>":
                    right.push(s);
                    break;
            }

            String l = left.pop();
            String r = right.pop();

            if (l.equals(r)) {
            } else {
                System.out.println("Проблема в " + licz + "ом по счету "+ l);
            }
            licz++;
        }
       }
     reader.close();
    }
}


Сообщение было отредактировано: 26 мар 20, 12:42
26 мар 20, 11:36    [22106211]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Garrick
Member

Откуда: Москва
Сообщений: 2983
utlikk, что-нибудь про XSD и валидацию XML слышали?
26 мар 20, 13:00    [22106269]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
utlikk
Предположительный код:

        for(int a = 0; a <= data.length()+1 ; a++){

            s = String.valueOf(data.charAt(a));

            switch (s) {
                case "<YEAR>":
....
            }

Жесть какая.
Понятно, что "предположительный", но все же жесть.

Читать книжки про конечные автоматы и парсеры. Вроде что-то было у Вирта. Хотя книжка Вирта мне не очень понравилась, но других просто не помню.

https://www.ozon.ru/context/detail/id/4803779/

AFAIK
26 мар 20, 13:55    [22106306]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
utlikk

Моя идея такая: создать два стека....

Стека явно достаточно одного.
При открытии тэга - push
При закрытии тэга - pop

А текущей элемент вообще в стек класть не нужно

IMHO
26 мар 20, 13:57    [22106307]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
mayton
Member

Откуда: loopback
Сообщений: 45514
utlikk, в этой задаче есть два смысла.

1) Ты изучаешь xml или алгоритмы со стеком и просто играешся. Тогда делай стеками или деками или очередями как хочешь.

2) Ты делаешь продуктовую систему которая должна
- проверить что документ является well-formatted (правильно форматированным). Для этого его можно просто
"перемотать через XMLStreamReader.
- проверить что предыдущий пункт выполнен + еще и документ валиден. Это уже - соответсвие DTD (Document Type
Definition) старое и архаичное или XSD (XML Schema definition). Схему ты должен либо описать сам либо взять готовую.
26 мар 20, 14:11    [22106313]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
Если кто помнит книжки по построению парсеров и конечных автоматов, стоило бы автору топика ссылок накидать. IMHO. В любом случае пригодится.
26 мар 20, 14:20    [22106318]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
mayton
Member

Откуда: loopback
Сообщений: 45514
Все зависит от глубины увлеченности человека. Мне сегодня тема проектирования парсеров
настолько далека что я вообще не могу ее осилить. Просто в силу своего перфекционизма.
Начинаю делать с Antlr/JavaCC и понимаю как глубоко закопался и потом плюю и решаю
все конечным автоматом над потоком символов. Просто задачи обычно тупые попадаются.
26 мар 20, 14:22    [22106319]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
mayton

Ну дык в примере кода даже не видна попытка побить на токены. Т.е. прочитать что нибудь про конечные автомы стоило бы (а в книжке Вирт'а AFAIK про конечные автоматы как-то бедно написано)

mayton
потом плюю и решаю все конечным автоматом над потоком символов

AFAIK по общению с бывшими студентами, хорошо, если после обучения вообще такой термин помнят/знают ))) Но про использование данного термина в банальных задачах типа побить входной поток на токены - вместо sql.ru все же лучше почитать книжки.
+

Выложенный пример кода с конструкцией:
        for(int a = 0; a <= data.length()+1 ; a++){

            s = String.valueOf(data.charAt(a));

все же немного жесть ))) даже для "предположительный код"

Что лично мне не нравится:
1) для чтения входного потока совершенно не нужно загонять его в память и максимум достаточно операции readChar
2) для дальнейшей проверки на тэги, входной поток из потока символов нужно превратить в поток токенов/тэгов. Т.е. нужно реализовать этот самый конечный автомат, который readChar превратит в readToken или readXmlTag

IMHO
26 мар 20, 14:52    [22106349]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
mayton
Member

Откуда: loopback
Сообщений: 45514
Давай поможем бедняге. Чисто механический рефакторинг. Даже вот глубого не вникая в логику
а просто выбрасывая ненужные действия.
26 мар 20, 15:09    [22106368]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
тогда уж вбрасывая нужные
сначала - преобразование входного потока в поток токенов/тэгов
26 мар 20, 15:21    [22106379]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
mayton
Member

Откуда: loopback
Сообщений: 45514
Типо того
interface TokenStream {
   boolean hasNext();
   String nextToken();
}
26 мар 20, 15:30    [22106389]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
utlikk
Написать программу, проверяющую правильно ли в файле XML вложены и закрыты теги с ипользованием стека как вспомогательной системы


MyTokinizer tokinizer = new MyTokinizer( new FileInputStream( fileName ) );
MyToken currentToken = null;
Stack stack = new ....;
while ( tokinizer.hasNext() {
   MyToken  nextToken = tokinizer.readToken();
   if ( nextToken.isOpenTag() ) {
      // Открывающий тэг, текущий просто сохраняем в стеке
      stack.push( currentToken );
      currentToken = nextToken;
   } else if ( nextToken.isCloseTag() ) {
     // или XML начинается с закрывающего тэга - оригинально
     // или закрывающих тэгов больше, что открывающих
     if ( currentToken  == null ) {
        throw new MyTokenMistmathException();
     }
     // Закрывающий тэг должен равняться открывающему
     if ( ! nextToken.getTagName().equal( currentToken.getTagName ) ) {
        throw new MyTokenMistmathException();
     }
     currentToken = stack.pop();
     // EmptyStackException быть не может, т.к. первым элементом
     // мы все равно будет туда класть currentToken=null
  }
}  // while
// Поток закончился, проверяем, что не осталось открытых тэгов
if ( stack.size() != 0 ) {
  throw new MyTokenMistmathException();
}


utlikk
Программа проверяет только некоторые теги

странное условие, если нужно - добавить
зачем проверять только некоторые, когда проще проверить все - не понятно
26 мар 20, 15:45    [22106400]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
mayton
Типо того
interface TokenStream {
   boolean hasNext();
   String nextToken();
}

В топку. Тэг в XML имеет значительно более сложную структуру, что String
26 мар 20, 15:45    [22106402]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
mayton
Member

Откуда: loopback
Сообщений: 45514
Согласен. Ну так ты за беднягу все сделаешь. Лучше пускай бы он сам реализацию писал.
26 мар 20, 15:49    [22106406]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
Например токен из входного потока
<PRICE value="100" currency="USD">
явно не String

Как минимум нам нужно знать:
1. Тип токена/тэга:
1.1. Открывающий тэг <PRICE...>
1.2. Закрывающий тэг </PRICE>
1.3. "самодостаточный" тэг <PRICE .../>
1.4. Комеентарии
1.5. Значения между тегами <tag>VALUE</tag> и прочий мусор
возможно что-то еще. По хорошему нужно читать стандарт XML

1.3 - 1.5 для данной задачи в принципе не важны, но для парсера токенов будут различаться (например комментарии! вполне могут содержать < >)

2. Имя тэга, если это тег
Т.е. <PRICE.... и <PRICE..../> и </PRICE => PRICE

Для простоты, я бы хранил:

tokenType -
rawSource - сырые данные, весь входной поток данных включая < и >
tagName - выделенное имя тэга

вычлинять атрибуты в тэгах вряд ли требуется

Сообщение было отредактировано: 26 мар 20, 15:59
26 мар 20, 15:55    [22106408]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
AFAIK В токенайзере самое мутороное будет комментарии выделить.

<!--Your comment-->

одна эта конструкция 8 состояний конечного автомата даст ((( мне кажется больше, чем весь остальной токенайзер )))
26 мар 20, 15:59    [22106412]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
mayton
Согласен. Ну так ты за беднягу все сделаешь. Лучше пускай бы он сам реализацию писал.

То, что почему-то не понимают "студенты желающие помоши"

Если он принесет _нормальный_ токенайз преподавателю, то первый вопрос будет:
что такое конечный автомат?
после чего преподаватель с точностью 99.99% будет знать, что задание списано/заказано
26 мар 20, 16:09    [22106419]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
mayton
Member

Откуда: loopback
Сообщений: 45514
Полную спеку сложно поддержать. Вместе с блоками processing instructions и entities.

Лучше забить пока на коментарии и сделать что-то простое и деревянное. А потом по необходимости допилить.
26 мар 20, 16:09    [22106420]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
mayton
Вместе с блоками processing instructions и entities.

+100500

Если есть ссылка на спеку, линкани в тему.

лично я сложности не вижу. с комментариями тоже сложности нет, но больно монстрообразно получится.

Есть еще открытый вопрос: а имя тэга по стандарту может содержать символы < и > ?
+

кто читал рендеринг срачь в соседней ветке, вопрос должны понять )))


mayton
Лучше забить пока на коментарии

Облом )))
В приложенном топик стартере файле есть комментарии
26 мар 20, 16:18    [22106424]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
mayton
Member

Откуда: loopback
Сообщений: 45514
Не смотрел его файл.

Надо спросить его.

Афтор. Этот кейс покрывает все-все варианты? Или еще может какой-то синтасис прилететь?
26 мар 20, 16:31    [22106436]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
mayton
Member

Откуда: loopback
Сообщений: 45514
Я боюсь читать про серверный рендеринг. У меня есть свой взгяд на проблему. Но поскольку я не юайщик
то моё мнение носит сугубо теоретически и рекомендательный характер и вряд-ли будет интересно
тем зубрам которые там бодаются. Пускай себе бодаются вусмерть..

Хотя по части инженерной графики я много чего знаю и могу рассказать.
26 мар 20, 16:37    [22106438]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
Фигня получилась. Нужно спецификация по XML читать.

Отделяет тэги от не тэгов, за тот же проход выделяет имя токена
Отделение OPEN_TAG от CLOSE_TAG не сделано, пусть автор читает книжки и дорабатывает )))

Осталось добавить состояния парсера для выделения символа '/' перед именем токена и можно двигаться дальше )))

Почему фигня, т.к. в атрибутах тэга вполне могут встретиться символы / < > Текущий вариант лично меня бы не устроил. Но, возможно, для "студента" и пойдет.
+

import java.io.IOException;
import java.io.InputStream;
import java.io.Reader;
import java.io.StringReader;

enum MyXmlTokenType {  TT_UNKNOWN_TAG, TT_OPEN_TAG, TT_CLOSE_TAG, TT_ONE_TAG, TT_OTHERS }

class MyXmlToken {
     MyXmlTokenType tokenType;
     StringBuilder rawSource;
     StringBuilder tokenName;
     public MyXmlToken() {
         tokenType = MyXmlTokenType.TT_OTHERS;
         rawSource = new StringBuilder();
         tokenName = new StringBuilder();
     }
}

enum TokenizerState { ST_START, ST_TAG_OPENED, ST_TAG_NAME, ST_TAG_AFTER_NAME, ST_OTHER_TEXT }

class MyTokenizer {
    boolean isEof;
    Reader inp;
    int char_to_return;

    public MyTokenizer(Reader reader) {
        inp = reader;
        char_to_return = -1;
        isEof = false;
    }
    boolean hasNext() {
        return ! isEof;
    }
    MyXmlToken readNextToken() throws IOException {
        TokenizerState currentState = TokenizerState.ST_START;
        MyXmlToken token = new MyXmlToken();
        int c = -1, prev_char = -1;
        while ( true ) {
            // Запоминаем предыдущий символ, это как-то не совсем в духе
            // конечного автомата, но пофиг
            prev_char = c;
            // Чтение одного символа из входного потока
            // символ мог остаться недообработанным от пред. вызова
            if ( char_to_return > 0 ) {
               c = char_to_return;
               char_to_return = -1;
             } else {
               c = inp.read();
               if ( c <  0 ) {
                  isEof = true;
                  return token;
               }
            }
            switch ( currentState ) {
                // Начало потока, может быть символ < или любые другие
                case ST_START:
                    token.rawSource.append( (char)c );
                    if ( c=='<' ) {
                        currentState = TokenizerState.ST_TAG_OPENED;
                        token.tokenType = MyXmlTokenType.TT_UNKNOWN_TAG;
                    } else {
                        currentState = TokenizerState.ST_OTHER_TEXT;
                        token.tokenType = MyXmlTokenType.TT_OTHERS;
                    }
                    break;
                case ST_TAG_OPENED:
                    token.rawSource.append( (char)c );
                    if ( c=='>' ) {
                        return token;
                    } else {
                        currentState = TokenizerState.ST_TAG_NAME;
                        token.tokenName.append( (char)c );
                    }
                    break;
                case ST_TAG_NAME:
                    token.rawSource.append( (char)c );
                    if ( c=='>' ) {
                        return token;
                    }
                    else if ( c==' ' || c=='/' ) {   // Кроме пробелов могут быть и другие пробельные символы
                        currentState = TokenizerState.ST_TAG_AFTER_NAME;
                    }
                    else {
                        token.tokenName.append( (char)c );
                    }
                    break;
                case ST_TAG_AFTER_NAME:
                    token.rawSource.append( (char)c );
                    if ( c=='>' ) {
                        if ( prev_char=='/' ) {
                            token.tokenType=MyXmlTokenType.TT_ONE_TAG;
                        }
                        return token;
                    }
                    break;
                case ST_OTHER_TEXT:
                    if ( c=='<' ) {
                        this.char_to_return = c;
                        return token;
                    }
                    token.rawSource.append( (char)c );
                    break;
            }
        }
    }
}

public class Tokenizer1 {
    public static void main(String[] args) throws Exception {
        MyTokenizer tokenizer = new MyTokenizer( new StringReader( "<PRICE>100</PRICE><ONE/><ONE some text/><TAG attr=\"attr\">value</TAG>"));
        while ( tokenizer.hasNext() ) {
            MyXmlToken token = tokenizer.readNextToken();
            System.out.println( token.tokenType.toString()+" "+token.tokenName+" "+token.rawSource);
        }
    }
}
26 мар 20, 17:49    [22106487]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
mayton
Member

Откуда: loopback
Сообщений: 45514
Можно ускорить этот парсер.
26 мар 20, 18:15    [22106499]     Ответить | Цитировать Сообщить модератору
 Re: Стек, теги XML  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8475
mayton
Можно ускорить этот парсер.

Чего там ускорять то?
некая избыточность c rawSource есть, но как-то хочется возможности по уже распарсенному документу имееть возможно оригинал возстановить.
26 мар 20, 18:35    [22106509]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Java Ответить