回答編集履歴

スペルミス

2021/12/18 14:16

投稿

jimbe

スコア13357

answer CHANGED Viewed

@@ -212,7 +212,7 @@
             : word.equals("*") || word.equals("/") ? Priority.HIGH
             : Priority.LOW;
   }
-  void setPriotiry(Priority priority) { this.priority = priority; }
+  void setPriority(Priority priority) { this.priority = priority; }
   /**
    * 自分のほうが優先順位が高いと true
    */
@@ -271,7 +271,7 @@
       return true;
     }
     if(token.equals(")")) {
-      root.setPriotiry(Node.Priority.NUMBER); //括弧部分は数値の優先度
+      root.setPriority(Node.Priority.NUMBER); //括弧部分は数値の優先度
       root = setNumberNode(stack.pop(), root);
       return true;
     }

若干最適化

2021/12/18 14:16

投稿

jimbe

スコア13357

answer CHANGED Viewed

@@ -271,9 +271,8 @@
       return true;
     }
     if(token.equals(")")) {
-      Node old = stack.pop();
       root.setPriotiry(Node.Priority.NUMBER); //括弧部分は数値の優先度
-      if(old != null) root = setNumberNode(old, root);
+      root = setNumberNode(stack.pop(), root);
       return true;
     }
     return false;

コード追加

2021/12/18 13:33

投稿

jimbe

スコア13357

answer CHANGED Viewed

@@ -179,4 +179,152 @@
    L:'1'
      R:null
      L:null
+```
+----
+括弧を処理できるようにして BinaryTree を (FormulaBinaryTree) オブジェクトとして復活させると以下の風になりました。
+```java
+package teratail_java.q374212;
+import java.util.*;
+import java.util.regex.Pattern;
+class Node {
+  public static enum Priority {
+    LOW, HIGH, NUMBER;
+    boolean over(Priority other) { return ordinal() > other.ordinal(); }
+  }
+  private static final Pattern NUM_PATTERN = Pattern.compile("[0123456789]+");
+  final String word;
+  Node right, left;
+  final boolean isNumber;
+  private Priority priority;
+  Node(String word) {
+    this(word, null, null);
+  }
+  Node(String word, Node left, Node right) {
+    this.word = word;
+    this.left = left;
+    this.right = right;
+    isNumber = NUM_PATTERN.matcher(word).matches();
+    priority = isNumber ? Priority.NUMBER
+            : word.equals("*") || word.equals("/") ? Priority.HIGH
+            : Priority.LOW;
+  }
+  void setPriotiry(Priority priority) { this.priority = priority; }
+  /**
+   * 自分のほうが優先順位が高いと true
+   */
+  boolean isPrioritize(Node other) { return priority.over(other.priority); }
+  void print() { print(""); }
+  void print(String indent) {
+    System.out.println("'"+word+"'");
+    printLink(indent, " R:", right);
+    printLink(indent, " L:", left);
+  }
+  private void printLink(String indent, String label, Node link) {
+    System.out.print(indent+label);
+    if(link == null) System.out.println("null");
+    else link.print(indent+"  ");
+  }
+}
+class FormulaBinaryTree {
+  private Node root = null;
+  FormulaBinaryTree(String[] tokens) {
+    Deque<Node> stack = new LinkedList<>(); //null が入れられる必要がある為 ArrayDeque は不可
+    for(String token : tokens) {
+      if(doBrackets(token, stack)) continue;
+      Node node = new Node(token);
+      if(node.isNumber) {
+        root = setNumberNode(root, node);
+      } else if(node.isPrioritize(root)) { //演算子優先順位による入れ替え
+        node.left = root.right;
+        root.right = node;
+      } else {
+        node.left = root;
+        root = node;
+      }
+    }
+  }
+  private Node setNumberNode(Node root, Node node) {
+    if(root == null) return node; //(1つ目は数字のはず)
+    //右端へ
+    Node t = root;
+    while(t.right != null) t = t.right;
+    t.right = node;
+    return root;
+  }
+  /**
+   * 括弧処理
+   * こっそり括弧内を別ツリーとして生成を続けさせ、閉じ括弧で元のツリーに合成する
+   */
+  private boolean doBrackets(String token, Deque<Node> stack) {
+    if(token.equals("(")) {
+      stack.push(root);
+      root = null;
+      return true;
+    }
+    if(token.equals(")")) {
+      Node old = stack.pop();
+      root.setPriotiry(Node.Priority.NUMBER); //括弧部分は数値の優先度
+      if(old != null) root = setNumberNode(old, root);
+      return true;
+    }
+    return false;
+  }
+  //構造確認用
+  void print() {
+    System.out.print("root:");
+    root.print();
+  }
+}
+public class Step3 {
+  public static void main(String[] args){
+    String[] textm = input();//命令文入力
+    //中置記法を二分木にする
+    FormulaBinaryTree fbt = new FormulaBinaryTree(textm);
+    //確認
+    fbt.print();
+  }
+  private static String[] input() {
+    System.out.print("命令文入力:");
+    try(Scanner scan = new Scanner(System.in);) { //標準入力読み込み
+      String line = scan.nextLine();
+      return line.split(" ");//空白区切り
+    }
+  }
+}
+```
+```plain
+命令文入力:( 1 + ( 2 - 3 * 4 ) ) / 5
+root:'/'
+ R:'5'
+   R:null
+   L:null
+ L:'+'
+   R:'-'
+     R:'*'
+       R:'4'
+         R:null
+         L:null
+       L:'3'
+         R:null
+         L:null
+     L:'2'
+       R:null
+       L:null
+   L:'1'
+     R:null
+     L:null
 ```