Use a backtracking search to build a prefix expression. If there are
two more operands than operators in the expression, the next item
could be either an operand or an operator. Otherwise, it must be an
operand.
In very loose pseudocode:
search(int target, list operands, stack opStack, string expression)
{
if ((operands.size() == 0) && (opStack.size() == 1) &&
(opStack.top() == target))
output (expression);
// Try adding each operand next in the expression
for(op = operands.begin(); op != operands.end(); ++op)
{
list nextOps = operands;
nextOps.remove(op);
opStack.push(op);
search(target, nextOps, nextStack, expression+op);
opStack.pop();
}
// Try each operator
if (opStack.size() >= 2)
{
int b = opStack.pop();
int a = opStack.pop();
opStack.push(a+b);
search(target, operands, opStack, expression + "+");
opStack.pop();
opStack.push(a-b);
search(target, operands, opStack, expression + "-");
opStack.pop();
opStack.push(a*b);
search(target, operands, opStack, expression + "*");
opStack.pop();
opStack.push(a/b);
search(target, operands, opStack, expression + "/");
opStack.pop();
opStack.push(a);
opStack.push(b);
}
}
On Mar 21, 8:57 pm, prankur gupta <duke.lnm...@gmail.com> wrote:
> Hi All,
>
> Could you help me this question.
> This was asked at Yelp Interview.
>
> Given 6 integers and 1 target value, write a function to get the target
> value using 6 integers with any on these operations +,*,-,/
>
> Thanks
>
> --
> PRANKUR GUPTA
>
> Masters Student (CSE)
> State University of New York
> Stony Brook University
> prgu...@cs.stonybrook.edu
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
