题目
在下面的算式中，添加+、-、×、÷4个运算符，使下面这个等式成立。
5 5 5 5 5=5，各个5之间的是空格。
思路
算式左边每个间隙都可以是4个运算符中的一个，于是每个空隙都有4种可能于是总共有4的4次方种可能。以0、1、2、3分别代表+、-、×、÷四个运算符。
麻烦的点在于÷后面的数字不能是0，但是实际上本算式中是不可能出现0的。因为加号和乘号是不可能出现0的，有可能是只有减号和除号，但是减号的优先级低于除号，所以没等减号运算呢，除号先把被除数给除了，如果除号后面还是除号，那么也是前面的除号先参与运算，所以还是无法形成除0的异常，再加上本算式里面没有括号，所以本算式是不可能发生除0异常的。
本算法也是枚举算法思想的典型体现，不过稍微有点复杂。
算式中有4个空位，每个空位会放置一个符号，针对每种可能出现的情况，把它们压入符号栈。在压入的过程中，如果遇到了加减号则直接入栈，如果是遇到了乘除号则则把运算数栈的栈顶与5进行相应的乘除运算，这样一来符号栈中肯定就只有加减符号了，而运算数栈中就只剩下参与加减法的运算数了。
乘除法在上面的过程中就已经被解决了，但是加减法还没有处理呢。那么这个时候就从符号栈和运算数栈的栈底开始，2个运算数配一个运算符号，然后把结果放在第2个运算数的位置上作为下一次加减法的第一个运算数。
然后，如果最后运算数栈中的最后的那个值是5，则这个运算符号的组合就是我们想要的。
使用
package com.company;
public class Main {
public static void main(String[] args) {
// write your code here
Solution.five5Equal5();
}
}
输出
5+5+5-5-5=5
5+5-5+5-5=5
5+5-5-5+5=5
5+5-5×5÷5=5
5+5-5÷5×5=5
5+5×5-5×5=5
5+5×5÷5-5=5
5+5÷5-5÷5=5
5+5÷5×5-5=5
5+5÷5÷5×5=5
5+5÷5÷5÷5=5
5-5+5+5-5=5
5-5+5-5+5=5
5-5+5×5÷5=5
5-5+5÷5×5=5
5-5-5+5+5=5
5-5×5+5×5=5
5-5×5÷5+5=5
5-5÷5+5÷5=5
5-5÷5×5+5=5
5-5÷5÷5×5=5
5-5÷5÷5÷5=5
5×5+5-5×5=5
5×5-5×5+5=5
5×5×5÷5÷5=5
5×5÷5+5-5=5
5×5÷5-5+5=5
5×5÷5×5÷5=5
5×5÷5÷5×5=5
5÷5+5-5÷5=5
5÷5-5÷5+5=5
5÷5×5+5-5=5
5÷5×5-5+5=5
5÷5×5×5÷5=5
5÷5×5÷5×5=5
5÷5÷5×5+5=5
5÷5÷5÷5+5=5
Process finished with exit code 0
实现
package com.company;
public class Solution {
/**
* 在5个5中间添加运算符使整个算式等于5
*/
static public void five5Equal5() {
//0代表+，1代表-，2代表×，3代表÷
int[] symbolStack = new int[4];
int symbolStackPointer = -1;
int[] remainSymbolStack = new int[4];
int remainSymbolStackPointer = -1;
int[] operatorStack = new int[5];
int operatorStackPointer = -1;
for (int counter = 0;counter < 4;counter++) {
for (int counter0 = 0;counter0 < 4;counter0++) {
for (int counter1 = 0;counter1 < 4;counter1++) {
for (int counter2 = 0;counter2 < 4;counter2++) {
remainSymbolStack[++remainSymbolStackPointer] = counter2;
remainSymbolStack[++remainSymbolStackPointer] = counter1;
remainSymbolStack[++remainSymbolStackPointer] = counter0;
remainSymbolStack[++remainSymbolStackPointer] = counter;
operatorStack[++operatorStackPointer] = 5;
//先处理乘除
while (remainSymbolStackPointer > -1) {
symbolStack[++symbolStackPointer] = remainSymbolStack[remainSymbolStackPointer--];
switch (symbolStack[symbolStackPointer]) {
case 2:{
int topValue = operatorStack[operatorStackPointer--];
int result = topValue * 5;
operatorStack[++operatorStackPointer] = result;
symbolStackPointer--;
}break;
case 3:{
int topValue = operatorStack[operatorStackPointer--];
int result = topValue / 5;
operatorStack[++operatorStackPointer] = result;
symbolStackPointer--;
}break;
default:{
operatorStack[++operatorStackPointer] = 5;
}break;
}
}
//再处理加减
for (int counter3 = 0;counter3 <= symbolStackPointer;counter3++) {
switch (symbolStack[counter3]) {
case 0:{
int result = operatorStack[counter3] + operatorStack[counter3 + 1];
operatorStack[counter3 + 1] = result;
operatorStackPointer = counter3 + 1;
}break;
case 1:{
int result = operatorStack[counter3] - operatorStack[counter3 + 1];
operatorStack[counter3 + 1] = result;
operatorStackPointer = counter3 + 1;
}break;
}
}
if (operatorStack[operatorStackPointer] == 5) {
remainSymbolStackPointer = 3;
System.out.print("5");
while (remainSymbolStackPointer > -1) {
int currentSymbol = remainSymbolStack[remainSymbolStackPointer--];
switch (currentSymbol) {
case 0:{System.out.print("+5");}break;
case 1:{System.out.print("-5");}break;
case 2:{System.out.print("×5");}break;
case 3:{System.out.print("÷5");}break;
default:break;
}
}
System.out.println("=5");
}
operatorStackPointer = -1;
remainSymbolStackPointer = -1;
symbolStackPointer = -1;
}
}
}
}
}
}
