fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.List;
  3.  
  4. public class Komachi {
  5.  
  6.     public static void komachi(int[] lhs, int rhs) {
  7.         if (lhs.length == 0) return;
  8.  
  9.         List<Term> expression = new ArrayList<Term>();
  10.         expression.add(new TermValue(lhs[0]));
  11.         for (int index = 1; index < lhs.length; index++) {
  12.             List<Term> work = new ArrayList<Term>(expression);
  13.             expression.clear();
  14.             for (Term term: work) {
  15.                 List<Term> list = createTerm(term, lhs[index]);
  16.                 expression.addAll(list);
  17.             };
  18.         }
  19.  
  20.         int counter = 1;
  21.         for (Term term: expression) {
  22.             if (term.getValue() == rhs) {
  23.                 System.out.println(counter++ + ": " + term.toString() + " = " + rhs);
  24.             }
  25.         }
  26.     }
  27.     private static List<Term> createTerm(Term lhs, int r) {
  28.         List<Term> result = new ArrayList<Term>();
  29.         Operator[] operators = Operator.values();
  30.         for (int index = 0; index < operators.length; index++) {
  31.             result.add(new TermData(operators[index], lhs, new TermValue(r)));
  32.         }
  33.         return result;
  34.     }
  35.  
  36.  
  37.     public enum Operator {
  38.         None {
  39.             public int getPriority() { return 10; }
  40.             public int operate(int lhs, int rhs) { return lhs * 10 + rhs; }
  41.             public String toString() { return ""; }
  42.         },
  43.         Plus {
  44.             public int getPriority() { return 1; }
  45.             public int operate(int lhs, int rhs) { return lhs + rhs; }
  46.             public String toString() { return "+"; }
  47.         },
  48.         Minus {
  49.             public int getPriority() { return 1; }
  50.             public int operate(int lhs, int rhs) { return lhs - rhs; }
  51.             public String toString() { return "-"; }
  52.         },
  53.         Times {
  54.             public int getPriority() { return 2; }
  55.             public int operate(int lhs, int rhs) { return lhs * rhs; }
  56.             public String toString() { return "*"; }
  57.         };
  58.  
  59.         public abstract int getPriority();
  60.         public abstract int operate(int lhs, int rhs);
  61.     }
  62.     private static interface Term {
  63.         public boolean isOperate();
  64.         public int getValue();
  65.     }
  66.     private static class TermValue implements Term {
  67.         public final int value;
  68.  
  69.         public TermValue(int val) {
  70.             value = val;
  71.         }
  72.         public boolean isOperate() { return false; }
  73.         public int getValue() {
  74.             return value;
  75.         }
  76.         public String toString() { return String.valueOf(value); }
  77.     }
  78.     private static class TermData implements Term {
  79.         public final Operator op;
  80.         public final Term lhs;
  81.         public final Term rhs;
  82.  
  83.         /**
  84.          * 右辺は追加分と考えて、演算子の順序に従ってデータを正規化します。
  85.          */
  86.         public TermData(Operator o, Term l, Term r) {
  87.             Operator operator = o;
  88.             Term lterm = l;
  89.             Term rterm = r;
  90.  
  91.             if (l.isOperate()) {
  92.                 TermData data = (TermData) l;
  93.                 if (operator.getPriority() > data.op.getPriority()) {
  94.                     rterm = new TermData(operator, data.rhs, rterm);
  95.                     lterm = data.lhs;
  96.                     operator = data.op;
  97.                 }
  98.             }
  99.             op = operator;
  100.             lhs = lterm;
  101.             rhs = rterm;
  102.         }
  103.         public boolean isOperate() { return true; }
  104.         public int getValue() {
  105.             return op.operate(lhs.getValue(), rhs.getValue());
  106.         }
  107.         public String toString() {
  108.             return lhs.toString() + op.toString() + rhs.toString();
  109.         }
  110.     }
  111.  
  112.     public static void main(String[] args) {
  113.         long start = System.currentTimeMillis();
  114.         komachi(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}, 100);
  115.         System.out.println();
  116.         long end = System.currentTimeMillis();
  117.         System.out.println("elipse: " + (end - start) + "(ms)");
  118.     }
  119. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2HYH9
language:
Java (12.0.1)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!