3
\$\begingroup\$

Given any series of numbers, for example 1,2,3,4,5 and given the arithmetic operands + - * / including parenthesis, what would be the most optimal way to build a tree that contains all permutations and all expressions for these numbers and operators? It doesn't have to be in a specific programming language like Java or build using recursion but that is what I used.

At the end I want to find an expression that equals a result using depth-first search that contains the result I am looking for.

As of now right now I have a working example, but the problem is that it is not efficient and leads to a problem with memory. It only works for up to 6 given numbers at the moment.

The code is as follows:

package com.company;

import com.fathzer.soft.javaluator.DoubleEvaluator;

import java.util.*;

public class PopulateAlg2 {

public static Node populateAlg2(Node node, List<Double> numbers, List<Character> operators){

    for(double number : numbers){

        for (char operator : operators){

            List<Double> _numbers = new ArrayList(numbers);

            Node child = new Node(number, operator);

            node.addChild(child);

            if(!isRootNode(node)){
                double resultWithParent = calculateNumbersAndOperator(child.getParent().getNumber(), child.getNumber(), operator);
                child.setResultWithParent(resultWithParent);
            }

            LinkedHashMap<Double, String> previousResults = node.getPreviousResults();
            LinkedHashMap<Double, String> currentResults = new LinkedHashMap<>(previousResults);

            if(previousResults.size() == 0){
                double newKey = calculateNumbersAndOperator(0, child.getNumber(), child.getOperator());

                // First expression is 0 + num, or num itself
                String newExpression = "" + child.getNumber();

                currentResults.put(newKey, newExpression);
            } else{

                // Count hashmap and don't save previous result to prevent OutOfMemoryError
                int previousResultsCounter = 0;
                int previousResultsHashmapSize = previousResults.entrySet().size();

                for (Map.Entry<Double, String> entry : previousResults.entrySet()) {

                    previousResultsCounter++;

                    if(previousResultsCounter == previousResultsHashmapSize) {
                        Double previousKey = entry.getKey();
                        String previousExpression = entry.getValue();

                        // Create permutations
                        double newKey = calculateNumbersAndOperator(previousKey, child.getNumber(), child.getOperator());
                        String newExpression = "(" + previousExpression + child.getOperator() + child.getNumber() + ")";

                        String newExpression2 = "(" + previousExpression + ")" + child.getOperator()  +  child.getNumber();
                        double newKey2 = eval(newExpression2); // Evaluate new expression

                        // Add new permutations
                        currentResults.put(newKey, newExpression);
                        currentResults.put(newKey2, newExpression2);
                    }
                }
            }

            child.setPreviousResults(currentResults);

            _numbers.remove(number);

            populateAlg2(child, _numbers, operators);
        }
    }

    return node;

}

private static boolean isRootNode(Node node){
    return node.getOperator() == ' ' && node.getNumber() == 0.0;
}

public static double eval(String expression) {
    DoubleEvaluator eval = new DoubleEvaluator();
    Double result = 0.0;

    try {
        result = eval.evaluate(expression);
    } catch (IllegalArgumentException e){
        e.printStackTrace();
    }

    return result;
}

private static double calculateNumbersAndOperator(double num1, double num2, char operator){

    double result = 0;

    if(operator == '+') {
        result = num1 + num2;
    } else if (operator == '-') {
        result = num1 - num2;
    } else if (operator == '*') {
        result = num1 * num2;
    } else if (operator == '/') {
        result = num1 / num2;
    }

    return result;

}

}

This builds a tree with every permutation possible but it contains a lot of duplicates. For example, the nodes under the root node contains every number in combination with an operator, but there are also duplicates like:

1+2+3... 
3+2+1... 
2+1+3...

I'm using the following Node class:

public class Node{
private List<Node> children = new ArrayList<>();
private Node parent = null;
private LinkedHashMap<Double, String> previousResults = new LinkedHashMap<>();

private double number;
private char operator;
private double resultWithParent;

public Node(double number, char operator) {
    this.number = number;
    this.operator = operator;
}

public void addChild(Node child) {
    child.setParent(this);
    this.children.add(child);
}

public boolean isRootNode(){
    return (parent == null);
}

public List<Node> getChildren() {
    return children;
}

public double getNumber() {
    return number;
}

public void setNumber(double number) {
    this.number = number;
}

private void setParent(Node parent) {
    this.parent = parent;
}

public Node getParent() {
    return parent;
}

public char getOperator() {
    return operator;
}

public void setOperator(char operator) {
    this.operator = operator;
}

public double getResultWithParent() {
    return resultWithParent;
}

public void setResultWithParent(double resultWithParent) {
    this.resultWithParent = resultWithParent;
}

public LinkedHashMap<Double, String> getPreviousResults() {
    return previousResults;
}

public void setPreviousResults(LinkedHashMap<Double, String> previousResults) {
    this.previousResults = previousResults;
}
}

After doing depth-first search with a different set of numbers and wanting to find the result of 728, the result is as follows:

(((((75.0)*5.0)-6.0)/25.0)*50.0)-10.0=728.0

So it works but I feel like there is a better way to build the tree in the first place, thank you for reading.

\$\endgroup\$
1
  • \$\begingroup\$ Is your goal to find the expression that produces the result or is it to build the tree and then search it? Building a complete in-memory tree for this sole purpose seems unoptimal since you're going to discard approximately 100% of the data you generate. \$\endgroup\$ May 17 at 5:46
3
\$\begingroup\$

Using infix expressions makes the code very complicated. If you were using postfix (commonly known as RPN) you could calculate each permutation for the operands and for each permutation, calculate every permutation of the operators and simply append them. No need to worry about operator precedence or parenthesis.

For example, operands [ 2, 3, 4 ] and operators [ +, * ] you get

2 3 4 + * = 14
2 3 4 * + = 14
2 4 3 + * = 14
2 4 3 * + = 14
...

Ok, those were pretty badly chosen operators and operands, but you get the idea. :D

The number of expressions you generate will be x! * (x-1)! where x is the number of operands. So for 6 operands you will create 86400 expressions, 3628800 for seven and 203212800 for eight. The factorial really isn't your friend if you want to store data in memory...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.