Facebook interview questions - String Expression Evaluation

Given an expression in the form of a string and x, solve for y?

The highest power of x in the expression will be equal to 1. Operators allowed are +, -, * and /. 

For example, consider the following equation:

3+2x+5y-(3+5x)=9-7y+2x Given such an equation and the value of x, find y.

 

这个问题事先不了解下的话很难在半小时内bugfree的写完。

Step1:

参考这里：

http://www.quora.com/Programming-Interview-Questions/Given-an-expression-in-the-form-of-a-string-solve-for-x

What you can do is call the expression on the left side of the equation f(x) and the expression on the right side of the equation g(x), and calculate f(0), g(0), f(1), and g(1). This calculation can be made by simple substituting the value of x in the string and use stack for solving expression. Then the value of x will be:
 
x = (f(0) -g(0)) / (f(0) - g(0) - f(1) + g(1))
 
For example:
2*x+5-(4*x-7+(4-2))=10*x-9

The values will be f(0) = 10, f(1) = 8, g(0) = -9, and g(1) = 1, so x = 19/12. Presuming that you want the exact answer, leave it in fractional form, and if the denominator is negative, then negate both numerator and denominator. Then divide both numerator and denominator by their gcd. Finally, if the denominator is 1, report the numerator as the answer; otherwise report the fraction numerator/denominator as the answer.

懒得翻译了，就是如何将变量和常量分别移动到等号两侧。

f(0) -g(0)表示常量，通过将变量设为0而将左右两边所有变量抵消掉

f(0) - g(0) - f(1) + g(1)代表x变量的系数，此运算可将所有常量抵消掉。

 

Step2:

每侧的表达式怎么求值呢？需要把它转换成RPN逆波兰表达式。

这里就需要用到Shunting-yard algorithm了。以下内容来自维基百科。

算法细节为：

• While there are tokens to be read:

• Read a token.
• If the token is a number, then add it to the output queue.
• If the token is a function token, then push it onto the stack.
• If the token is a function argument separator (e.g., a comma):

• Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.

• If the token is an operator, o₁, then:

• while there is an operator token, o₂, at the top of the stack, and

either o₁ is left-associative and its precedence is *less than or equal* to that of o₂,

or o₁ if right associative, and has precedence *less than* that of o₂,

then pop o₂ off the stack, onto the output queue;

• push o₁ onto the stack.

• If the token is a left parenthesis, then push it onto the stack.
• If the token is a right parenthesis:

• Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
• Pop the left parenthesis from the stack, but not onto the output queue.
• If the token at the top of the stack is a function token, pop it onto the output queue.
• If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

• When there are no more tokens to read:

• While there are still operator tokens in the stack:

• If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
• Pop the operator onto the output queue.

• Exit.

 

看一个详细的例子：

Input: 3 + 4 * 2 / ( 1 − 5 ) ^ 2 ^ 3 operator precedence associativity

^	4	Right
*	3	Left
/	3	Left
+	2	Left
−	2	Left

Token Action Output (in RPN) Operator Stack Notes

3	Add token to output	3
+	Push token to stack	3	+
4	Add token to output	3 4	+
*	Push token to stack	3 4	* +	* has higher precedence than +
2	Add token to output	3 4 2	* +
/	Pop stack to output	3 4 2 *	+	/ and * have same precedence
Push token to stack	3 4 2 *	/ +	/ has higher precedence than +
(	Push token to stack	3 4 2 *	( / +
1	Add token to output	3 4 2 * 1	( / +
−	Push token to stack	3 4 2 * 1	− ( / +
5	Add token to output	3 4 2 * 1 5	− ( / +
)	Pop stack to output	3 4 2 * 1 5 −	( / +	Repeated until "(" found
Pop stack	3 4 2 * 1 5 −	/ +	Discard matching parenthesis
^	Push token to stack	3 4 2 * 1 5 −	^ / +	^ has higher precedence than /
2	Add token to output	3 4 2 * 1 5 − 2	^ / +
^	Push token to stack	3 4 2 * 1 5 − 2	^ ^ / +	^ is evaluated right-to-left
3	Add token to output	3 4 2 * 1 5 − 2 3	^ ^ / +
end	Pop entire stack to output	3 4 2 * 1 5 − 2 3 ^ ^ / +

再看一个维基百科上的图例：（这个更好理解）

 

代码：

public class StringEval {	
	
	public final static String OPERATORS = "+-*/";
	public final static String BRACES = "()";
	
	public double evaluate(String expression, int x) {
		String[] exp = expression.replace(" ", "") //表达式可能有空格
				.replace("x", "*"+x) //把5x替换成5*2的形式
				.replace("y", "*y") //把5y替换成5*y的标准表达式
				.split("="); //把方程分解成左右两个表达式
		double f0 = parse(exp[0], 0);
		double f1 = parse(exp[0], 1);
		double g0 = parse(exp[1], 0);
		double g1 = parse(exp[1], 1);
		return (f0-g0)/((f0-g0)-(f1-g1));
	}
	
	//求单边表达式的值
	public int parse(String expression, int y) {
		Queue<String> rpn = new LinkedList<>(); //保存逆波兰表达式
		Stack<String> opstack = new Stack<>(); //保存运算符
		expression = expression.replace("y", ""+y).replace("(-", "(0-"); //注意左括号后面可能紧跟负数的情况
		//把所有运算符和左右括号当成分隔符，true表示把所有分隔符也一同输出出去
		StringTokenizer tokenizer = new StringTokenizer(expression, OPERATORS+BRACES, true); 
		while(tokenizer.hasMoreTokens()) {
			String token = tokenizer.nextToken();
			if(OPERATORS.contains(token)) { // it is an operator
				while(!opstack.isEmpty() && getPrecedence(opstack.peek()) >= getPrecedence(token)) {
					rpn.offer(opstack.pop());
				}
				opstack.push(token);
			} else if(BRACES.contains(token)) { 
				if(token.equals("(")) { // left brace
					opstack.push(token);
				} else { // right brace
					while(!opstack.isEmpty() && !"(".equals(opstack.peek())) {
						rpn.offer(opstack.pop());
					}
					opstack.pop();
				}
			} else { // it is a number
				rpn.offer(token);
			}
		}
		//注意，当我们遍历完表达式的时候，别忘了运算符stack里面还有东西呢。
		//一定要把它们全部pop到rpn队列里面去。
		while(!opstack.isEmpty()) { 
			rpn.offer(opstack.pop());
		}
		return evaluateRPN(rpn);
	}
	
	// 这个方法就是leetcode上很常规的求逆波兰达式的值
	public int evaluateRPN(Queue<String> rpn) {
		Stack<Integer> stack = new Stack<>(); //保存运算结果
		while(!rpn.isEmpty()) {
			String token = rpn.poll();
			if(OPERATORS.contains(token)) {
				int b = stack.pop();
				int a = stack.pop();
				if(token.equals("+")) {
					stack.push(a+b);
				} else if(token.equals("-")) {
					stack.push(a-b);
				} else if(token.equals("*")) {
					stack.push(a*b);
				} else if(token.equals("/")) {
					stack.push(a/b);
				}
			} else {
				stack.push(Integer.parseInt(token));
			}
		}
		return stack.pop();
	}
	
	//+-*/的运算符优先度，括号为0
	public int getPrecedence(String op) {
		if(op.equals("+") || op.equals("-")) {
			 return 1;
		} else if(op.equals("(")) { //注意，把(的优先度降为最低,因为这个方法只用来比较+-*/运算符的优先度，其他一概为0
			return 0;
		}
		return 2; // *和/的优先度相同，都为2
	}
	
	public static void main(String[] args) {
		StringEval eval = new StringEval();
		double y = eval.evaluate("3+2x+5y-(3+5x)=9-7y+2x", 3);
		System.out.println(y);
	}
}

以上代码仅仅能够解上面简单的问题，更全面（包括单运算符，三角函数，复数运算等）的解决方案的代码可以参考这里：

https://github.com/autsia/bracer/blob/master/src/main/java/com/autsia/bracer/BracerParser.java