Skip to content

Instantly share code, notes, and snippets.

@rajeakshay
Last active September 10, 2024 08:19
Show Gist options
  • Save rajeakshay/3c62bc01f0d8a97898662b74c334e085 to your computer and use it in GitHub Desktop.
Save rajeakshay/3c62bc01f0d8a97898662b74c334e085 to your computer and use it in GitHub Desktop.
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…
/**
* 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]
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment