Solution with recursive in java


  • 0
    I

    public List<Integer> diffWaysToCompute(String input) {

    	List<Integer> rst = new ArrayList<Integer>();
    	List<Integer> subrst = new ArrayList<Integer>();
    	List<Integer> number = new ArrayList<Integer>();
    	List<String> sign = new ArrayList<String>();
    	char[] charelement = input.toCharArray();
    	String entire="";
    	int in=0,is=0;
    	for(int i=0;i<charelement.length;i++)
    	{
    		if(charelement[i]!='+' && charelement[i]!='-' && charelement[i]!='*')
    			entire = entire+charelement[i];
    		else
    		{
    			number.add(Integer.parseInt(entire));
    			in++;
    			sign.add(String.valueOf(charelement[i]));
    			entire = "";
    		}
    		
    		if(i+1==charelement.length)
    			number.add(Integer.parseInt(entire));
    	}
    	
    	
    	    	if(number.size()==1)
    	{
    		rst.add(number.get(0));
    		return rst;
    	}
    	for (int i = 0; i< number.size()-1; i++){
    		subrst = action(0,i+1,number.size(),number,sign);
    		for(int j=0; j<subrst.size();j++){
    			rst.add(subrst.get(j));
    		}
    	}
    
    	return rst;
    }
    
    public List<Integer> action(int s, int m, int e, List<Integer> number, List<String> sign){
    	
    	List<Integer> left = new ArrayList<Integer>(),right=new ArrayList<Integer>(),result=new ArrayList<Integer>();
    	List<Integer> lefts = new ArrayList<Integer>(),rights=new ArrayList<Integer>();
    	int signindex = 0;
    	
    	if(s+1>=m){lefts.add(number.get(s));signindex=s;}
    	else{
    	for(int i = s+1; i<m; i++){
        	List<Integer> leftss = new ArrayList<Integer>();
        	signindex=i;
        	leftss=action(s,i,m,number,sign);
        	for(int j = 0; j<leftss.size();j++){
        	lefts.add(leftss.get(j));
        	}
    	}
    	}
    	
    	if(m>=e-1){rights.add(number.get(e-1));}
    	else{
    	for(int i=m+1; i<e; i++){
    			List<Integer> rightss = new ArrayList<Integer>();
    			rightss=action(m,i,e,number,sign);
            	for(int j = 0; j<rightss.size();j++){
                	rights.add(rightss.get(j));
                	}
    	}
    	}
    		
        	for(int j =0; j< lefts.size();j++){
        			for(int x=0;x<rights.size();x++)
        			{
        				result.add(calculate(lefts.get(j),rights.get(x),sign.get(signindex)));
        			}
    	} 	
    	
    	return result;
    	
    }
    
    public int calculate(int x, int y, String sign){
    	switch (sign){
    	case "+": return x+y; 
    	case "-": return x-y;
    	case "*": return x*y;
    	}
    	return 0;
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.