Материал: 7 - Презентация - Дженерики, Абстрактные типы данных, Стек, Очередь
Центрдистанционногообучения
Пример: Сопоставление HTML тэгов
nДля полностью корректного HTML, каждому тегу <name> должен
соответствовать тег </name>
<body>
<center>
<h1> The Little Boat </h1> </center>
<p> The storm tossed the little boat like a cheap sneaker in an old washing machine. The three drunken fishermen were used to such treatment, of course, but
not the tree salesman, who even as a stowaway now felt that he
had overpaid for the voyage. </p> <ol>
<li> Will the salesman die? </li> <li> What color is the boat? </li> <li> And what about Naomi? </li> </ol>
</body>
The Little Boat
The storm tossed the little boat like a cheap sneaker in an old washing machine. The three drunken fishermen were used to such treatment, of course, but not the tree salesman, who even as
a stowaway now felt that he had overpaid for the voyage.
1.Will the salesman die?
2.What color is the boat?
3.And what about Naomi?
36 online.mirea.ru
Центрдистанционногообучения
Пример:Алгоритм сопоставления тегов(4/1)
import java.io.*;
import java.util.Scanner; import net.datastructures.*;
/** Упрощеннаяпроверкасоответстпарныхтеговия
HTML-документе. */ public class HTML {
/**выдпервыйиляемпоследнийсимволытег<> строке. */
Похоже на установление соответствия для скобок?
public static String stripEnds(String t) { if (t.length() <= 2) return null;
//этовырожденныйтег
return t.substring(1,t.length()-1);
} |
проверка,явлияется |
аключенная втегистрока |
/** |
||
пустойилиэтооткрывающийтег |
. */ |
|
public static boolean isOpeningTag(String tag){ return (tag.length() == 0) || (tag.charAt(0) != '/');
}
37 online.mirea.ru
Центрдистанционногообучения
Алгоритм сопоставления тегов(4/2)
/** проверка,еслитегу |
tag1 соотвезакрывающийтегствует |
tag2 (первыйсимволунего |
'/'). */ |
public static boolean areMatchingTags(String tag1, String tag2) {// провимпосленирка '/'
return tag1.equals(tag2.substring(1));
} |
|
/**проверканато,чтокаждыйоткрывающийтегимеет |
. */ |
соответстзакрывающийтег у |
public static boolean isHTMLMatched(String[] tag) { Stack<String> S = new NodeStack<String>();
// стекдлясоотеговветствия
for (int i = 0; (i < tag.length) && (tag[i] != null); i++)
{ |
; то push егов стек |
//открывающийтег |
if (isOpeningTag(tag[i])) S.push(tag[i]); else { if (S.isEmpty()) return false;
// ничнесоответствуетго
if (!areMatchingTags(S.pop(), tag[i])) return false; //неправильноесоответствие
}
}
38 online.mirea.ru
Центрдистанционногообучения
Алгоритм сопоставления тегов(4/3)
if (S.isEmpty()) return true; //мывсравнилие
// унасетегить,которыенигднесовпали return false;
}
public final static int CAPACITY = 1000;
// размермассиватегов |
html тегов */ |
/* Распарсим HTML документвмассив |
|
public static String[] parseHTML(Scanner s) { |
|
//нашмассивтеговизначально( |
null) |
String[] tag = new String[CAPACITY]; |
|
int count = 0; // счетчиктегов |
scanners |
String token; // токен,возвращаемый |
|
39 online.mirea.ru
Центрдистанционногообучения
Алгоритм сопоставления тегов(4/4)
while (s.hasNextLine()) { //находимследующийтег
while ((token = s.findInLine("<[^>]*>")) != null) //выделимокончаниекаждоготега
tag[count++] = stripEnds(token); s.nextLine(); //перехокследующейстрокеим
}
return tag; //нашмассиввыя( )теговленных
}
public static void main(String[] args) throws IOException { // тестер
if (isHTMLMatched(parseHTML(new Scanner(System.in))))
System.out.println("The input file is a matched HTML document.");
else System.out.println("The input file is not a matched HTML document.");
}
}
online.mirea.ru