import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
class Filogen {
public static void main(String[] args) throws NumberFormatException,
IOException {
int n, t;
String s1, s2;
t = Integer.parseInt(br.readLine());
while (t-- > 0) {
n = Integer.parseInt(br.readLine());
s1 = br.readLine();
s2 = br.readLine();
out.println(compare(s1, s2, n));
}
out.flush();
}
static BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
static PrintWriter out = new PrintWriter(new BufferedWriter(
new OutputStreamWriter(System.out)));
public static String compare(String s1, String s2, int n) {
if (s1.length() != s2.length()) return "NIE";
ArrayList
ar1 = new ArrayList(), ar2 = new ArrayList();
String s = "";
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) == '(') {
if (s != "")
ar1.add(Integer.parseInt(s));
ar1.add(10001);
s = "";
}
else if (s1.charAt(i) == ')') {
if (s != "")
ar1.add(Integer.parseInt(s));
ar1.add(10002);
s = "";
}
else if (s1.charAt(i) == ' ') {
if (s != "")
ar1.add(Integer.parseInt(s));
s = "";
}
else s += s1.charAt(i);
}
for (int i = 0; i < s2.length(); i++) {
if (s2.charAt(i) == '(') {
if (s != "")
ar2.add(Integer.parseInt(s));
ar2.add(10001);
s = "";
}
else if (s2.charAt(i) == ')') {
if (s != "")
ar2.add(Integer.parseInt(s));
ar2.add(10002);
s = "";
}
else if (s2.charAt(i) == ' ') {
if (s != "")
ar2.add(Integer.parseInt(s));
s = "";
}
else s += s2.charAt(i);
}
int[] h1 = new int[n + 1], h2 = new int[n + 1];
int height = 0;
for (int i = 0; i < ar1.size(); i++) {
if (ar1.get(i) == 10001)
height++;
else if (ar1.get(i) == 10002)
height--;
else
h1[ar1.get(i)] = height;
}
height = 0;
for (int i = 0; i < ar2.size(); i++) {
if (ar2.get(i) == 10001)
height++;
else if (ar2.get(i) == 10002)
height--;
else
h2[ar2.get(i)] = height;
}
for (int i = 0; i <= n; i++)
if (h1[i] != h2[i])
return "NIE";
int[] pair = new int[n + 1];
for (int i = 0; i < ar1.size(); i++) {
if (ar1.get(i) == 10001 && ar1.get(i + 3) == 10002) {
if (ar1.get(i + 1) < ar1.get(i + 2))
pair[ar1.get(i + 1)] = ar1.get(i + 2);
else
pair[ar1.get(i + 2)] = ar1.get(i + 1);
}
}
for (int i = 0; i < ar2.size(); i++) {
if (ar2.get(i) == 10001 && ar2.get(i + 3) == 10002) {
if (ar2.get(i + 1) < ar2.get(i + 2)) {
if (pair[ar2.get(i + 1)] != ar2.get(i + 2))
return "NIE";
} else {
if (pair[ar2.get(i + 2)] != ar2.get(i + 1)) {
return "NIE";
}
}
}
}
return "TAK";
}
}
Wyszukiwarka
Podobne podstrony:
AiSD w4 sortowanie2
AiSD Liczby Pierwsze
W9 Bezpieczne nastawy dla typowych obiektów AiSD
AiSD wyklad 2
Rozwój filogenetyczny i ontogenetyczny
AiSD Travelling Salesman Again !
AiSD Problem Collatza
AiSD wyklad 7
AiSD Wyklad5 dzienne
AiSD lista 7, zadanie 4
AiSD Longest path in a tree
26 Spalik, Piwczynski, Rekonstrukcja filogenezy i wnioskowanie filogenetyczne w badaniach ewolucyjn
Tworzenie drzew filogenetycznych
AiSD zestaw zad4
pytania z analizy filogenetycznej (1)egzamin
filogenetyka
AiSD Wyklad9 dzienne
AiSD Dictionary Subsequences
więcej podobnych podstron