Problem Statement You are required to write a program which, when given a sequence of integers, creates an equation. All but the last integer in the given sequence form an LHS (left-hand-side). The last integer forms an RHS. Operators are inserted between the integers in the LHS to form an expression. Like in any good equation, the LHS must equal the RHS. The operators allowed to be used are: {+, -, *}

You can use any operator at any place and any number of times. An operator can only be placed in between two integers and two integers can have only one operator between them. While evaluating the formed expression, the precedence of operators has to be observed. Note that the positions of integers given cannot be changed.

Thus, if 8, 5, 2, -2 are the integers given, then your program must create the expression: 8 - 5 * 2 = -2 Here, the integers 8, 5, 2 belong to the LHS and integer -2 forms the RHS. The LHS, with placeholders for operators is: 8 5 2. When - and * are inserted, they form an expression: 8 - 5 * 2. Using precedence rules, this evaluates to: 8 - 10, which works out to be equal to RHS.

NOTE:

It is guaranteed that there will be only one possible LHS which equals the RHS. Expression evaluation is done from left to right, thus expression 2-2+2 evaluates to 2 and not -2 Input Specification First line contains one integer K (3 < K < 7) indicating the number of integers The second line contains 'K' integers, each separated by a space Output Specification The operator sequence without any spaces between them terminated by a newline

Sample Test Cases Test Case 1 Input: 4 8 5 2 -2

Output: -*

Test Case 2 Input: 5 1 1 1 1 4

Output: +++

Test Case 3 Input: 5 7 5 3 2 29

Output:
*-*

View Answers

July 24, 2012 at 1:27 PM

Here is a code that accepts the integers from the users and made an expression which in result satisfied the condition LHS=RHS.

import java.util.Scanner; public class SequenceOfIntegers { static int num; static int result; static int lhs[]; static boolean stop = false; public static char getOperator(int num) { switch (num) { case 0: return '+'; case 1: return '-'; case 2: return '*'; } return '.'; } public static void evaluate(String operators) { int arr[] = (int[])lhs.clone(); String answer = operators; while (operators.indexOf("-")!=-1) { int pos = operators.indexOf("-"); arr[pos+1] = -arr[pos+1]; operators = operators.substring(0,pos)+"+"+operators.substring(pos+1); } while (operators.indexOf("*")!=-1) { int pos=operators.indexOf("*"); arr[pos+1] = arr[pos]*arr[pos+1]; arr[pos]=0; operators = operators.substring(0,pos)+"+"+operators.substring(pos+1); } int sum = 0; for (int i=0; i<num; i++) sum += arr[i]; if (sum==result) System.out.println("Output: "+answer); } public static void find(String operators) { if (operators.length() > num-2) { evaluate(operators); return; } for (int i=0; i<3; i++) find(operators+getOperator(i)); } public static void main(String []s) { Scanner input = new Scanner(System.in); System.out.print("Enter number of Integers: "); num = input.nextInt() - 1; lhs = new int[num]; int i; System.out.println("Input: "); for(i=0; i<num ;i++) lhs[i] = input.nextInt(); result = input.nextInt(); find(""); } }

September 11, 2012 at 4:35 PM

Can u please explain me the concept in detail. I didn't get the concept.

Related Tutorials/Questions & Answers: