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.
