Facebook&Uber interview - Eval Math Expression

题目就是计算表达式  1+2*3+4 = 11可以去搜parse mathematical expression,不考虑括号

 

Solution: 

use two arrays to store numbers and signs.

    nums = [1,2,3,4]
    signs = [+, *, +]
scan signs, when we meet  * or /,  and change * or / into +, corresponding nums changed to  [0, a*b] or [0, a/b]. for the example:
    nums  = [1,0,6,4]
    signs = [+,+,+]. 
then do (zigzag) sum.

public int calcExpression(String expr) {
	//正则表达式，运算符得escape，并且用[]包裹，表示或;否则会表示"+-*/"四个都匹配才行
	String[] digits = expr.split("[\\+\\-\\*\\/]");
	//[, +, *, -, /], 第一个是leading empty string, trailing empty string会自动去掉，而头部的不会
	String[] ops = expr.split("\\d+"); // 或者下面这种做法，移除第一个数字
//	String[] ops = expr.replaceFirst("\\d+", "").split("\\d+");
	
	int n = digits.length;
	int[] nums = new int[n];
	for(int i=0; i<n; i++) {
		nums[i] = Integer.valueOf(digits[i]);
	}
	for(int i=1; i<ops.length; i++) {//因为第0项是空字符串，所以从第一项开始
		if(ops[i].equals("*")) {
			nums[i] = nums[i-1] * nums[i];
			nums[i-1] = 0;
		} else if(ops[i].equals("/")) {
			nums[i] = nums[i-1] / nums[i];
			nums[i-1] = 0;
		} else if(ops[i].equals("-")) {
			//不能减，因为后面有可能是*/运算，比-的优先度高，所以要变成负数的加法，这样不影响优先级
			nums[i] = -nums[i]; 
		}
	}
	int sum = 0;
	for(int i=0; i<n; i++) {
		sum += nums[i];
	}
	return sum;
}

  

Solution 2:

可以用Shunting-Yard先转换成逆波兰表达式，然后再求值，这种方法比较通用，但是实现起来可能要花点时间。具体代码见本博客的如下文章。

http://yuanhsh.iteye.com/blog/2177104