java - 获取数学表达式的每个排列

Question

任务

给定一个数字列表

例如:

1、2、3。

使用乘法或加法(*/+)运算得到这些数字的每一个组合

所以在上面的例子中，组合是

1+2+3

1+2*3

1*2*3

1*2+3

我写了一个基本的递归方法来解决它，我的思路如下

给定一个数字我也可以

1. 添加下一个号码

2. 乘以下一个数

这样你就得到了这样一棵树

           START NUMBER
              /   \
             *     +
            / \   /  \
           *   + *    +

等等...

但是输出输出每个答案两次

我使用 1,2,3 时得到的输出是

1*2+3

1*2+3

1*2*3

1*2*3

1+2+3

1+2+3

1+2*3

1+2*3

我的问题

1. 这是一个可以接受的算法吗？如果是的话，我的代码出了什么问题

2. 还有其他更有效的方法吗？

代码

    package AG;

import java.util.LinkedList;
import java.util.Stack;

/**
 *
 * @author Tamir Shklaz
 */
public class ArithmeticGame {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
        LinkedList<Integer> number = new LinkedList<>();
        for (int i = 1; i <= 3; i++) {
            numbers.add(i);
        }
        permutateSigns('*', numbers, 0, "");
        permutateSigns('+', numbers, 0, "");

    }


    public static void permutateSigns(char operation, LinkedList<Integer> number, int pos, String expresion) {
        double sum = 0;
        if (pos == number.size()-1) {
            expresion += number.get(pos);
            System.out.println(expresion);


        } else {
            expresion += (Integer.toString(number.get(pos)) + Character.toString(operation));
            permutateSigns('+', number, pos + 1, expresion);
            permutateSigns('*', number, pos + 1, expresion);
        }

    }
}

Answer 1

我认为您的错误在于您将单个运算符传递给函数 permutateSigns 而不是提供所有运算符。

因此，您在开始时调用了同一个函数两次，这导致了双重答案。

这是更正后的代码(我想这就是你需要的)

public class ArithmeticGame {

    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
        for (int i = 1; i <= 3; i++) {
            numbers.add(i);
        }
        char[] operations = { '*', '+' };
        permutateSigns(operations, numbers, 0, "");
    }

    public static void permutateSigns(char[] operations, LinkedList<Integer> numbers, int pos, String expression) {
        expression += numbers.get(pos);
        if (pos == numbers.size() - 1) {
            System.out.println(expression);
        } else {
            for (char operation : operations) {
                permutateSigns(operations, numbers, pos + 1, expression + operation);
            }
        }
    }
}

此外，我建议您使用ArrayList 而不是LinkedList，因为执行的get 操作将具有O( 1)时间而不是O(n)