3128625_mle.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main
{
	class node
	{
		int pos;
		int num1, num2;
		String exp;
	}
	
	public static void main(String [] args)
	{
		new Main().solve();
	}
	
	private void solve()
	{
		Scanner cin = new Scanner (System.in);
		String exp;
		int res;
		LinkedList queue = new LinkedList();
		int cas = 0;
		
		lable:
		while(true)
		{
			cas++;
			exp = cin.next();
			if(exp.compareTo("0=0")==0)
			{
				break;
			}
			res = Integer.parseInt(exp.substring(1+exp.indexOf('=')));
			node t = new node();
			t.num1 = t.num2 = t.pos = 0;
			t.exp = "";
			queue.clear();
			queue.addLast(t);
			int [] sum = new int [300];
			for(int i = exp.indexOf('=')-1; i >= 0; i--)
			{
				sum[i] = sum[i+1]+(int)(exp.charAt(i)-'0');
			}
			while(!queue.isEmpty())
			{
				t = (node)queue.removeFirst();
				if(t.num1+t.num2+sum[t.pos]>res)
				{
					continue;
				}
				//System.out.println(t.exp+" "+t.num1+" "+t.num2+" "+t.pos);
				if(t.exp.length()==0)//||t.exp.charAt(t.exp.length()-1)=='+')
				{
					t.exp += exp.charAt(t.pos);
					t.num2 = (int)(exp.charAt(t.pos++)-'0');
					if(t.num1 + t.num2 <= res)
					{
						queue.addLast(t);
					}
				}
				else
				{
					if(t.exp.charAt(t.exp.length()-1)=='+')
					{
						if(exp.charAt(t.pos)!='0')
						{
							t.exp += exp.charAt(t.pos);
							t.num2 = (int)(exp.charAt(t.pos++)-'0');
							if(t.num1 + t.num2 <= res)
							{
								queue.addLast(t);
							}
						}
					}
					else
					{
						node p = new node();
						p.exp = t.exp;
						p.num1 = t.num1;
						p.num2 = t.num2;
						p.pos = t.pos;
						if(exp.charAt(p.pos)!='=')
						{
							p.exp += exp.charAt(p.pos);
							p.num2 *= 10;
							p.num2 += (int)(exp.charAt(p.pos++)-'0');
							if(p.num1+p.num2 <= res)
							{
								queue.addLast(p);
							}
						}
						if(exp.charAt(t.pos)!='=')
						{
							t.exp += "+";
							t.num1 += t.num2;
							t.num2 = 0;
							//System.out.println("asd = "+t.num1+" "+t.num2);
							if(t.num1 + t.num2 <= res)
							{
								queue.addLast(t);
							}
						}
						else
						{
							t.exp += '=';
							if(t.num1 + t.num2 ==res)
							{
								System.out.println(cas+". "+t.exp+res);
								continue lable;
							}
						}
					}
				}
			}
			System.out.println(cas+". "+"IMPOSSIBLE");
		}
	}
}