学步园

游戏的规则很简单：恰好移动一根火柴，使等式成立。如下面的等式可以变成3+6=9（还有其他解）：移动哪一根火柴能使等式成立?

请你写一个程序，找出所有的规范解。所谓规范是指：
    * 只能改变数字，不能改变符号；
    * 数字和符号的组成方式必须严格的和图示的一样（减号由一根火柴组成）；
    * 新等式必须形如a+b=c或a-b=c，其中a、b、c都是不含前导0的非负整数。
当然，最重要的是：新的等式必须在数学上成立。

实现代码：

 import java.io.BufferedReader;<br /> import java.io.InputStreamReader;<br /> import java.util.ArrayList;<br /> import java.util.List;</p> <p>public class MoveMatch {<br /> /* _ _ _ _ _<br /> * | |<br /> * | 5 |<br /> * | 2 7 |<br /> * | 4 |<br /> * |_ _ _ _ _| 火柴对应的位置<br /> * | |<br /> * | |<br /> * | 1 6 |<br /> * | 3 |<br /> * |_ _ _ _ _|<br /> *<br /> *<br /> * _ _ _ _ _<br /> * |<br /> * 5(1) |<br /> * 2(0) 7(1)|<br /> * 4(1 ) |<br /> * _ _ _ _ _| 01011101<br /> * |<br /> * |<br /> * | 1(1) 6(0)<br /> * | 3(1)<br /> * |_ _ _ _ _<br /> * 标识位 1位 2位 3位 4 位 5位 6位 7位<br /> */<br /> // 所有数字和运算符用八位0和1表示,没8位中首位为0表示数字,首位是1表示操作符,<br /> // 对于数字对应火柴位置如上图,如果火柴存在则对应的二进制位为1,否则为0.通过移动1和0来实现移动火柴<br /> String[] allNumbers = { "01110111",// 0<br /> "00000011",// 1<br /> "01011101",// 2<br /> "00011111",// 3<br /> "00101011",// 4<br /> "00111110",// 5<br /> "01111110",// 6<br /> "00000111",// 7<br /> "01111111",// 8<br /> "00111111",// 9<br /> };<br /> String[] operator = { "11000000",// +<br /> "10000000",// -<br /> "11100000",// =<br /> };<br /> String[] operatorChar = { "+",// +<br /> "-",// -<br /> "=",// =<br /> };</p> <p> // 判断8为二进制字符串是否表示数字<br /> public boolean isDigit(String s) {</p> <p> if (s.startsWith("0")) {<br /> for (int i = 0; i < allNumbers.length; i++) {<br /> if (s.equals(allNumbers[i])) {<br /> return true;<br /> }<br /> }<br /> }<br /> return false;<br /> }</p> <p> // 判断8为二进制字符串是否表示运算符号<br /> public boolean isOperator(String s) {<br /> return s.startsWith("1");<br /> }</p> <p> // 8为二进制字符串转为数字<br /> public int translate2Digit(String s) {<br /> try {<br /> if (isDigit(s)) {<br /> for (int i = 0; i < allNumbers.length; i++) {<br /> if (s.equals(allNumbers[i])) {<br /> return i;</p> <p> }<br /> }<br /> } else {<br /> throw new NumberFormatException();<br /> }</p> <p> } catch (Exception e) {<br /> e.printStackTrace();<br /> }</p> <p> return -1;</p> <p> }</p> <p> // 8为二进制字符串转为字符<br /> public String translate2operator(String s) {<br /> try {<br /> if (isOperator(s)) {<br /> for (int i = 0; i < operator.length; i++) {<br /> if (s.equals(operator[i])) {<br /> return operatorChar[i];</p> <p> }<br /> }<br /> } else {<br /> throw new IsNotOperatorException();<br /> }</p> <p> } catch (Exception e) {<br /> e.printStackTrace();<br /> }</p> <p> return "";</p> <p> }</p> <p> // 判断某个数字对应index位置上的火柴是否可以移动<br /> public boolean isMoveable(String s, int index) {<br /> if (!isDigit(s))<br /> return false;<br /> String temp = s.intern();<br /> char c = temp.charAt(index);<br /> if (c == '1') {<br /> temp = temp.substring(0, index) + "0" + temp.substring(index + 1);<br /> return isDigit(temp);<br /> }<br /> return false;<br /> }</p> <p> // 判断某个数字的位置上受否可以接受一根火柴<br /> public boolean isAcceptable(String s, int index) {<br /> if (!isDigit(s))<br /> return false;<br /> String temp = s.intern();<br /> char c = temp.charAt(index);<br /> if (c == '0') {<br /> temp = temp.substring(0, index) + "1" + temp.substring(index + 1);<br /> return isDigit(temp);<br /> }<br /> return false;<br /> }</p> <p> // 半段某个数字是否可以把indx位上的火柴移动到indexto上<br /> public boolean isSelfAcceptable(String s, int index, int indexto) {<br /> if (!isDigit(s))<br /> return false;<br /> String temp = s.intern();<br /> char c = temp.charAt(index);<br /> char c2 = temp.charAt(indexto);<br /> if (c == '1') {<br /> temp = temp.substring(0, index) + "0" + temp.substring(index + 1);<br /> if (c2 == '0') {<br /> temp = temp.substring(0, indexto) + "1"<br /> + temp.substring(indexto + 1);<br /> return isDigit(temp);<br /> }<br /> }</p> <p> return false;<br /> }</p> <p> public void calculate(String string) {<br /> int result = -1;<br /> int length = string.length();<br /> int count = length / 8;<br /> // 循环移动可以移动的火柴<br /> for (int i = 0; i < count; i++) {<br /> String source = string.substring(i * 8, (i + 1) * 8);<br /> if (isDigit(source)) {<br /> // 循环所有火柴位移动火柴<br /> for (int j = 1; j < 8; j++) {<br /> // 判断j位上的火柴是否可以移动<br /> if (isMoveable(source, j)) {<br /> // 循环多有可以接受火柴的数<br /> for (int k = 0; k < count; k++) {<br /> String target = string<br /> .substring(k * 8, (k + 1) * 8);<br /> // 判断是否为数字<br /> if (isDigit(target)) {<br /> // 接受火柴和移动火柴是否同时在同一个数字上<br /> if (k == i) {<br /> // 循环所有的火柴位<br /> for (int l = 1; l < 8; l++) {<br /> // 是否可以接受<br /> if (l != j<br /> && isSelfAcceptable(target, j,<br /> l)) {<br /> String temp = string.intern();<br /> int indexMove = i * 8 + j;<br /> int indexto = k * 8 + j;<br /> // 生成新的字符串<br /> temp = temp.substring(0, indexMove)<br /> + "0"<br /> + temp<br /> .substring(indexMove + 1);<br /> temp = temp.substring(0, indexto)<br /> + "1"<br /> + temp<br /> .substring(indexto + 1);<br /> if (print(temp) == 0)<br /> result = 0;</p> <p> }<br /> }<br /> } else {<br /> // 循环所有的火柴位<br /> for (int l = 1; l < 8; l++) {<br /> // 判断时候可以接受火柴<br /> if (isAcceptable(target, l)) {<br /> String temp = string.intern();<br /> int indexMove = i * 8 + j;<br /> int indexto = k * 8 + l;<br /> // 生成新的结果<br /> temp = temp.substring(0, indexMove)<br /> + "0"<br /> + temp<br /> .substring(indexMove + 1);<br /> temp = temp.substring(0, indexto)<br /> + "1"<br /> + temp<br /> .substring(indexto + 1);<br /> if (print(temp) == 0)<br /> result = 0;<br /> }<br /> }</p> <p> }<br /> }</p> <p> }</p> <p> }<br /> }<br /> }</p> <p> }<br /> if (result == -1)<br /> System.out.println(-1);<br /> }</p> <p> @SuppressWarnings("serial")<br /> class IsNotOperatorException extends Exception {<br /> }</p> <p> // 打印结果<br /> @SuppressWarnings("unchecked")<br /> public int print(String s) {<br /> List list = new ArrayList();<br /> int length = s.length();<br /> int count = length / 8;<br /> long result = 0;<br /> @SuppressWarnings("unused")<br /> long param = 0;<br /> String digits = "";<br /> String opreator = "";<br /> String tempOperator = "";<br /> // 生成计算表达式<br /> for (int i = 0; i < count; i++) {<br /> String source = s.substring(i * 8, (i + 1) * 8);<br /> if (isDigit(source)) {<br /> digits += translate2Digit(source);<br /> // 把操作数加入队列</p> <p> if (!opreator.equals("")) {<br /> list.add(new String(opreator));<br /> }<br /> opreator = "";</p> <p> } else {</p> <p> if (digits.length() > 0 && digits.startsWith("0")) {<br /> return -1;<br /> }<br /> // 计算结果<br /> if (tempOperator.equals("")) {<br /> result = Long.valueOf(digits).longValue();<br /> }<br /> if (tempOperator.endsWith("+")) {<br /> result += Long.valueOf(digits).longValue();<br /> }<br /> if (tempOperator.endsWith("-")) {<br /> result -= Long.valueOf(digits).longValue();<br /> }<br /> opreator = translate2operator(source);<br /> tempOperator = opreator;<br /> list.add(new String(digits));<br /> digits = "";<br /> }<br /> }<br /> list.add(digits);<br /> if (digits.length() > 0 && digits.startsWith("0")) {<br /> return -1;<br /> }</p> <p> if (result == Long.valueOf(digits).longValue()) {<br /> // 输出表达式<br /> for (int i = 0; i < list.size(); i++) {<br /> System.out.print(list.get(i));</p> <p> }<br /> System.out.println();<br /> return 0;<br /> }<br /> return -1;<br /> }</p> <p> public static void main(String[] args) throws Exception {<br /> MoveMatch test = new MoveMatch();<br /> BufferedReader br = new BufferedReader(new InputStreamReader(System.in));<br /> String str = null;<br /> System.out.println("Enter your value:");<br /> str = br.readLine();<br /> StringBuffer sb = new StringBuffer(800);<br /> for (int i = 0; i < str.length(); i++) {<br /> char c = str.charAt(i);<br /> if (Character.isDigit(c)) {<br /> sb.append(test.allNumbers[Integer.valueOf(c + "").intValue()]);<br /> } else {<br /> if (c == '+') {<br /> sb.append(test.operator[0]);<br /> } else if (c == '-') {<br /> sb.append(test.operator[1]);<br /> } else if (c == '=') {<br /> sb.append(test.operator[2]);<br /> } else {<br /> throw new Exception();<br /> }<br /> }</p> <p> }<br /> test.calculate(sb.toString());<br /> }<br /> }<br />

输入：9+5=9

输出：3+5=8

          3+6=9