需求：写程序在1,2,…,9（保持这个顺序）之间可任意放+或-或都不放使其结果等于100，输出所有可能的放法。例如：1 + 2 + 3 – 4 + 5 + 6 + 78 + 9 = 100。
分析：
我们可以理解为有8个位置可以用来放置：“+”、“-”、“”，也就是说表达式的左侧一共有3^8=6561种可能。我们只需递归出它们同时检表达式的结果是否等于100即可。
实现：
根据上面的分析，在实现的过程当中有两个问题：
1：怎样得到所有的表达式；
2：如何求表达式的值。
第一个问题思路：用递归插入“+”、“-”、“”，直到插入最后一个数字；
第二个问题的思路：使用栈先将一般的中缀表达式转成后缀表达式，然后再用栈将后缀表达式的值求出，具体思路可以去看下栈在计算表达式值的应用。参考：中缀表达式转后缀表达式并求值。
代码：
import java.util.Stack;
import java.util.Vector;
public class Intermediate {
static String[] symbol = { "+", "-", "" };
static String[] num1 = { "1", "2", "3", "4", "5", "6", "7", "8", "9" };
static String[] num2 = { "9", "8", "7", "6", "5", "4", "3", "2", "1" };
private static Vector<String> strVector; // 存储所有表达式
/**
* 穷举出所有的表达式
*
* @param prevStr
* @param length
*/
public static void hundred(String prevStr, int length) {
// 加入下一个数字
if (length <= num1.length) {
prevStr += num1[length - 1];
}
for (int i = 0; i < symbol.length; i++) {
// 如果还没到第九个数字，加入下一个符号，继续递归
if (length < num1.length) {
String nextStr = prevStr + symbol[i];
hundred(nextStr, length + 1);
}else {// 如果已经到第九个数字，加入到strVector中
getStrVector().addElement(prevStr);
break;
}
}
}
public static void main(String[] args) {
if (getStrVector() == null) {
setStrVector(new Vector<String>());
} else {
getStrVector().removeAllElements();
}
String prevStr = "";
hundred(prevStr, 1);
int count = 0;
for (int i = 0; i < getStrVector().size(); i++) {
if (valueFloat(toPostfix((String) getStrVector().elementAt(i))) == 100) {
// 输出符合条件的表达式
System.out.println("解" + (count + 1) + ": "
+ getStrVector().elementAt(i)+"=100");
count++;
}
}
// 输出符合条件的表达式的个数
System.out.println("复合条件的等式一共有："+count+"个。");
}
/**
* 将中缀表达式转为后缀表达式
*
* @param expstr
* @return
*/
public static String toPostfix(String expstr) {
Stack<String> stack = new Stack<String>();
String postfix = "";
int i = 0;
while (i < expstr.length()) {
char ch = expstr.charAt(i);
switch (ch) {
case ‘+‘:
case ‘-‘:
while (!stack.isEmpty()) {
postfix += stack.pop();
}
stack.push(ch + "");
i++;
break;
case ‘*‘:
case ‘/‘:
while (!stack.isEmpty()
&& (stack.peek().equals("*") || stack.peek()
.equals("/"))) {
postfix += stack.pop();
}
stack.push(ch + "");
i++;
break;
default:
while (ch >= ‘0‘ && ch <= ‘9‘) {
postfix += ch;
i++;
if (i < expstr.length()) {
ch = expstr.charAt(i);
} else {
ch = ‘=‘;
}
}
postfix += " ";
}
}
while (!stack.isEmpty()) {
postfix += stack.pop();
}
return postfix;
}
/**
* 计算后缀表达式的值
*
* @param postfix
* @return
*/
public static float valueFloat(String postfix) {
Stack<Float> stack = new Stack<Float>();
int i = 0;
float result = 0;
while (i < postfix.length()) {
char ch = postfix.charAt(i);
if (ch >= ‘0‘ && ch <= ‘9‘) {
result = 0;
while (ch != ‘ ‘) {
result = result * 10 + Integer.parseInt(ch + "");
i++;
ch = postfix.charAt(i);
}
i++;
stack.push(new Float(result));
} else {
float y = stack.pop().floatValue();
float x = stack.pop().floatValue();
switch (ch) {
case ‘+‘:
result = x + y;
break;
case ‘-‘:
result = x - y;
break;
case ‘*‘:
result = x * y;
break;
case ‘/‘:
result = x / y;
break;
}
stack.push(new Float(result));
i++;
}
}
return stack.pop().floatValue();
}
public static Vector<String> getStrVector() {
return strVector;
}
public static void setStrVector(Vector<String> strVector) {
Intermediate.strVector = strVector;
}
}运行结果：
解1: 1+2+3-4+5+6+78+9=100
解2: 1+2+34-5+67-8+9=100
解3: 1+23-4+5+6+78-9=100
解4: 1+23-4+56+7+8+9=100
解5: 12+3+4+5-6-7+89=100
解6: 12+3-4+5+67+8+9=100
解7: 12-3-4+5-6+7+89=100
解8: 123+4-5+67-89=100
解9: 123+45-67+8-9=100
解10: 123-4-5-6-7+8-9=100
解11: 123-45-67+89=100
复合条件的等式一共有：11个。
参考：用java求解一道趣味体:123456789插入+，-，*，/后，最后结果为100
本文出自 “一个风向” 博客，请务必保留此出处http://lanffy.blog.51cto.com/6452125/1357553
在1,2,…,9（保持这个顺序）之间可任意放+或-或都不放使其结果等于100
原文：http://lanffy.blog.51cto.com/6452125/1357553