import java.util.Scanner;
import java.util.Vector;

public class DigitRiddle {
	
	// main vector holding all digit transformations
	Transformations transformations;
	
	// vector of found correct equations
	Vector correctEquations;

	// given equation, stored for reference
	String[] myFormula;
	
	// define variables for input digits
	String d1, d2, d3, op;

	public DigitRiddle() {
		this("3","+","6","0");
	}
	
	public DigitRiddle(String d1, String op, String d2, String d3) {
		this.d1 = d1;
		this.d2 = d2;
		this.op = op;
		this.d3 = d3;

		this.transformations = new Transformations();
		
		this.correctEquations = new Vector();
		
		// store as formula
		this.myFormula = new String[]{this.d1,this.op,this.d2,this.d3};
	}
	
	public static void main(String[] args) {
		
		DigitRiddle dr;
		
		if (args.length == 5) {
			// get program arguments as equation parts		
			dr = new DigitRiddle(args[0],args[1],args[2],args[4]);
		}
		else {
			// get input from console 
			Scanner console = new Scanner(System.in);
			System.out.println("Please enter an equation as\n <digit> <operator> <digit> = <digit>");
			
			String d1 = console.next();
			String op = console.next();
			String d2 = console.next();
			console.next(); // Gleichheitszeichen überspringen
			String d3 = console.next();
			
			dr = new DigitRiddle(d1,op,d2,d3);
		}
	
		// string arrays will be referenced, so get a standalone one
		String[] form = dr.myFormula.clone();
	
		// call recursive method to found correct equations
		dr.searchTree(form, 0, false, false);
		
		// print starting equation
		System.out.println("Starting equation: " + dr.myFormula[0]+dr.myFormula[1]+dr.myFormula[2]+"="+dr.myFormula[3]);
		
		// print found solutions
		dr.printFoundEquations();	
	}
	
	public void searchTree() {
		this.searchTree(new String[]{this.d1,this.op,this.d2,this.d3},0, false, false);
	}
	
	public boolean searchTree(String[] equation, int position, boolean up, boolean down)
	{
		int digit;
		Vector digitVector;
		boolean result;
				
		// two moves done -> check and return
		if (up && down) {
			
			// check equation
			if(checkEquation(equation)) {

				// store correct result in a vector
				storecorrectResult(equation.clone());
				
				return true;
			}
			return false;
		}
		
		// all digits done
		if (position >= 4) {
			return true;				
		}
			
		// get digit from formula
		digit = getDigitFromEquation(equation.clone(), position);
			
		// get digit row with all transformations
		Vector digitTransformations = (Vector) transformations.digitNumbers.get(digit);		
				
		if (!up) {

			// get possible digits for adding a stick
			digitVector = ((Vector)digitTransformations.get(2));	

			// call with all possible equations
			for (int k = 0; k < digitVector.size(); k++) {				

				if (!digitVector.get(k).toString().equals("")) {

					// store equation
					String s = equation[position];

					// set new equation
					equation[position] = digitVector.get(k).toString();
					
					// recursive call
					result = searchTree(equation, position+1, true, down);
					if (!result) {					
						equation[position] = s;
						searchTree(equation, position+1, up, down);
					}
					equation[position] = s;
				}
			}
		}
			
		if (!up && !down) {
					
			// get possible digits for changing a stick
			digitVector = ((Vector)digitTransformations.get(1));	
			
				// call with all possible equations
				for (int k = 0; k < digitVector.size(); k++) {				

					if (!digitVector.get(k).toString().equals("")) {

						// store equation
						String s = equation[position];

						// set new equation
						equation[position] = digitVector.get(k).toString();
						
						// recursive call
						result = searchTree(equation, position+1, true, true);
						//System.out.println(result);
						if (!result) {

							equation[position] = s;
							searchTree(equation, position+1, up, down);
						}
						equation[position] = s;
					}
				}			
		}

		if (!down) {
			
			// get possible digits for removing a stick
			digitVector = ((Vector)digitTransformations.get(0));
				
			// call with all possible equations
			for (int k = 0; k < digitVector.size(); k++) {				

				if (!digitVector.get(k).toString().equals("")) {
				
					// store equation
					String s = equation[position];
					
					// set new equation
					equation[position] = digitVector.get(k).toString();
					
					// recursive call
					result = searchTree(equation, position+1, up, true);
					
					if (!result) {
						equation[position] = s;
						searchTree(equation, position+1, up, down);
					}
					equation[position] = s;
				}
			}
		}

		return false;
	}
	
	private boolean checkEquation(String[] eq)
	{
		if (eq[1].equals("+")) {
			
			if (Integer.valueOf(eq[0])+Integer.valueOf(eq[2])==Integer.valueOf(eq[3])) {
				return true;
			}
		}
		else if (eq[1].equals("-")){
			
			if (Integer.valueOf(eq[0])-Integer.valueOf(eq[2])==Integer.valueOf(eq[3])) {
				return true;
			}
		}
		
		return false;		
	}
	
	private void storecorrectResult(String[] correctEquation) {
		
		boolean stored = false;
		
		// store correct result in global vector if it is not
		// already stored
		
		for (int i = 0; i < this.correctEquations.size(); i++) {
					
			String[] result = (String[]) this.correctEquations.get(i); 

			if (result[0].equals(correctEquation[0]) &&
				result[1].equals(correctEquation[1]) &&
				result[2].equals(correctEquation[2]) &&
				result[3].equals(correctEquation[3])
			) {
				stored = true;
			}
		}

		if (!stored) this.correctEquations.add(correctEquation);		
	}
	
	private int getDigitFromEquation(String[] equation, int pos) {
		
		int digit;
		
		if (equation[pos].equals("+")) {
			digit = 10;
		}
		else if (equation[pos].equals("-")) {
			digit = 11;
		}
		else {
			digit = Integer.valueOf(equation[pos]);		
		}

		return digit;
	}
	
	public void printFoundEquations() {
		
		for (int i = 0; i < this.correctEquations.size(); i++) {	
			String[] result = (String[]) this.correctEquations.get(i);	
			System.out.println("Correct equation no."+(i+1)+": "+ result[0]+result[1]+result[2]+"="+result[3]);
		}
	}
}