gistfile1.txt

class Solution {
	private static final char OP_CONCATENATE = ' ';

	/**
	 * Operators, ordered by priority
	 */
	private static final char[] OPERATORS = { OP_CONCATENATE, '*', '+', '-' };

	private static final boolean DEBUG = false;


	public List<String> addOperators( final String digits,
	                                  final int target ) {
		if( digits.isEmpty() ) {
			return Collections.emptyList();
		} else if( digits.length() == 1 ) {
			if( Integer.parseInt( digits ) == target ) {
				return Collections.singletonList( digits );
			} else {
				return Collections.emptyList();
			}
		}

		final int operatorsCount = digits.length() - 1;
		//4 operators -> 2bits per operator:
		final int permutationsCount = 1 << ( 2 * operatorsCount );

		final List<String> result = new ArrayList<>();
		for( int encodedOps = 0; encodedOps < permutationsCount; encodedOps++ ) {
			if( evaluate( digits, encodedOps ) == target ) {
				//evaluate( digits, encodedOps );
				result.add( decode( digits, encodedOps ) );
			}
		}
		return result;
	}

	private static long evaluate( final String digits,
	                              final int encodedOps ) {
		//Use long for operands to avoid overflow
		final List<Long> operands = new ArrayList<>( digits.length() );
		for( int i = 0; i < digits.length(); i++ ) {
			final char digit = digits.charAt( i );
			operands.add( ( long ) Character.digit( digit, 10 ) );
		}

		final int operatorsCount = digits.length() - 1;
		final List<Character> operators = new ArrayList<>( operatorsCount );
		for( int i = 0; i < operatorsCount; i++ ) {
			final int opIndex = ( encodedOps >> 2 * i ) & 0b11;
			final char operator = OPERATORS[opIndex];
			operators.add( operator );
		}
		log( operands, operators );

		//Now evaluate layer by layer, from most prioritized operators to least prioritized: 

		int j = 0;
		for( Iterator<Character> i = operators.iterator(); i.hasNext(); ) {
			final char operator = i.next();
			if( operator == OP_CONCATENATE ) {
				final long op1 = operands.get( j );
				if( op1 == 0 ) {
					//exceptional case: (0 concat 5) is invalid (!= 5)
					return Long.MIN_VALUE;//use as NaN
				}
				final long op2 = operands.get( j + 1 );
				final long result = op1 * 10 + op2;
				operands.set( j, result );
				operands.remove( j + 1 );
				i.remove();
				continue;
			}
			j++;
		}
		log( operands, operators );

		j = 0;
		for( Iterator<Character> i = operators.iterator(); i.hasNext(); ) {
			final char operator = i.next();
			if( operator == '*' ) {
				final long op1 = operands.get( j );
				final long op2 = operands.get( j + 1 );
				final long result = op1 * op2;
				operands.set( j, result );
				operands.remove( j + 1 );
				i.remove();
				continue;
			}
			j++;
		}
		log( operands, operators );

		j = 0;
		for( Iterator<Character> i = operators.iterator(); i.hasNext(); ) {
			final char operator = i.next();
			final long op1 = operands.get( j );
			final long op2 = operands.get( j + 1 );
			final long result = ( operator == '+' ) ? ( op1 + op2 ) : ( op1 - op2 );
			operands.set( j, result );
			operands.remove( j + 1 );
			i.remove();
		}

		log( operands, operators );
		if( operands.size() != 1 ) {
			throw new AssertionError( "Code bug: operands = " + operands );
		}
		return operands.get( 0 );
	}

	private static String decode( final String digits,
	                              final int encodedOps ) {
		final int operatorsCount = digits.length() - 1;
		final StringBuilder sb = new StringBuilder();
		for( int i = 0; i < operatorsCount; i++ ) {
			final int opIndex = ( encodedOps >> 2 * i ) & 0b11;
			final char operator = OPERATORS[opIndex];
			sb.append( digits.charAt( i ) );
			if( operator != OP_CONCATENATE ) {
				sb.append( operator );
			}
		}
		sb.append( digits.charAt( digits.length() - 1 ) );
		return sb.toString();
	}

	private static void log( final String str ) {
		if( DEBUG ) {
			System.out.println( str );
		}
	}

	private static void log( final List<?> operands,
	                         final List<Character> operators ) {
		if( DEBUG ) {
			log( "\toperands: " + operands + ", operators: " + operators );
		}
	}


}