//https://stackoverflow.com/questions/1102891/how-to-check-if-a-string-is-numeric-in-java/29331473
//https://gist.github.com/Gaurav-Jayswal/9228965
//https://www.101computing.net/reverse-polish-notation/
//https://www.tabnine.com/code/java/methods/net.sf.saxon.dom.DOMNodeList/%3Cinit%3E

import java.util.*;

public class Tnode {

   private String name;
   private Tnode firstChild;
   private Tnode nextSibling;

   private static boolean isDigit(Tnode node) { //https://stackoverflow.com/questions/1102891/how-to-check-if-a-string-is-numeric-in-java/29331473
      try {
         Integer.parseInt(node.name); //Возвращает true, если все символы в строке являются цифрами и есть хотя бы один символ, иначе false.
         return true;
      } catch (RuntimeException e) {
         return false;
      }
   }

   private static List<Tnode> newList(List<String> stringList) { //https://www.tabnine.com/code/java/methods/net.sf.saxon.dom.DOMNodeList/%3Cinit%3E
      List<Tnode> tList = new ArrayList<>(); //Создает пустой список для узлов дерева.
      for (String str : stringList) { //Для каждой строки из параметра stringList создает узел дерева с текстом из этой строки и помещает созданный узел в список узлов.
         tList.add(new Tnode(str, null, null));
      }
      return tList; //Возвращает полученный список узлов в качестве результата туда, где метод был вызван.
   }


   private static List<Tnode> expressions(String pol) {

      List<String> symbolList = Arrays.asList(pol.split(" "));
      List<Tnode> tList = newList(symbolList);

      if (tList.size() == 1 && !isDigit(tList.get(0))) {
         throw new RuntimeException(String.format("Invalid %s symbol ", pol));
      }

      for (Tnode tnode : tList) {
         if (!isDigit(tnode) && !isSymbol(tnode)) {
            throw new RuntimeException(String.format("Statement %s has invalid symbol ", pol));
         }
      }
      return tList;
   }


   @Override
   public String toString() {
      StringBuffer b = new StringBuffer();
      List<Tnode> usedList = new ArrayList<>();
      Tnode current = this;

      do {
         if (!usedList.contains(current)) {
            b.append(current.getName());
            usedList.add(current);
         }

         Tnode child = current.getFirstChild();
         Tnode sibling = current.getNextSibling();

         if (child != null) {
            if (child.getNextSibling() != null || child.getFirstChild() != null) {
               current = current.getFirstChild();
            } else {
               current.setFirstChild(null);
               current = this;
            }
            if (!usedList.contains(current)) {
               b.append("(");
            }
         } else if (null != sibling) {
            if (sibling.getFirstChild() != null) {
               current = current.getNextSibling();
            } else {
               current.setNextSibling(null);
               if (!usedList.contains(sibling)) b.append(",").append(sibling.getName());
               current = this;
               b.append(")");
            }
            if (!usedList.contains(current)) {
               b.append(",");
            }
         }
      } while (this.getFirstChild() != null);
      return b.toString();
   }

    private Tnode(String n, Tnode down, Tnode right) {
       name = n;
       firstChild = down;
       nextSibling = right;
    }

   private String getName() {
      return name;
   }

   private Tnode getFirstChild() {
      return firstChild;
   }

   private void setFirstChild(Tnode down) {
      firstChild = down;
   }

   private Tnode getNextSibling() {
      return nextSibling;
   }

   private void setNextSibling(Tnode right) {
      nextSibling = right;
   }

   private static boolean isSymbol(Tnode node) {
      return (Arrays.asList("*", "/", "+", "-").contains(node.name));
   }

   public static Tnode buildFromRPN (String pol) {
      List<Tnode> tList = expressions(pol);
      int counter = 0;

      while (true) {
          if (tList.size() <= 1)
             break;
          if (tList.size() < 3) {
            throw new RuntimeException(String.format("There are not enough elements in the stack to complete %s", pol));
         }
         if (tList.size() > 9) {
            throw new RuntimeException(String.format("There are too much elements in the stack to complete %s", pol));
         }
         if (pol.contains("[!@#$%^&?,.]+")) {
            throw new RuntimeException(String.format("%s contains illegal arguments", pol));
         } else if (pol.contains("( )")) {
            throw new RuntimeException(String.format("empty subtree %s", pol));
         }

         if (isDigit(tList.get(counter)) || tList.get(counter).getFirstChild() != null) {
            if (isDigit(tList.get(counter + 1)) || tList.get(counter + 1).getFirstChild() != null) {
               if (!isDigit(tList.get(counter + 2)) && tList.get(counter + 2).getFirstChild() == null) {
                  Tnode top = tList.get(counter + 2);
                  Tnode left = tList.get(counter);
                  Tnode right = tList.get(counter + 1);
                  left.setNextSibling(right);
                  top.setFirstChild(left);
                  tList.remove(counter + 1);
                  tList.remove(counter);
                  counter = 0;
                  continue;
               }
            }
         }
         counter = counter + 1;
      }
      return tList.get(0);
   }



   public static void main (String[] param) {
      String rpn = "1 2 +";
      System.out.println ("RPN: " + rpn);
      Tnode res = buildFromRPN (rpn);
      System.out.println ("Tree: " + res);
   }
}