function parse_phone_format_internal(format, start) {
    flen = format.length;

    var required = 0;
    var optional = 0;
    var prefix = "";
	var digits = "";
    for (i = start; i < flen; i++) {
        var c = format.charAt(i);
		if (start > 0 && (c == '|' || c == '}'))
			break;
        switch(c) {
        case '\\':
            i++;
            break;
        case 'x':
        case 'z':
        case 'n':
            optional++;
            break;
        case 'X':
        case 'Z':
        case 'N':
            required++;
            break;
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
			digits += c;
            required++;
            break;
		case '[':
			required++;
			while (i < flen && format.charAt(i) != ']')
				i++;
			break;
		case '{':
			var inner_required = 0;
			var inner_optional = 0;
			do
			{
				var inner_result = parse_phone_format_internal(format, i+1);
				if (inner_required == 0 && inner_optional == 0)
				{
					inner_required = inner_result['required'];
				}
				else if (inner_result['required'] < inner_required)
				{
					inner_optional += inner_required - inner_result['required'];
					inner_required = inner_result['required'];
				} else {
					inner_result['optional'] += inner_result['required'] - inner_required;
				}
				if (inner_result['optional'] > inner_optional)
					inner_optional = inner_result['optional'];
				i = inner_result['end'];
			} while (i < flen && format.charAt(i) != '}');
			required += inner_required;
			optional += inner_optional;
			break;
		case '?':
		case '!':
			optional = 0;
			required = 0;
			prefix = digits;
            break;
        }
    }

	var result = new Array();
	result['required'] = required;
	result['optional'] = optional;
	result['prefix'] = prefix;
	result['end'] = i;

    return result;
}

function parse_phone_format(format)
{
	return parse_phone_format_internal(format, 0);
}

function isValidPhone(phone, format)
{
	var fmt = parse_phone_format(format);
	var required = fmt['required'];
	var optional = fmt['optional'];
	var prefix = fmt['prefix'];

	var digits = "0123456789";

	var stripped = "";
	for (i = 0; i < phone.length; i++)
	{
		var c = phone.charAt(i);
		if (digits.indexOf(c,0) != -1)
			stripped += c;
	}

	var preLen = prefix.length;
	if (preLen > 0 && stripped.substr(0,preLen) == prefix)
		stripped = stripped.substr(preLen);

	if (stripped.length < required)
		return false;

	if (stripped.length <= required + optional)
		return stripped;

	return false;
}