1 问题描述

匪警请拨110,即使手机欠费也可拨通！

为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！

某批警察叔叔正在进行智力训练：

1 2 3 4 5 6 7 8 9 = 110;

请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法；123+4+5+67-89 是另一个可能的答案。

请你利用计算机的优势，帮助警察叔叔快速找到所有答案。

每个答案占一行。形如：

12+34+56+7-8+9

123+4+5+67-89

......

已知的两个答案可以输出，但不计分。

各个答案的前后顺序不重要。

注意：

请仔细调试！您的程序只有能运行出正确结果的时候才有机会得分！

请把所有类写在同一个文件中，调试好后，存入与【考生文件夹】下对应题号的“解答.txt”中即可。

2 解决方案

1 import java.util.Stack; 2  3 public class Main { 4     public static char[] operation = {' ', '+', '-' }; 5      6     public void check(char[] A) { 7         StringBuffer s = new StringBuffer(""); 8         for(int i = 1;i <= 8;i++) { 9             s.append(i);10             if(A[i - 1] != ' ')11                 s.append(A[i - 1]);12         }13         s.append(9);14         String t = s.toString();15         if(t.length() == 9)16             return;17         Stack
     
       r = new Stack
      
       ();18         Stack
       
         o = new Stack
        
         ();19         for(int i = 0;i < t.length();i++) {20             if(t.charAt(i) == '+' || t.charAt(i) == '-') {21                 if(r.size() == 2) {22                     int a1 = r.pop();23                     int b1 = r.pop();24                     char o1 = o.pop();25                     if(o1 == '+')26                         r.push(a1 + b1);27                     else28                         r.push(b1 - a1);29                 }30                 o.push(t.charAt(i));31                 continue;32             }33             int a = 0;34             while(i < t.length() && t.charAt(i) >= '1' && t.charAt(i) <= '9') {35                 a = a * 10 + (t.charAt(i) - '0');36                 i++;37             }38             i--;39             r.push(a);40         }41         int a1 = r.pop();42         int b1 = r.pop();43         char o1 = o.pop();44         if(o1 == '+')45             r.push(a1 + b1);46         else47             r.push(b1 - a1);48         if(r.pop() == 110)49             System.out.println(t);50     }51     52     public void dfs(int step, char[] A) {53         if(step == 8) {54             check(A);55         } else {56             for(int i = 0;i < 3;i++) {57                 A[step] = operation[i];58                 dfs(step + 1, A);59             }60         }61     }62     63     public static void main(String[] args) {64         Main test = new Main();65         char[] A = new char[8];66         test.dfs(0, A);67     }68 }

运行结果：

123+4+5+67-89123+4-5-6-7-8+9123-4+5-6-7+8-9123-4-5+6+7-8-912+34+56+7-8+912+3+45+67-8-912-3+4-5+6+7+891+234-56-78+91+2+34+5+67-8+91-2+3+45-6+78-9

转载于:https://www.cnblogs.com/liuzhen1995/p/6895957.html

你可能感兴趣的文章