Facebook Interview Question
Country: India
Interview Type: In-Person
found one small bug in the code!
updated = splits[0].strip()+'- ('+splits[1].strip()+')'
is the correct update and not
updated = splits[0].strip()+'- '+splits[1].strip()
if there is only X i.e one degree expression,then you can use 2 stacks here,
Stack 1: for keeping all the operators
Stack 2:for keeping terms
keep pushing data to stacks,when you hit a left parenthesis (")"),pop 1 element from stack 1 and 2 elements from stack 2,then apply the operator to the terms and push the result again on the stack..you will end up with a simple expression in X that can be solved easily..
But how will you calculate the result that you want to put again on the stack 2. coz this has the term x.
I think should be when met with a right parenthesis. pop() till met left parenthesis.
besides, for term x, we can keep a variable for its coefficient
The example given is a linear equation in x, and if it is then its do-able I think. any higher power, I have no clue.
For this.
1. divide the LHS by x. you get an equation with only constants
2. Evaluate LHS using the 2 stacks as mentioned by Gitesh.
3 x = RHS / evaluated (LHS)
we need not divide by X,as we do not know all terms will contain X,some may be constants as well,we can add like terms together and push on stack in the form AX+B,so we will end up with such term in the end,which can be solved by taking all constants on one side and dividing by coefficient of X
Not really an answer. just hints:
function prettify(s){
return s.replace(/\d+|x/g, function(n){return '(' + n + ')'})
.replace(/\)\(/g, ')*(')
.replace(/\s+|\t+|\n+/, '')
}
function solve (string) {
sides = string.split('='),
s1 = prettify(sides[0]),
s2 = prettify(sides[1]);
// do a regressive call on smaller side until it's just one element
// do the recursive call for this patterns you learned in high school
// f2 = (9)*(x) => f2 = (9) and f1 = f1 + '/' + x
f1 = new Function('x', 'return ' + s1),
f2 = new Function('x', 'return ' + s2);
// if f2 is single element like f2 = (9)
return f1(f2())
}
solve('4x+13(x-(4x+x/3)) = 9');
Not ideal code there is space for improvements, but...
public static void main(String[] args) {
String input = "4x+13(x-(4x+x/3)) = 99";
input = input.replace(" ", "");
System.out.println(" input " + input);
int resultOfEquation = getEquationResult(input);
System.out.println(" result is " + resultOfEquation);
double xCount = proccessCalculations(input);
System.out.println("x count is " + xCount);
double finalvalue = resultOfEquation/xCount;
System.out.println("finalvalue is " + finalvalue);
}
private static double proccessCalculations(String input) {
Stack<String> values = new Stack<>();
Stack<String> operations = new Stack<String>();
int start = 0;
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (isX(c)) {
values.push(input.substring(start, i + 1));
start = i + 1;
continue;
}
if (isOperation(c)) {
operations.push(input.substring(start, i + 1));
start = i + 1;
continue;
}
if (isBeginSkobka(c)){
if (start != i){
values.push(input.substring(start, i));
operations.push("*");
}
start = i + 1;
continue;
}
if (isEndSkobka(c)) {
if (start != i){
values.push(input.substring(start, i));
}
String valueRight = values.pop();
String valueLeft = values.pop();
String operation = operations.pop();
values.push(computeX(valueLeft, valueRight, operation));
start = i + 1;
}
}
while (!operations.isEmpty()){
perforfmOP(values, operations);
}
System.out.println(" VALUES: ");
for (String s : values) {
System.out.println(s);
}
System.out.println(" OPERATIONS: ");
for (String s : operations) {
System.out.println(s);
}
return Double.valueOf(values.pop().replace("x", ""));
}
private static void perforfmOP(Stack<String> values, Stack<String> operations){
String valueRight = values.pop();
String valueLeft = values.pop();
String operation = operations.pop();
values.push(computeX(valueLeft, valueRight, operation));
}
private static String computeX(String valueLeft, String valueRight,
String operation) {
System.out.println("performing op " + valueLeft + " " + operation + " "
+valueRight);
if (valueLeft.equals("x") || valueLeft.equals("X"))
valueLeft = "1";
else
valueLeft = valueLeft.replace("x", "");
if (valueRight.equals("x") || valueRight.equals("X"))
valueRight = "1";
else
valueRight = valueRight.replace("x", "");
if (operation.equals("*")) {
return (Double.valueOf(valueLeft) * Double.valueOf(valueRight))
+ "x";
} else if (operation.equals("/")) {
return (Double.valueOf(valueLeft) / Double.valueOf(valueRight))
+ "x";
}
if (operation.equals("+")) {
return (Double.valueOf(valueLeft) + Double.valueOf(valueRight))
+ "x";
} else if (operation.equals("-")) {
return (Double.valueOf(valueLeft) - Double.valueOf(valueRight))
+ "x";
}
return null;
}
private static boolean isEndSkobka(char c) {
return c == ')';
}
private static boolean isBeginSkobka(char c) {
return c == '(';
}
private static boolean isOperation(char c) {
// TODO Auto-generated method stub
return c == '+' || c == '/' || c == '-' || c == '*';
}
private static boolean isX(char c) {
return c == 'x' || c == 'X';
}
private static int isInt(char c) {
return c - '0';
}
private static int getEquationResult(String s) {
for (int j = s.length() - 1; j > 0; j--) {
if (s.charAt(j) == '=')
return Integer.valueOf(s.substring(j + 1, s.length()));
}
return 0;
}
Use newton-raphson method. to find the root upto the required precision.
xn+1 = xn- f(xn)/f'(xn)
What if the expression some 100th degree polynomial. What kind of solution is expected?
Are there any constraints on the expression?
If it is linear, then we can try to simplify it in the from (ax + b)/(cx + d) = e.
Create a parse tree (standard algorithms apply).
The evaluate function will basically compute the set of coefficients (a,b,c,d) for each subtree and combine based on the operator.
note that equation is of the form
y(x)=E[x]=mx+c
now y(x)=0 => x=(-c/m)
E[0]=c and m=E[1]-E[0]
thus the required solution is
x = E[0]/(E[0]-E[1])
for arbitrary form of the expression we should use newton-raphson method, however for linear equation it is already simple enough!
now assume that we are given the expression in the form of a string
note that in the expression every two entities are separated by an operator except for multiplication, like 4x, 5x, etc. also 3(4+x), etc.
so update the expression to make up for that, then evaluate it for 0 and 1.0
please refer to this code:
import re def solve(expr): updated = re.sub(r'(\d+)(x|\()',r'\1*\2',expr.strip()) #if there are other corrections that need to be made to make it a proper infix form, we have to make those changes too splits = updated.split('=') if len(splits)>2: raise Exception('incorrect format') updated = splits[0].strip()+'-'+splits[1].strip() e0str = re.sub(r'x',r'0',updated) e1str = re.sub(r'x',r'1.0',updated) try: e0 = eval(e0str) e1 = eval(e1str) except: raise("incorrect expression") print e0, e1 return e0*1.0/(e0-e1) if __name__=='__main__': print solve('4x+13(x-(4x+x/3)) = 9 ')note that if u do not want to use built in eval, write your own eval method!
- light February 23, 2013