java 逆ポーランド記法への変換のための２分木作成

Question

逆ポーランド記法への変換のために２分木を作成したい

中置記法を逆ポーランド記法に変換するために中置記法を２分木に入れ後順で読んでいきたいのですが、
追加された後の根を取得することができないのでその方法を知りたいです。

追記
質問の意図はnullが戻ってきてしまう原因を教えてほしいです。

発生している問題・エラーメッセージ

要素が追加された後の根を取得したい

###実行結果

命令文入力:1 + 2 * 3
text[0] = 1
text[1] = +
text[2] = 2
text[3] = *
text[4] = 3
text[0+1]= +
text[0]= 1
text[2+1]= *
text[2]= 2
text[4]= 3
 null

該当のソースコード

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Data{
    String order;//命令文
    String num;//数値
}

public class Step3{
    public static void main(String[] args){
        Data data[] = new Data[256];

        //標準入力読み込み
        System.out.print("命令文入力:");
        Scanner scan = new Scanner(System.in);
        String line = scan.nextLine();
        String[] textm = line.split(" ");//空白区切り

        //確認
        for(int i=0;i<textm.length;i++){
            System.out.println("text[" + i + "] = " + textm[i]); 
        }

        //中置記法を二分木にする
        CheakNum cn = new CheakNum();//数字か判定
        BinaryTree tree = new BinaryTree();
        Node node = new Node(null,null,null);
        for(int i=0;i<textm.length;i++){

            if(cn.cheaknum(textm[i])){//数字の場合
                if(i == textm.length-1){//最後の場合
                    tree.maketreeRight(node,textm[i]);//右に追加
                    System.out.println("text[" + i + "]= " + textm[i]);
                }else{
                    tree.maketree(node,textm[i+1]);//演算子を追加
                    System.out.println("text[" + i+1 + "]= " + textm[i+1]);
                    tree.maketree(node,textm[i]);//数字を追加
                    System.out.println("text[" + i + "]= " + textm[i]);
                    i++;
                }
            }
        }

        //二分木を後順で読み込む
        List<String> list = new ArrayList<String>();
        list = (Search(node,list));
        
        String[] text = new String[256];
        for(int i=0;i<list.size();i++){
            text[i] = list.get(i);
        }
    }


    public static List<String> Search(Node root, List<String> list){
        if(root != null){
            Search(root.left,list);
            Search(root.right,list);
            list.add(root.word);
            //確認
            System.out.print(" " + root.word);
            System.out.println();
        }
        return list;
    }
    
}


public class BinaryTree{
    public static Node maketree(Node root, String text){
        CheakNum cn = new CheakNum();
        if(root == null){//空の場合
            return new Node(text,null,null);
        }else if(cn.cheaknum(text)){//数字の場合
            maketree(root.left, text);
        }else{
            maketree(root.right, text);
        }
        return root;
    }

    public static Node maketreeRight(Node root, String text){
        if(root == null){
            return new Node(text,null,null);
        }else{
            maketree(root.right, text);
        }
        return root;
    }
}


public class CheakNum{
    public static boolean cheaknum(String word){
        switch(word){
        case "+":
        case "-":
        case "*":
        case "/":
            return false;

        default:
            return true;            
        }
    }
}


//追記
class Node{
    String word;
    Node right;
    Node left;

    Node(String word,Node left,Node right){
        this.word = word;
        this.left = left;
        this.right = right;
    }
}

Comments

[jimbe]

パッと見ですが、 Node クラスがありません。
また、これだけコードを作られた後で「根が…」とはどういう訳でしょう。
処理の開始点である根から処理するようにコードを書くのが本来のはずで、それが分からなくなるコードとは一体どう作られたのでしょうか。

[tamintya]

すみません、Node クラスは載せるのを忘れてしまいました。

「根が…」というのはBinaryTree クラスで値を木に追加しているはずなのにnullが帰ってきてしまう理由を、 return がうまく作動していないのではと考えたので、値が代入され完成した2分木の始まりを取得したいという意味です。

[tamintya]

うまくいかない原因を勝手に決めつけてしまい質問の意図が分かりにくくなってしまっていたので、質問文を追記しました。

[jimbe]

どこで根となる変数に値を設定しているのでしょうか。
Node node = new Node(null,null,null);
の node が根のつもりのようですが、 この代入の他に node に値を設定している個所が見当たりません。

> BinaryTree クラスで値を木に追加しているはず
どの部分のことでしょう。

[tamintya]

指摘ありがとうございます。確かに上のコードでは木に値を追加できてないですね。
まずそこから直してみます。

Answer 1

ざっくりと加減乗除だけ(括弧無し)で、ツリーを作って見ます。

package teratail_java.q374212;

import java.util.Scanner;
import java.util.regex.Pattern;

class Node{
  private static final Pattern NUM_PATTERN = Pattern.compile("[0123456789]+");

  final String word;
  final boolean isNumber;
  Node right;
  Node left;

  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();
  }
  //自分も相手も演算子で、自分のほうが優先順位が高いと true
  boolean isPrioritize(Node other) {
    return (word.equals("*") || word.equals("/")) &&
           (other.word.equals("+") || other.word.equals("-"));
  }
  void print() { print(""); }
  void print(String indent) {
    System.out.println("'"+word+"'");

    System.out.print(indent+" R:");
    if(right == null) System.out.println("null");
    else right.print(indent+"  ");

    System.out.print(indent+" L:");
    if(left == null) System.out.println("null");
    else left.print(indent+"  ");
  }
}

public class Step3{
  public static void main(String[] args){
    String[] textm = input();//命令文入力

    //中置記法を二分木にする
    Node root = null;
    for(int i=0; i<textm.length; i++) {
      Node node = new Node(textm[i], null, null);
      if(node.isNumber) {
        if(root == null) { //(1つ目は数字のはず)
          root = node;
        } else {
          Node t = root;
          while(t.right != null) t = t.right;
          t.right = node;
        }
      } else if(node.isPrioritize(root)) {
        node.left = root.right;
        root.right = node;
      } else {
        node.left = root;
        root = node;
      }
    }

    //確認
    System.out.print("root:");
    root.print();
  }

  private static String[] input() {
    System.out.print("命令文入力:");
    try(Scanner scan = new Scanner(System.in);) { //標準入力読み込み
      String line = scan.nextLine();
      return line.split(" ");//空白区切り
    }
  }
}

実行結果

命令文入力:1
root:'1'
 R:null
 L:null

命令文入力:1 + 2
root:'+'
 R:'2'
   R:null
   L:null
 L:'1'
   R:null
   L:null

命令文入力:1 + 2 + 3
root:'+'
 R:'3'
   R:null
   L:null
 L:'+'
   R:'2'
     R:null
     L:null
   L:'1'
     R:null
     L:null

命令文入力:1 * 2 + 3
root:'+'
 R:'3'
   R:null
   L:null
 L:'*'
   R:'2'
     R:null
     L:null
   L:'1'
     R:null
     L:null

命令文入力:1 + 2 * 3
root:'+'
 R:'*'
   R:'3'
     R:null
     L:null
   L:'2'
     R:null
     L:null
 L:'1'
   R:null
   L:null

命令文入力:1 * 2 + 3 * 4
root:'+'
 R:'*'
   R:'4'
     R:null
     L:null
   L:'3'
     R:null
     L:null
 L:'*'
   R:'2'
     R:null
     L:null
   L:'1'
     R:null
     L:null

命令文入力:1 + 2 * 3 / 4 - 5
root:'-'
 R:'5'
   R:null
   L:null
 L:'+'
   R:'/'
     R:'4'
       R:null
       L:null
     L:'*'
       R:'3'
         R:null
         L:null
       L:'2'
         R:null
         L:null
   L:'1'
     R:null
     L:null

---

括弧を処理できるようにして BinaryTree を (FormulaBinaryTree) オブジェクトとして復活させると以下の風になりました。

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 setPriority(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(")")) {
      root.setPriority(Node.Priority.NUMBER); //括弧部分は数値の優先度
      root = setNumberNode(stack.pop(), 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(" ");//空白区切り
    }
  }
}

命令文入力:( 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

Comments

[tamintya]

回答ありがとうございます。
現在コード修正している途中なので参考にさせてもらいます。

Answer 2

+, -, *, / に優先順位は無いのでしょうか？
また、( ) も無いのでしょうか？

質問のコードをどう修正すればよいか分からなかったので、
新たに書いてみました。

import java.util.Scanner;

class Node {
	String word;
	Node left, right;

	Node(String s, Node l, Node r) { word = s; left = l; right = r; }
}

class Expr {
	private String[] text;
	private int pos;
	private String token;

	Expr(String s) { text = s.split(" "); }

	Node expr() {
		Node node = term();
		while (token.equals("+") || token.equals("-")) {
			String s = token;
			Node right = term();
			node = new Node(s, node, right);
		}
		return node;
	}

	Node term() {
		Node node = factor();
		while (token.equals("*") || token.equals("/")) {
			String s = token;
			Node right = factor();
			node = new Node(s, node, right);
		}
		return node;
	}
	
	Node factor() {
		Node node = null;
		if (get().equals("(")) {
			node = expr();
			token = token.equals(")") ? get() : "x";
		}
		else if (token.isEmpty()) token = "x";
		else { node = new Node(token, null, null); get(); }
		return node;
	}

	String get() { return token = pos < text.length ? text[pos++] : ""; }

	boolean ok() { return token.isEmpty(); }

	void print(Node node) {
		if (node == null) return;
		print(node.left);
		print(node.right);
		System.out.print(node.word + " ");
	}
}

class Main {
    public static void main(String[] args){
        System.out.print("式入力:");
        Scanner scan = new Scanner(System.in);
        String line = scan.nextLine();
		Expr e = new Expr(line);
		Node root = e.expr();
		if (e.ok()) {
			e.print(root);
			System.out.println();
		}
		else System.out.println(" Error");
	}
}

Comments

[tamintya]

回答ありがとうございます。
優先順位や括弧については作ったコードもあるのですが、今回のコードのように値がほとんど表示されなかったので原因を調べるために今回のコードを作ったので省いています。

回答してくださったコードについては確認した後にまた返事をします。

[tamintya]

コードを確認したところ
・Node factor の"x"の意味
・長い式を入力するとErrorになってしまう理由
が分からないです。

[kazuma-s]

"x" は演算子でない文字で、構文解析が終了するようにして、ok() でエラーの発生を検出します。
長い式の具体例を挙げてください。

[tamintya]

説明ありがとうございます。理解することができました。

長い式のErrorはスペースを入れる際に2桁の数字の間にもスペースをいれてしまっていたこちらのミスでした。すみません。