Mathematical Expression evaluation preferably without using stacks or queues

Question

Given the allowed operators of +, /, -, *, and given a user inputted list of single digit numbers (any length allowed), how can I output all possible combinations of mathematical expressions (and the resulting values) that can be formed with the numbers and the given constant set of operators? Also to allow for scalability, for example, to easily be able to add another operator in the mix (if possible)

Preferably without the use of a stack or queue but they are not unacceptable.

Note, if the input is {1,3,5,7}

Possible output would be (1+3)-(5+7) = -8, (1+5)-(3-7) = 10, etc. (13+57) is not a possible combination since combining of the digits should not be allowed.

Also note: I was able to write something similar using Scheme to do this, but I can't seem to do it with Java or C#

Answer 1

Hi

I'm not a Java or C# programmer, so here goes with a language-ignorant answer. Neither of your chosen languages seems to have an eval function. I'd suggest that you take on board Reverse Polish Notation. Capture the inputs as characters in a string or whatever you wish; encode the operators as characters too. Then, using iterators or whatever, generate all possible orderings of the input digits, followed by all possible orderings of the right number of binary operators. Then use a couple or so switch statements to translate each string into a result.

Sorry I can't be more explicit, got to rush.

Regards

Mark

Answer 2

Classic permutation problem.

The trick is to pass in a set of function pointers to create an operators array (stack, list, etc...). In C# and Java, function pointers can be implemented by objects and interfaces.

You then need to come up with all the various orderings of each list.

Note also that you can only have 3 operators and that it's ambiguous whether some of the operators can be applied to the sets on either side in different ways.

Eg//

a+b / c - d <> (a+b) / (c-d)

I'm not sure if brackets are also to be considered. If they are, the solution is a little trickier (though the principles are the same). Simply include a set of brackets and permeate those too (though you'll also have to consider the constraint that a left bracket must have a closing right bracket). I'll not cover that here.

Permutation algorithms abound for inputs, so just pick one and use it to generate all the various collections of operators and of numbers.

To calculate all the results simply iterate the list of operators, passing the list of numbers sequentially and you're done.

Eg//

public interface Operator {
    public Double calc(int val1, int val2);
}

public class Add implements Operator {
    public Double calc(int val1, int val2){
        return Double(val1 + val2);
    } 
}

public class Sub implements Operator {
    public Double calc(int val1, int val2){
        return Double(val1 - val2);
    } 
}
public class Mul implements Operator {
    public Double calc(int val1, int val2){
        return Double(val1 * val2);
    } 
}

public class Div implements Operator {
    public Double calc(int val1, int val2){
        return Double(val1 / val2);
    } 
}

public static Double calc(Operator[] operator_list, int[] value_list)
{
  Double ret_val = Double(value_list[0]);

  for (int j = 0; j < operator_list.length(); j++){
    Operator oper = operator_list[j];
    ret_val = oper.calc(ret_val, value_list[j+1]);                 
  }

  return ret_val;
}

public static void main(String[] args)
{ 
int[] values = {1,2,3,4};

Operator add = new Add();
Operator div = new Div();
Operator mul = new Mul();
Operator sub = new Sub();

Operator[] operators = {add, div, sub, mul};

// Calculate from permutation algorithm...
// Don't forget to only generate three values for each permutation!
// out_perm_1 = {add, div, sub};
// out_perm_2 = {div, add, sub};
Operator[] operator_permutations = perm(operators);

// Calculate from permutation algorithm...    
// val_perm_1 = {1,2,3,4};
// val_perm_2 = {2,1,3,4};
int[] value_permutations = perm(values);

// Interleave the two lists...
for (int i=0; i < output_permutations.length(); i++)
{
    for (int j=0; j < value_permutations.length(); j ++)
    {
        System.out.println(calc(output_permutations[i], output_permutations[j]));
    }
}
}

etc...