Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //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;
- @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 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) {
- tList.add(new Tnode(str, null, null));
- }
- return tList;
- }
- private static boolean isSymbol(Tnode node) {
- return (Arrays.asList("*", "/", "+", "-").contains(node.name));
- }
- private static List<Tnode> correctExpression(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("Invalid symbol");
- }
- for (Tnode tnode : tList) {
- if (!isDigit(tnode) && !isSymbol(tnode)) {
- throw new RuntimeException("Statement has invalid symbol");
- }
- }
- return tList;
- }
- public static Tnode buildFromRPN (String pol) {
- List<Tnode> tList = correctExpression(pol);
- int counter = 0;
- while (tList.size() > 1) {
- if (tList.size() < 3) {
- throw new RuntimeException("Few invoices in statement");
- }
- 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++;
- }
- 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);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement