回答編集履歴

3

スペルミス

2021/12/18 14:16

投稿

jimbe
jimbe

スコア13209

test CHANGED
@@ -426,7 +426,7 @@
426
426
 
427
427
  }
428
428
 
429
- void setPriotiry(Priority priority) { this.priority = priority; }
429
+ void setPriority(Priority priority) { this.priority = priority; }
430
430
 
431
431
  /**
432
432
 
@@ -544,7 +544,7 @@
544
544
 
545
545
  if(token.equals(")")) {
546
546
 
547
- root.setPriotiry(Node.Priority.NUMBER); //括弧部分は数値の優先度
547
+ root.setPriority(Node.Priority.NUMBER); //括弧部分は数値の優先度
548
548
 
549
549
  root = setNumberNode(stack.pop(), root);
550
550
 

2

若干最適化

2021/12/18 14:16

投稿

jimbe
jimbe

スコア13209

test CHANGED
@@ -544,11 +544,9 @@
544
544
 
545
545
  if(token.equals(")")) {
546
546
 
547
- Node old = stack.pop();
548
-
549
547
  root.setPriotiry(Node.Priority.NUMBER); //括弧部分は数値の優先度
550
548
 
551
- if(old != null) root = setNumberNode(old, root);
549
+ root = setNumberNode(stack.pop(), root);
552
550
 
553
551
  return true;
554
552
 

1

コード追加

2021/12/18 13:33

投稿

jimbe
jimbe

スコア13209

test CHANGED
@@ -361,3 +361,299 @@
361
361
  L:null
362
362
 
363
363
  ```
364
+
365
+ ----
366
+
367
+ 括弧を処理できるようにして BinaryTree を (FormulaBinaryTree) オブジェクトとして復活させると以下の風になりました。
368
+
369
+ ```java
370
+
371
+ package teratail_java.q374212;
372
+
373
+
374
+
375
+ import java.util.*;
376
+
377
+ import java.util.regex.Pattern;
378
+
379
+
380
+
381
+ class Node {
382
+
383
+ public static enum Priority {
384
+
385
+ LOW, HIGH, NUMBER;
386
+
387
+ boolean over(Priority other) { return ordinal() > other.ordinal(); }
388
+
389
+ }
390
+
391
+ private static final Pattern NUM_PATTERN = Pattern.compile("[0123456789]+");
392
+
393
+
394
+
395
+ final String word;
396
+
397
+ Node right, left;
398
+
399
+ final boolean isNumber;
400
+
401
+ private Priority priority;
402
+
403
+
404
+
405
+ Node(String word) {
406
+
407
+ this(word, null, null);
408
+
409
+ }
410
+
411
+ Node(String word, Node left, Node right) {
412
+
413
+ this.word = word;
414
+
415
+ this.left = left;
416
+
417
+ this.right = right;
418
+
419
+ isNumber = NUM_PATTERN.matcher(word).matches();
420
+
421
+ priority = isNumber ? Priority.NUMBER
422
+
423
+ : word.equals("*") || word.equals("/") ? Priority.HIGH
424
+
425
+ : Priority.LOW;
426
+
427
+ }
428
+
429
+ void setPriotiry(Priority priority) { this.priority = priority; }
430
+
431
+ /**
432
+
433
+ * 自分のほうが優先順位が高いと true
434
+
435
+ */
436
+
437
+ boolean isPrioritize(Node other) { return priority.over(other.priority); }
438
+
439
+
440
+
441
+ void print() { print(""); }
442
+
443
+ void print(String indent) {
444
+
445
+ System.out.println("'"+word+"'");
446
+
447
+ printLink(indent, " R:", right);
448
+
449
+ printLink(indent, " L:", left);
450
+
451
+ }
452
+
453
+ private void printLink(String indent, String label, Node link) {
454
+
455
+ System.out.print(indent+label);
456
+
457
+ if(link == null) System.out.println("null");
458
+
459
+ else link.print(indent+" ");
460
+
461
+ }
462
+
463
+ }
464
+
465
+
466
+
467
+ class FormulaBinaryTree {
468
+
469
+ private Node root = null;
470
+
471
+
472
+
473
+ FormulaBinaryTree(String[] tokens) {
474
+
475
+ Deque<Node> stack = new LinkedList<>(); //null が入れられる必要がある為 ArrayDeque は不可
476
+
477
+ for(String token : tokens) {
478
+
479
+ if(doBrackets(token, stack)) continue;
480
+
481
+
482
+
483
+ Node node = new Node(token);
484
+
485
+ if(node.isNumber) {
486
+
487
+ root = setNumberNode(root, node);
488
+
489
+ } else if(node.isPrioritize(root)) { //演算子優先順位による入れ替え
490
+
491
+ node.left = root.right;
492
+
493
+ root.right = node;
494
+
495
+ } else {
496
+
497
+ node.left = root;
498
+
499
+ root = node;
500
+
501
+ }
502
+
503
+ }
504
+
505
+ }
506
+
507
+
508
+
509
+ private Node setNumberNode(Node root, Node node) {
510
+
511
+ if(root == null) return node; //(1つ目は数字のはず)
512
+
513
+ //右端へ
514
+
515
+ Node t = root;
516
+
517
+ while(t.right != null) t = t.right;
518
+
519
+ t.right = node;
520
+
521
+ return root;
522
+
523
+ }
524
+
525
+ /**
526
+
527
+ * 括弧処理
528
+
529
+ * こっそり括弧内を別ツリーとして生成を続けさせ、閉じ括弧で元のツリーに合成する
530
+
531
+ */
532
+
533
+ private boolean doBrackets(String token, Deque<Node> stack) {
534
+
535
+ if(token.equals("(")) {
536
+
537
+ stack.push(root);
538
+
539
+ root = null;
540
+
541
+ return true;
542
+
543
+ }
544
+
545
+ if(token.equals(")")) {
546
+
547
+ Node old = stack.pop();
548
+
549
+ root.setPriotiry(Node.Priority.NUMBER); //括弧部分は数値の優先度
550
+
551
+ if(old != null) root = setNumberNode(old, root);
552
+
553
+ return true;
554
+
555
+ }
556
+
557
+ return false;
558
+
559
+ }
560
+
561
+
562
+
563
+ //構造確認用
564
+
565
+ void print() {
566
+
567
+ System.out.print("root:");
568
+
569
+ root.print();
570
+
571
+ }
572
+
573
+ }
574
+
575
+
576
+
577
+ public class Step3 {
578
+
579
+ public static void main(String[] args){
580
+
581
+ String[] textm = input();//命令文入力
582
+
583
+
584
+
585
+ //中置記法を二分木にする
586
+
587
+ FormulaBinaryTree fbt = new FormulaBinaryTree(textm);
588
+
589
+
590
+
591
+ //確認
592
+
593
+ fbt.print();
594
+
595
+ }
596
+
597
+
598
+
599
+ private static String[] input() {
600
+
601
+ System.out.print("命令文入力:");
602
+
603
+ try(Scanner scan = new Scanner(System.in);) { //標準入力読み込み
604
+
605
+ String line = scan.nextLine();
606
+
607
+ return line.split(" ");//空白区切り
608
+
609
+ }
610
+
611
+ }
612
+
613
+ }
614
+
615
+ ```
616
+
617
+ ```plain
618
+
619
+ 命令文入力:( 1 + ( 2 - 3 * 4 ) ) / 5
620
+
621
+ root:'/'
622
+
623
+ R:'5'
624
+
625
+ R:null
626
+
627
+ L:null
628
+
629
+ L:'+'
630
+
631
+ R:'-'
632
+
633
+ R:'*'
634
+
635
+ R:'4'
636
+
637
+ R:null
638
+
639
+ L:null
640
+
641
+ L:'3'
642
+
643
+ R:null
644
+
645
+ L:null
646
+
647
+ L:'2'
648
+
649
+ R:null
650
+
651
+ L:null
652
+
653
+ L:'1'
654
+
655
+ R:null
656
+
657
+ L:null
658
+
659
+ ```