class Rational {
public int num;
public int den;
Rational(int a, int b) { num = a; den = b; }
Rational add(Rational val) {
return reduce (new Rational(this.num * val.den + this.den * val.num, this.den * val.den));
}
Rational subtract(Rational val) {
return reduce(new Rational(this.num * val.den - this.den * val.num, this.den * val.den));
}
Rational multiply(Rational val) {
return reduce(new Rational(this.num * val.num, this.den * val.den));
}
Rational divide(Rational val) {
return reduce(new Rational(this.num * val.den, this.den * val.num));
}
boolean isZero() {
if (this.num == 0 && this.den != 0)
return true;
if (this.den == 0) {
System.
err.
println("denomination is zero !!(1)"); }
return false;
}
boolean equal(Rational val) {
if (this.subtract(val).isZero())
return true;
return false;
}
private static Rational reduce(Rational val) {
if (val.den == 0) {
System.
err.
println("denomination is zero !!(2)"); }
if (val.num == 0)
return new Rational(0, 1);
int n = gcd(val.num, val.den);
return new Rational(val.num / n, val.den / n);
}
private static int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
return "(" + this.num + "/" + this.den + ")";
}
}
class Check {
final static int TARGET_NUM = 100;
final static int stacksize = 16;
Rational[] numStack;
int[] opStack;
Rational[] numStack2;
int[] opStack2;
Rational[] numStack3;
int[] opStack3;
int numStackPoint, opStackPoint, numStack2Point, opStack2Point, numStack3Point, opStack3Point;
Check() {
numStack = new Rational[stacksize];
opStack = new int[stacksize];
numStack2 = new Rational[stacksize];
opStack2 = new int[stacksize];
numStack3 = new Rational[stacksize];
opStack3 = new int[stacksize];
}
void CheckAndOutput(int[] seed) {
boolean minusstartflag = false;
numStackPoint = opStackPoint = numStack2Point = opStack2Point = numStack3Point = opStack3Point = 0;
numStack[numStackPoint++] = new Rational(0, 1);
/* step 1 */
for (int i = 0; i < 9; i++) {
switch (seed[i]) {
case 0: /* concat */
Rational t = numStack[--numStackPoint];
if (!minusstartflag)
/* t * 10 + (i + 1); */
numStack[numStackPoint++] = t.multiply(new Rational(10, 1)).add(new Rational(i, 1)).add(new Rational(1, 1));
else
/* t * 10 - (i + 1); */
numStack[numStackPoint++] = t.multiply(new Rational(10, 1)).subtract(new Rational(i, 1)).subtract(new Rational(1, 1));
break;
case 1: /* + */
opStack2[opStack2Point++] = opStack[opStackPoint++] = 1;
numStack2[numStack2Point++] = numStack[numStackPoint - 1];
/* i + 1 */
numStack[numStackPoint++] = new Rational(i + 1, 1);
minusstartflag = false;
break;
case 2: /* - */
if (i == 0) {
minusstartflag = true;
numStack[numStackPoint - 1] = new Rational(-1, 1);
} else {
opStack2[opStack2Point++] = opStack[opStackPoint++] = 2;
numStack2[numStack2Point++] = numStack[numStackPoint - 1];
numStack[numStackPoint++] = new Rational(i + 1, 1);
minusstartflag = false;
}
break;
case 3: /* * */
opStack2[opStack2Point++] = opStack[opStackPoint++] = 3;
numStack2[numStack2Point++] = numStack[numStackPoint - 1];
numStack[numStackPoint++] = new Rational(i + 1, 1);
minusstartflag = false;
break;
case 4: /* / */
opStack2[opStack2Point++] = opStack[opStackPoint++] = 4;
numStack2[numStack2Point++] = numStack[numStackPoint - 1];
numStack[numStackPoint++] = new Rational(i + 1, 1);
minusstartflag = false;
}
} /* for */
numStack2[numStack2Point++] = numStack[numStackPoint - 1];
ReverseStack(numStack, numStackPoint);
ReverseStack(opStack, opStackPoint);
/* step 2a */
while (opStackPoint > 0) {
switch (opStack[--opStackPoint]) {
case 3: /* * */
Rational t1 = numStack[--numStackPoint];
Rational t2 = numStack[--numStackPoint];
numStack[numStackPoint++] = t1.multiply(t2);
break;
case 4: /* / */
t1 = numStack[--numStackPoint];
t2 = numStack[--numStackPoint];
if (t1.isZero()) return;
numStack[numStackPoint++] = t1.divide(t2);
break;
case 1: /* + */
numStack3[numStack3Point++] = numStack[--numStackPoint];
opStack3[opStack3Point++] = opStack[opStackPoint];
break;
case 2: /* - */
numStack3[numStack3Point++] = numStack[--numStackPoint];
opStack3[opStack3Point++] = opStack[opStackPoint];
break;
}
} /* while */
numStack3[numStack3Point++] = numStack[--numStackPoint];
ReverseStack(numStack3, numStack3Point);
ReverseStack(opStack3, opStack3Point);
/* step 2b */
while (opStack3Point > 0) {
switch (opStack3[--opStack3Point]) {
case 1: /* + */
Rational t1 = numStack3[--numStack3Point];
Rational t2 = numStack3[--numStack3Point];
numStack3[numStack3Point++] = t1.add(t2);
break;
case 2: /* - */
t1 = numStack3[--numStack3Point];
t2 = numStack3[--numStack3Point];
numStack3[numStack3Point++] = t1.subtract(t2);
break;
}
}
Rational answer = numStack3[0];
/* step 3 */
if (answer.equal(new Rational(TARGET_NUM, 1))) {
int num_sp = 0, op_sp = 0;
if (minusstartflag) {
op_sp++;
}
while (num_sp < numStack2Point) {
System.
out.
print(numStack2
[num_sp
++].
num); if (op_sp < opStack2Point)
switch (opStack2[op_sp++]) {
case 1:
case 2:
case 3:
case 4:
}
} /* while */
System.
out.
println(" = " + TARGET_NUM
); } /* if TARGET_NUM */
} /* method */
static void ReverseStack(Rational[] array, int n) { for (int i = 0; i < n - i - 1; i++) myswap(array, i, n - i - 1); }
static void ReverseStack(int[] array, int n) { for (int i = 0; i < n - i - 1; i++) myswap(array, i, n - i - 1); }
static void myswap(Rational[] array, int a, int b) { Rational t; t = array[a]; array[a] = array[b]; array[b] = t; }
static void myswap(int[] array, int a, int b) { int t; t = array[a]; array[a] = array[b]; array[b] = t; }
}
class Main {
public static void main
(String[] args
) { Factory factory = new Factory();
int[] seed;
Check check = new Check();
while (factory.getSeed(seed = new int[9])) {
check.CheckAndOutput(seed);
}
}
}
class Factory {
static int[] seed;
boolean stopflag;
Factory() {
seed = new int[9];
stopflag = false;
for (int i = 0; i < 9; i++) seed[i] = 0;
}
private boolean next() {
int idx = 8;
if (stopflag)
return !stopflag;
do {
boolean cy = false;
if (seed[idx]++ >= 4) {
seed[idx] = 0;
cy = true;
}
while (idx > 0 ) {
--idx;
if (cy == true)
if (seed[idx]++ >= 4) {
seed[idx] = 0;
cy = true;
} else {
cy = false;
}
}
if (cy == true)
stopflag = true;
} while (seed[0] != 0 && seed[0] != 2);
return !stopflag;
}
public boolean getSeed(int[] seed) {
boolean flag;
flag = this.next();
for (int i = 0; i < 9; i++)
seed[i] = this.seed[i];
return flag;
}
}
/* end */