迭代通式法

1.迭代通项
2.四则运算
[一]
x1, x2, x3, x4，四个数属于[1, 10]
f(x1, x2, x3, x4)，f表示四个数之间加减乘除且每个数字仅使用一次计算得到的结果
如果结果列表存在24返回true，否则false。
[二]
f: 多种算式
条件：运算符号为+ - * /，考虑括号
每个数字在算式出现一次
目标：f的所有结果列表，即需得到f通项结果，即需要得到f通项算式，即需要得到f算式列表
通项算式：
组成：数字、数子间3个符号、小括号对
[三]
数字: x 符号; s1一级符号， s2二级符号
A括号只有小括号(ok)
(x s2 x) s1 x s1 x
s2 s1 s1
[x s2 (x s2 x)] s1 x
等价于(x s2 x s2 x) s1 x
s2 s2 s1

[x s1 (x s2 x)] s1 x
等价于x s1 (x s2 x) s1 x
s1 s2 s1
s1 s1 s2
综上：无需中括号，只需小括号

B小括号数：最多两对
零对：x s1 x s1 x s1 x
一对：(x s1 x) s1 x s1 x
x s1 (x s1 x) s1 x
x s1 x s1 (x s1 x)
(x s1 x s1 x) s1 x
x s1 (x s1 x s1 x)
两对：(x s1 x) s1 (x s1 x)
[五]
迭代通式：
迭代法遍历数字和符号，获取无括号通项算式，基于无括号通项算式获得有括号通项算式。
迭代法本质：(((xsx)sx)sx)
迭代衍码：
f(x, list)=x
f(x s x s x, list) 值确定
f(x s x s x s x, list) = f( f(x s x s x) s x, list)
4! 已用数子坐标list，用于过滤数和确定返回最终结果。
统计如下：
str=""
str=x1+s1+x2+s2+x3+s3+x4
算式个数：72464=10752
括号对数(对数及位置)：7个
符号组合数：444=64个
数子组合数：432*1=24个
通项结果：
g(str)：四则运算

[六]
迭代通项代码

/**
 * 24点游戏算法
 *     1.通项算式
 *     2.四则运算
 * @author zhuyq
 * @date 2020-12-08
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import com.tellhow.czp.netorder.app.nowcoder.huawei.Arithmetic;

public class TwentyFourPointGameArithmetic {
    private static String points = "24";
    public static ArrayList<String> arithmeticStrWithoutBracketList = new ArrayList<>();

    public static void main(String[] args){
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        try {
            while((str = br.readLine())!= null){
                String[] strArr = str.split(" ");
                ArrayList<Integer> numberList = new ArrayList<>();
                for(int i=0; i<strArr.length; i++){
                    Integer val = Integer.valueOf(strArr[i]);
                    numberList.add(val);
                }
                ArrayList<String> arithmeticStrList = getArithmeticStrList1(numberList);
                ArrayList<String> arithmeticResultList = getArithmeticResultList(arithmeticStrList);
                boolean result = isTwentyFourPoint(arithmeticResultList);
                System.out.println(result);

                ArrayList<String> twentyFourPointarithmeticResultList = getTwentyFourPointArithmeticResultList(arithmeticStrList);
                for(String s: twentyFourPointarithmeticResultList){
                    System.out.println(s);
                }
            }
        } catch (NumberFormatException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }




    /**
     * 判断是否24点
     * @author zhuyq
     * @date 2020-12-08
     */
    public static boolean isTwentyFourPoint(ArrayList<String> arithmeticResultList){
        boolean isTwentyFourPoint = false;

        for(int i=0; i<arithmeticResultList.size(); i++){
            String result = arithmeticResultList.get(i);
            if(result.equals(points)){
                isTwentyFourPoint = true;
                break;
            }
        }
        return isTwentyFourPoint;
    }

    /**
     * 获取24点算式列表
     * @author zhuyq
     * @date 2020-12-08
     */
    public static ArrayList<String> getTwentyFourPointArithmeticResultList(ArrayList<String> arithmeticStrList){
        ArrayList<String> twentyFourPointarithmeticResultList = new ArrayList<>();
        for(int i=0; i<arithmeticStrList.size(); i++){
            String arithmeticStr = arithmeticStrList.get(i);
            String result = Arithmetic.arithmeticCaculate(arithmeticStr);
            if(result.equals(points)){
                twentyFourPointarithmeticResultList.add(arithmeticStr);
            }
        }
        return twentyFourPointarithmeticResultList;
    }

    /**
     * 算式结果列表
     * @author zhuyq
     * @date 2020-12-08
     */
    public static ArrayList<String> getArithmeticResultList(ArrayList<String> arithmeticStrList){
        ArrayList<String> arithmeticResultList = new ArrayList<>();
        for(int i=0; i<arithmeticStrList.size(); i++){
            String arithmeticStr = arithmeticStrList.get(i);
            String result = Arithmetic.arithmeticCaculate(arithmeticStr);
            arithmeticResultList.add(result);
        }
        return arithmeticResultList;
    }


    /**
     * 迭代替换多层for
     * 
     * f(x, list)=x
     * f(x s x s x, list) 值确定
     * f(x s x s x s x, list) = f( f(x s x s x) s x, list)
     * 
     * list：已用数子坐标列表，用于过滤数和确定返回最终结果
     * 
     * 细节点：迭代法参数有list，list必须clone
     * 
     * @author zhuyq
     * @date 2020-12-09
     */
    public static ArrayList<String> getArithmeticStr(ArrayList<Integer> numberList, ArrayList<String> symbolList, String x, ArrayList<Integer> list){
        if(list.size()==4){
            arithmeticStrWithoutBracketList.add(x);
        }
        else{
            for(int i=0; i<numberList.size(); i++){
                boolean isExist = false;
                for(int j=0; j<list.size(); j++){
                    if(list.get(j).equals(i)){
                        isExist = true;
                    }
                }
                if(!isExist){
                    ArrayList<Integer> list1 = (ArrayList<Integer>) list.clone();
                    list1.add(i);
                    for(int j=0; j<symbolList.size(); j++){
                        getArithmeticStr(numberList, symbolList, x+symbolList.get(j)+numberList.get(i), list1);
                    }
                }
            }
        }
        return arithmeticStrWithoutBracketList;
    }

    /**
     * 算式列表
     * @author zhuyq
     * @date 2020-12-09
     */
    public static ArrayList<String> getArithmeticStrList1(ArrayList<Integer> numberList){
        ArrayList<String> arithmeticStrList = new ArrayList<>();

        ArrayList<String> symbolList = new ArrayList<>();
        symbolList.add("+");
        symbolList.add("-");
        symbolList.add("*");
        symbolList.add("/");

        for(int i=0; i<numberList.size(); i++){
            ArrayList<Integer> list = new ArrayList<>();
            list.add(i);
            String x = String.valueOf(numberList.get(i));
            /**
             * 零对：x s1 x s1 x s1 x
             */
            getArithmeticStr(numberList, symbolList, x, list);
        }
        /**
         * 通项算式(有括号)
         */
        for(int i=0; i<arithmeticStrWithoutBracketList.size(); i++){
            String arithmeticStrWithoutBracket = arithmeticStrWithoutBracketList.get(i);
            ArrayList<String> bracketArithmeticStrList = getBracketArithmeticStrListForSpecifiedArithmeticStr(arithmeticStrWithoutBracket);
            arithmeticStrList.add(arithmeticStrWithoutBracket);
            for(int j=0; j<bracketArithmeticStrList.size(); j++){
                arithmeticStrList.add(bracketArithmeticStrList.get(j));
            }
        }

        return arithmeticStrList;
    }



    /**
     * 通项算式(有括号)
     * 一对：(x s1 x) s1 x s1 x
     *         x s1 (x s1 x) s1 x
     *         x s1 x s1 (x s1 x)
     *         (x s1 x s1 x) s1 x
     *         x s1 (x s1 x s1 x)
     * 两对：(x s1 x) s1 (x s1 x)
     */
    public static ArrayList<String> getBracketArithmeticStrListForSpecifiedArithmeticStr(String arithmeticStr){
        ArrayList<String> bracketArithmeticStrList = new ArrayList<>();

        ArrayList<String> bracketList = new ArrayList<>();
        bracketList.add("(");
        bracketList.add(")");

        String regex = "[\\+\\-\\*/]";
        String[] numArr = arithmeticStr.split(regex);

        String[] symbolArr = new String[3];
        Matcher slashMatcher = Pattern.compile(regex).matcher(arithmeticStr); 
        int idx = -1;
        while(slashMatcher.find()) { 
            idx++;
            symbolArr[idx] = slashMatcher.group();
        }
        String x1 = numArr[0];
        String x2 = numArr[1];
        String x3 = numArr[2];
        String x4 = numArr[3];
        String s1 = symbolArr[0];
        String s2 = symbolArr[1];
        String s3 = symbolArr[2];

        StringBuilder sb1 = new StringBuilder();
        sb1.append(bracketList.get(0)).append(x1).append(s1).append(x2).append(bracketList.get(1)).append(s2).append(x3).append(s3).append(x4);
        StringBuilder sb2 = new StringBuilder();
        sb2.append(x1).append(s1).append(bracketList.get(0)).append(x2).append(s2).append(x3).append(bracketList.get(1)).append(s3).append(x4);
        StringBuilder sb3 = new StringBuilder();
        sb3.append(x1).append(s1).append(x2).append(s2).append(bracketList.get(0)).append(x3).append(s3).append(x4).append(bracketList.get(1));
        StringBuilder sb4 = new StringBuilder();
        sb4.append(bracketList.get(0)).append(x1).append(s1).append(x2).append(s2).append(x3).append(bracketList.get(1)).append(s3).append(x4);
        StringBuilder sb5 = new StringBuilder();
        sb5.append(x1).append(s1).append(bracketList.get(0)).append(x2).append(s2).append(x3).append(s3).append(x4).append(bracketList.get(1));
        StringBuilder sb6 = new StringBuilder();
        sb6.append(bracketList.get(0)).append(x1).append(s1).append(x2).append(bracketList.get(1)).append(s2).append(bracketList.get(0)).append(x3).append(s3).append(x4).append(bracketList.get(1));
        bracketArithmeticStrList.add(sb1.toString());
        bracketArithmeticStrList.add(sb2.toString());
        bracketArithmeticStrList.add(sb3.toString());
        bracketArithmeticStrList.add(sb4.toString());
        bracketArithmeticStrList.add(sb5.toString());
        bracketArithmeticStrList.add(sb6.toString());

        return bracketArithmeticStrList;
    }


    /**
     * 基于list去掉指定项返回新(不同指针)的list
     * @author zhuyq
     * @date 2020-12-08
     */
    public static ArrayList<Integer> getNewListByRemove(ArrayList<Integer> numberList, int i){
        ArrayList<Integer> numberList1 = new ArrayList<>();
        for(int k=0; k<numberList.size(); k++){
            Integer xk = numberList.get(k);
            if(k!=i){
                numberList1.add(xk);
            }
        }
        return numberList1;
    }

}

四则算法代码如下：

package com.tellhow.czp.netorder.app.nowcoder.huawei;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import com.tellhow.czp.netorder.app.nowcoder.huawei.entity.UnitExpression;
import com.tellhow.czp.netorder.app.nowcoder.huawei.util.StrUtil;

/**
 * 四则运算
 * @author zhuyq
 * @date 2020-11-11
 */ 
public class Arithmetic {

    public static void main(String[] args){
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strExpression = null;
        try {
            while((strExpression = br.readLine())!= null){
                String result = arithmeticCaculate(strExpression);
                System.out.println(result);
            }
        } catch (NumberFormatException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 四则运算
     * @author zhuyq
     * @date 2020-11-11
     */
    public static String arithmeticCaculate(String strExpression){
        /*************************括号运算开始*****************************/
        //小括号运算
        strExpression = bracketCaculate(strExpression, "()");
        //中括号运算
        strExpression = bracketCaculate(strExpression, "[]");
        //大括号运算
        strExpression = bracketCaculate(strExpression, "{}");
        /*************************括号运算结束*****************************/
        /*************************单元算式开始*****************************/
        //通用单元表达式解析计算
        strExpression = UnitExpression.commonUnitExpressionParseCaculate(strExpression);
        /*************************单元算式结束*****************************/
        return strExpression;
    }


    /**
     * 括号运算
     * @author zhuyq
     * @date 2020-11-11
     */
    public static String bracketCaculate(String strExpression, String bracket){
        ArrayList<UnitExpression> unitExpressionList = new ArrayList<>();
        //截取所有小中大括号部分，并按UnitExpression格式及顺序存入List
        Integer count = StrUtil.countChar(strExpression, bracket.substring(0, 1));
        for(int i=0; i<count; i++){
            Integer start = StrUtil.getCharacterPosition(strExpression, bracket.substring(0, 1), i+1);
            Integer end = StrUtil.getCharacterPosition(strExpression, bracket.substring(1, 2), i+1);
            String unitExpressionStr = strExpression.substring(start+1, end);
            UnitExpression unitExpression = new UnitExpression(unitExpressionStr, start, end, bracket);
            unitExpressionList.add(unitExpression);
        }
        //小中大括号计算，并替换到四则运算表达式中
        StringBuilder strExpressionSb = new StringBuilder(strExpression);
        for(int i=0; i<unitExpressionList.size(); i++){
            UnitExpression unitExpression = unitExpressionList.get(i);
            Integer start = StrUtil.getCharacterPosition(strExpressionSb.toString(), bracket.substring(0, 1), 1);
            Integer end = StrUtil.getCharacterPosition(strExpressionSb.toString(), bracket.substring(1, 2), 1);
            unitExpression.setStart(start);
            unitExpression.setEnd(end);
            //通用单元表达式解析计算
            String result = UnitExpression.commonUnitExpressionParseCaculate(unitExpression.getUnitExpressionStr());

            int position = strExpressionSb.toString().indexOf("("+unitExpression.getUnitExpressionStr()+")");
            //特殊情况处理 小括号7+2+(1-10) 2020-12-08
            if(unitExpression.getBracket().equals("()") && (new BigDecimal(result)).compareTo(BigDecimal.valueOf(0))==-1 && position>0){
                strExpressionSb.replace(unitExpression.getStart()-1, unitExpression.getEnd()+1, result);
            }
            else{
                strExpressionSb.replace(unitExpression.getStart(), unitExpression.getEnd()+1, result);
            }
        }
        strExpression = strExpressionSb.toString();
        return strExpression;
    }


}

package com.tellhow.czp.netorder.app.nowcoder.huawei.entity;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import com.tellhow.czp.netorder.app.nowcoder.huawei.util.StrUtil;

/**
 * 单元表达式(小/中/大括号里头的表达式和优先级表达式)
 * @author zhuyq
 * @date 2020-11-11
 */
public class UnitExpression {
    String unitExpressionStr;        //单元表达式
    Integer start;                    //单元表达式左符号在四则运算表达式字符串定位
    Integer end;                    //单元表达式右符号在四则运算表达式字符串定位
    String bracket;                    //括号(小括号、中括号、大括号)及优先级符号(*/)

    public UnitExpression() {

    }
    public UnitExpression(String unitExpressionStr, Integer start, Integer end, String bracket) {
        super();
        this.unitExpressionStr = unitExpressionStr;
        this.start = start;
        this.end = end;
        this.bracket = bracket;
    }

    public String getUnitExpressionStr() {
        return unitExpressionStr;
    }
    public void setUnitExpressionStr(String unitExpressionStr) {
        this.unitExpressionStr = unitExpressionStr;
    }
    public Integer getStart() {
        return start;
    }
    public void setStart(Integer start) {
        this.start = start;
    }
    public Integer getEnd() {
        return end;
    }
    public void setEnd(Integer end) {
        this.end = end;
    }
    public String getBracket() {
        return bracket;
    }
    public void setBracket(String bracket) {
        this.bracket = bracket;
    }

    /**
     * 通用单元表达式解析计算
     * 方法：先算一级，再算二级
     * @author zhuyq
     * @date 2020-11-13
     */
    public static String commonUnitExpressionParseCaculate(String strExpression){
        //单元表达式解析计算--优先级(*/)
        strExpression = priorityCaculate(strExpression);
        //单元表达式解析计算--无优先级(+-)
        strExpression = UnitExpression.unitExpressionParseCaculate(strExpression);
        return strExpression;
    }

    /**
     * 优先级(计算*和/，*和/优先级大于+和-，且*和/同优先级)
     * 问题：连乘除和同优先级。方法：具体边解析边计算，逻辑或正则表达式 [乘除]。
     * 优化：优先级多位数及小数问题。方法：解析添加正则引擎。根据数字[乘或除]数字匹配字符串中第一处。
     *             兼容负数问题。方法：正则引擎数字兼容负数。
     * @author zhuyq
     * @date 2020-11-12
     */
    public static String priorityCaculate(String strExpression){
        StringBuilder strExpressionSb = new StringBuilder(strExpression);
        //截取所有*和/算式部分
        Integer count = StrUtil.countChar(strExpression, "*") + StrUtil.countChar(strExpression, "/");
        for(int i=0; i<count; i++){
            //解析
            String regex = "-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))[*/]-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))";
            Matcher slashMatcher = Pattern.compile(regex).matcher(strExpression); 
            Integer mIdx = 0; 
            while(slashMatcher.find()) { 
                mIdx++; 
                 //当regex正则一级运算第1次出现的位置 
                 if(mIdx == 1){ 
                       break; 
                 } 
            } 
            Integer start = slashMatcher.start();
            Integer end = slashMatcher.end();
            String unitExpressionStr = strExpression.substring(start, end);
            UnitExpression unitExpression = new UnitExpression(unitExpressionStr, start, end, "[*/]");

            //计算
            String result = UnitExpression.unitExpressionParseCaculate(unitExpression.getUnitExpressionStr());
            //特殊情况处理:-0[*/]数或负数[*/]0
            String regex1 = "(-0[*/]-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9])))|-(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))[*]0";
            Matcher slashMatcher1 = Pattern.compile(regex1).matcher(unitExpressionStr); 
            if(slashMatcher1.find()){
                result = "+0";
            }
            strExpressionSb.replace(unitExpression.getStart(), unitExpression.getEnd(), result);
            strExpression = strExpressionSb.toString();
        }
        return strExpression;
    }

    /**
     * 单元表达式解析计算, 优先级(无优先级按顺序计算)
     * @author zhuyq
     * @date 2020-11-11
     */
    public static String unitExpressionParseCaculate(String unitExpressionStr){
        BigDecimal result = new BigDecimal(0.00);
        //ArrayList<Integer> numberList = new ArrayList<>();
        ArrayList<String> numberList = new ArrayList<>();
        ArrayList<String> symbolList = new ArrayList<>();

        //特殊情况：表达式只有一个数字
        String resultStr = "";
        String regex0 = "-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))";
        Matcher slashMatcher0 = Pattern.compile(regex0).matcher(unitExpressionStr); 
        Integer z = -1;
        while(slashMatcher0.find()){
            z++;
        }
        if(z==0){
            resultStr = unitExpressionStr;
        }
        else{
            /**
             * 单元表达式解析，切割数字及符号并按顺序分别存入List
             * @version V2.0 [正则解析] 适用正数(多位数、小数)、负数
             * @author zhuyq
             * @date 2020-11-13
             */
            String regex = "-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))|[*/+]";
            Matcher slashMatcher = Pattern.compile(regex).matcher(unitExpressionStr); 
            Integer j = -1; 
            while(slashMatcher.find()) { 
                String s = unitExpressionStr.substring(slashMatcher.start(), slashMatcher.end());
                /**
                 * 问题：减号与负号冲突
                 * 方案：减号作负号用，如果数为负数，那么符号symbolList添加"+"
                 * @date 2020-11-13
                 */
                if( !(s.equals("*") || s.equals("/") || s.equals("+")) ){
                    j++;
                    numberList.add(s);

                    if( j>0 ){
                        String str = numberList.get(j-1)+s;
                        String regex1 = "-?(([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))[-](([0-9]\\d*\\.?\\d*)|(0\\.\\d*[0-9]))";
                        Matcher slashMatcher1 = Pattern.compile(regex1).matcher(str); 
                        if(slashMatcher1.find()){
                            symbolList.add("+");
                        }
                    }
                }
                else{
                    symbolList.add(s);
                }
            } 

            //单元表达式计算

            for(int i=0; i<symbolList.size(); i++){
                String symbol = symbolList.get(i);

                BigDecimal first = new BigDecimal(0.00);
                if( i == 0 ){
                    first = new BigDecimal(numberList.get(i));
                } else{
                    first = result;
                }

                BigDecimal second = new BigDecimal(numberList.get(i+1));

                result = new BigDecimal( smallUnitCaculate(first, second, symbol ) );
            }
            resultStr = result.toString();
        }

        return resultStr;

    }

    /**
     * 小单元运算
     * @author zhuyq
     * @date 2020-11-11
     */
    public static String smallUnitCaculate(BigDecimal first, BigDecimal second, String symbol){
        BigDecimal result = new BigDecimal(0.00);
        if(symbol.equals("+")){
            result = first.add(second);
        }
        else if(symbol.equals("-")){
            result = first.subtract(second);
        }
        else if(symbol.equals("*")){
            result = first.multiply(second);
        }
        else if(symbol.equals("/")){
            if(second.compareTo(BigDecimal.valueOf(0)) == 0){
                result = BigDecimal.valueOf(Double.MAX_VALUE);
            }
            else{
                result = first.divide(second, 2, BigDecimal.ROUND_HALF_UP);
            }
        }
        return result.toString();
    }


}

package com.tellhow.czp.netorder.app.nowcoder.huawei.util;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * 字符串工具类
 * @author zhuyq
 * @date 2020-11-13
 */
public class StrUtil {
    /**
     * 获取指定字符在字符串第n次出现的位置
     * @author zhuyq
     * @date 2020-11-11
     */
    public static Integer getCharacterPosition(String strExpression, String bracket, Integer n){ 
        //这里是获取bracket符号的位置 
        Matcher slashMatcher;
        //括号
        if( bracket.equals("(") || bracket.equals(")") || bracket.equals("[") || bracket.equals("]") || bracket.equals("{") || bracket.equals("}") ){
            slashMatcher = Pattern.compile("\\"+bracket).matcher(strExpression); 
        }
        //乘除
        else{
            slashMatcher = Pattern.compile(bracket).matcher(strExpression); 
        }

        Integer mIdx = 0; 
        while(slashMatcher.find()) { 
            mIdx++; 
             //当bracket符号第n次出现的位置 
             if(mIdx == n){ 
                   break; 
             } 
        } 
        return Integer.valueOf(slashMatcher.start()); 
    }

    /**
     * 统计字符串中指定字符出现的次数
     * @author zhuyq
     * @date 2020-11-11
     */
    public static Integer countChar(String strExpression, String bracket){
        Integer count = 0;
        for(int i=0; i<strExpression.length(); i++){
            if(bracket.equals(String.valueOf(strExpression.charAt(i)))){
                count++;
            }     
        }
        return count;
    }
}