Find all possible outcomes of a given expression - Given an arithmetic expression, find all possible outcomes of this expression. Different outcomes are evaluated by putting brackets at different places. There will be no spaces in the input. Only operators '+','-', and '*' are allowed. Numbers can have multiple digits. Example: Input: 1+3*2 Outp…

AllOutcomesOfAnExpression.java

/**
 * Find all possible outcomes of a given expression (http://www.geeksforgeeks.org/find-all-possible-outcomes-of-a-given-expression/)
 * ================================================
 * Given an arithmetic expression, find all possible outcomes of this expression. Different outcomes are evaluated by 
 * putting brackets at different places. 
 * NOTES:
 * 1. There will be no spaces in the input.
 * 2. Only operators '+','-', and '*' are allowed. 
 * 3. Numbers can have multiple digits. 
 * 
 * Example:  
 * Input: 1+3*2 
 * Output: [7,8] 
 * Possible groupings: 1 + (3 * 2) and (1 + 3) * 2
 * */
import java.util.*;
import java.lang.*;
import java.io.*;

public class AllOutcomesOfAnExpression{
    	
    	static int evaluate(char operator, int lhs, int rhs){
		if(operator == '*'){
			return lhs * rhs;
		}
		else if(operator == '+'){
			return lhs + rhs;
		}
		else{
			return lhs - rhs;
		}
	}
    	
	static List<Integer> findAllOutcomes(String s){
		List<Integer> currentResults = new ArrayList<Integer>();
		boolean noOp = true;
		for(int i = 0; i < s.length(); i++){
		    	// Search for an operator '+', '-', '*'
			if(s.charAt(i) == '*' || s.charAt(i) == '+' || s.charAt(i) == '-'){
				noOp = false;
				// Split the string at operator and find outcomes for left part and right part
				List<Integer> left = findAllOutcomes(s.substring(0, i));
				List<Integer> right = findAllOutcomes(s.substring(i + 1));
				// Get all outcomes by applying the found operator to all pairs of results from left and right parts
				for(Integer l : left){
					for(Integer r : right){
						currentResults.add(evaluate(s.charAt(i), l, r));
					}
				}
			}
		}
		// Terminating case: If there was no operator, result is just the number formed by the digits
		if(noOp){
			currentResults.add(Integer.parseInt(s));
		}
		return currentResults;
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		List<Integer> outcomes1 = findAllOutcomes("1+3*2");
		System.out.println(outcomes1); // Output: [7, 8]
		List<Integer> outcomes2 = findAllOutcomes("1*2+3*4");
		System.out.println(outcomes2); // Output: [14, 20, 14, 20, 20]
		List<Integer> outcomes3 = findAllOutcomes("12-3*4+7");
		System.out.println(outcomes3); // Output: [-21, -7, 99, 7, 43]
	}
}