LeetCode -- Expression Add Operators

LeetCode -- Expression Add Operators

題目描述：


Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.


Examples:
123, 6 -> [1+2+3, 1*2*3]
232, 8 -> [2*3+2, 2+3*2]
105, 5 -> [1*0+5,10-5]
00, 0 -> [0+0, 0-0, 0*0]
3456237490, 9191 -> []


給定一串數，在數字中間插入操作符構成表達式，計算表達式，使得結果等於target。


思路：
由於要考慮多位數的情況，對於數組nums,需要對每一位nums[i]（其中i∈[0,n)）進行字符串截取: nums.Substr[i,i+1],nums.Substr[i,i+2]...nums.Substr[i,i+n-1]，然後對每個字串DFS。


一開始想DFS出所有表達式然後逐個計算的，可是表達式計算本身需要字符串遍歷，使用棧和隊列求解，因此這個方案不可取；
而是需要在遍歷過程中立即計算，對於這個方案，要考慮到不同操作符+,-和*計算時的優先級問題。


1.對於+和-可以直接計算，然後從下一位作為起始進入DFS；
2.而對於*並且之前為+或-，需要恢復上一次+或-的計算值，先計算當前的*，然後再執行之前運算的逆運算。


其次，需要考慮當字符串長度大於1並且首字符為0的情況，直接返回。


 


實現代碼：

public class Solution {
    public IList AddOperators(string num, int target) 
    {
        var result = new List();
    	Dfs(target, num, 0, 0, '+', , ref result);
    	
    	return result;
    }
    
private void Dfs(int target, string num, long current , long prevNum, char prevOp, string s, ref List result)
{
   if (num == )
   {
   		if(current == target){
			result.Add(s);
		}
		return;
   }
   
	for(var i = 1 ;i <= num.Length; i++)
	{
		var str = num.Substring(0, i);
		
		if(str.Length > 1 && str[0] == '0'){
			return;
		}
		
		long n = long.Parse(str);
		
		var left = num.Substring(i, num.Length - i);
		if(s == ){
			Dfs(target, left, n, n,'+', str, ref result);
			continue;
		}
		//Console.WriteLine(str + ,+index);
		
		Dfs(target, left, current + n, n,'+', s +++str, ref result);
		Dfs(target, left, current - n, n,'-', s +-+str, ref result);
		
		// for '*' operator , execute reverse operation for previous operation
		if(prevOp == '+'){
			Dfs(target, left, current - prevNum + prevNum * n,  prevNum * n, prevOp, s +*+str, ref result);
		}
		else if(prevOp == '-'){
			Dfs(target, left, current + prevNum - prevNum * n,  prevNum * n, prevOp, s +*+str, ref result);
		}
		else{
		    Dfs(target, left, current * n, n, prevOp, s +*+str, ref result);
		}


	}
}


}