<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu
************************************************/

import java.io.*;
import java.util.*;

public class P06QuadTree {
  private static final String FileInputName = "quad.in";

  private static final String FileOutputName = "quad.out";

  private StringBuilder unifiedTree;

  P06QuadTree() {
    this.unifiedTree = new StringBuilder();
  }

  private static boolean isLeaf(char c) {
    return 'e' == c || 'f' == c;
  }

  public void unifyTrees(StringBuilder t1, StringBuilder t2) {
    if ('p' == t1.charAt(0) &amp;&amp; 'p' == t2.charAt(0)) {
      this.unifiedTree.append('p');
      int i1 = 1, i2 = 1;
      StringBuilder sr1 = new StringBuilder();
      StringBuilder sr2 = new StringBuilder();
      for (int i = 0; i &lt; 4; i++) {
        i1 = subTree(t1, sr1, i1);
        i2 = subTree(t2, sr2, i2);
        this.unifyTrees(sr1, sr2);
      }
      ;
    } else if (t1.charAt(0) == 'f' || t2.charAt(0) == 'f')
      this.unifiedTree.append('f');
    else if ('e' == t2.charAt(0))
      this.unifiedTree.append(t1);
    else if ('e' == t1.charAt(0))
      this.unifiedTree.append(t2);
  }

  private static int subTree(StringBuilder ss, StringBuilder sr, int t) {
    sr.setLength(0);
    if ('p' == ss.charAt(t)) {
      for (int n = 1; n != 0 &amp;&amp; t &lt; ss.length();) {
        if (isLeaf(ss.charAt(t)))
          n--;
        else
          n += 3;
        sr.append(ss.charAt(t++));
      }
    } else {
      sr.append(ss.charAt(t++));
    }
    return t;
  }

  private static int getValue(StringBuilder ss, int v) {
    if ('p' == ss.charAt(0)) {
      StringBuilder sr = new StringBuilder();
      int t = 1;
      int suma = 0;
      for (int i = 0; i &lt; 4; i++) {
        t = subTree(ss, sr, t);
        suma += getValue(sr, v / 4);
      }
      return suma;
    } else
      return 'f' == ss.charAt(0) ? v : 0;
  }

  public static void main(String[] args) throws IOException {
    Scanner sc = null;
    PrintStream out = null;
    try {
      out = new PrintStream(new File(FileOutputName));
      sc = new Scanner(new File(FileInputName));
      while (sc.hasNext()) {
        StringBuilder t1 = new StringBuilder(sc.next());
        if (!sc.hasNext())
          break;
        StringBuilder t2 = new StringBuilder(sc.next());
        P06QuadTree p6 = new P06QuadTree();
        p6.unifyTrees(t1, t2);
        out.printf("%s + %s = %s\n", t1, t2, p6.unifiedTree);
        out.printf("%d + %d = %d\n", getValue(t1, 1024), getValue(t2, 1024),
            getValue(p6.unifiedTree, 1024));
        out.println("-------------------------------------");
      }

    } finally {
      if (sc != null) {
        sc.close();
      }
      if (out != null) {
        out.close();
      }
    }
  }
}
</pre></body></html>