前言

笔试结果应该是挂了。这也没什么好说的。只能怪自己太傻逼了。唉。但是感觉要是就这样心里总是感觉很不愉快。所以我就写一下了这文章了感慨一下了。事先说明，本人使用的C#语言。文章中的代码部分都是C#。

第一题程序填空题

阅读下列程序说明和 C#程序，将应填入__(n)__处的字句写在答题纸的对应栏内。

【程序说明】

应用计算机处理日常事务或者是编写程序的时候，经常需要用到带有通配符的字符串匹配。比如：linux命令行下输入，ls .txt 就是列出当前目录下所有的结尾是.txt的文件。下面一段函数实现了带有$和*两种通配符的字符串的匹配功能。其中：$表示长度大于0的数字串,表示任意长度的字符串。要求：按照自己对于算法的理解填写该函数的5个空白。

请注意：必须是完全匹配才能返回true，比如1.txt, a.txt可以匹配*.txt, 2.tx或者

2.txta不能匹配*.txt。函数的参数与返回值的说明请参见函数的注释。

// 功能描述:

表达式是否匹配成功, $表示长度大于 0 的数字串，*表示任意长的字符串

// 输入参数:

字符串 rule 表示规则;

字符串 str 表示待匹配的字符串;

// 返回值:true:匹配成功; false: 匹配失败

程序填空代码如下：

public static bool isRegularMatching(string rule, string str)
{
    int lRule = rule.Length;
    int lStr = str.Length;
    int iRule = 0;
    int iStr = 0;
    while (iRule < lRule && iStr < lStr)
    {
        switch (_____(1)_____)
        {
            case '*':
                {
                    iRule += 1;
                    if (iRule >= lRule)
                    {
                        return true;
                    }
                    else
                    {
                        for (int i = iStr; i < lStr; i++)
                        {
                            if  (_____(2)_____)
                            {
                                return true;
                            }
                        }
                    }
                }
                break;
            case '$':
                {
                    if (_____(3)_____)
                    {
                        return false;
                    }
                    while ((iStr < lStr) && (str[iStr] >= '0') && (str[iStr] <= '9'))
                    {
                        iStr += 1;
                    }
                    iRule += 1;
                    break;
                }
            default:
                {
                    if (rule[iRule] != str[iStr])
                    {
                        _____(4)_____;
                    }
                    iRule += 1;
                    iStr += 1;
                    break;
                }
        }
    }
    if (iRule < lRule && iStr >= lStr)
    {
        if (rule[iRule] == '*')
        {
            return true;
        }
    }
    else
    {
        return _____(5)_____;
    }
    return false;
}

我的答案：

(1) rule[iRule]
(2) String.Equals(str.Substring(i),rule.Substring(iRule)) 
(3) str[iStr] < '0' || str[iStr] > '9'
(4) return false
(5) iStr >= lStr

以下是我个人的分析（有错可以指正，毕竟我笔试挂了）。

第一个空是填写switch中的内容。从下面的case中我们可以得知两个信息：1. 我们要比较的是字符。2.这个比较中会出现‘*’和‘$’符号。首先这个字符一定是字符串rule和str中的字符。但只有rule是一定会出现‘\*'和’$‘这两个字符。所以第一个空填rule[iRule]。（虽然我感觉应该没什么不会但是我还是写一下吧）

第二个空是填写一个条件。当rule字符串中的字符匹配到’*‘时进入下面的这段代码：

if (iRule >= lRule)
{
    return true;
}
else
{
    for (int i = iStr; i < lStr; i++)
    {
        if  (_____(2)_____)
        {
            return true;
        }
    }
}

第一行判断’*‘字符是否为rule字符串中的最后一个字符。如果是那依照’*’字符可以匹配任意字符长度则str后面是什么样的字符都符合条件，那么直接返回true。否则就进入这个填空的代码。这里有一个对字符串str剩下的字符进行的for循环。当代码执行到这里其实就告诉了我们一个信息：‘*’字符后面还有字符未匹配。按照‘*'可以匹配任意字符串的特性。这就意味着只要我们能在字符串str剩下未匹配到的字符中得到一个字符串，这个字符串可以和'*'字符后面字符串一样那么这就符合条件返回true。我们可以使用C#使用String.Substring()函数得到我们想要的字符串。同时C#提供了字符串的比较函数String.Equals()进行字符串的比较。对于字符串rule来说，我们需要的子字符串就是rule.Substring(iRule)。对于字符串str来说，因为我们不知道什么时候获得我们需要的字符串所以这里使用了for循环得到从此处开始到末尾的所有可能的子字符串——str.Substring(i)。最后我们再进行比较。故第二个空填

String.Equals(str.Substring(i),rule.Substring(iRule))。

第三个空是填写一个条件。当rule字符串中的字符匹配到’$‘时进入下面的这段代码：

if (_____(3)_____)
{
    return false;
}
while ((iStr < lStr) && (str[iStr] >= '0') && (str[iStr] <= '9'))

'$'字符匹配长度大于0的数字串。这里我们可以提出'$'的两个条件：1.长度大于0。2.是数字字符串。这个条件是一开始的条件并且只要满足这个条件那么就直接返回false。而这个条件下面的代码才是对str字符串进行数字的评判。那么前面的条件就应该是长度的判断。那么只要满足就直接返回false。那么只能是一种情况那就是判断到这里时str已经没有字符可以进行匹配了。所以第三个空填iStr >= lStr。下面的循环是对str字符串进行数字评判的。但是如果此时str对比的第一个数据为非数字即str[iStr] < '0' || str[iStr] > '9'。那么会直接退出循环而iRule却会加一。所以一开始没有检测出来这个问题那么会让rule字符串的'$'字符失去其原本的用途。所以这一空答案应该为str[iStr] < '0' || str[iStr] > '9'。（感谢大家提出错误，那次面试我就没有通过，所以答案也不一定正确。如果还有错的地方欢迎大家纠错。）

第四个空是满足条件下的一个语句。当此时的字符既不是’*‘也不是'$'时进入下面的代码：

if (rule[iRule] != str[iStr])
{
    _____(4)_____;
}
iRule += 1;
iStr += 1;

这个判断条件就是同一个时刻rule字符串和str字符串下的字符是否不相同。首先我们要明白这个功能就是要匹配字符串。那么当同一时刻两个字符串下的字符不相同就是这个两个字符串不能匹配。所以第四空填return false（因为有分号了所以我们可以不用加，但是加了也没什么事。反正不会报错，但是对不对还是看改卷的人。）。

第五个空返回一个值。那么这里显然就是true或者是false选一个了。这段代码是整个循环正常结束并且不满足iRule < lRule && iStr >= lStr条件后才进入。循环正常结束的条件为iRule < lRule && iStr < lStr。这就意味着当执行到这句代码时，str或者rule字符串已经全部匹配完了。而后面加上的条件是判断未匹配完的字符串是否为rule字符，反之有两种情况：1.str全部匹配完。2.str还有剩余为匹配字符。如果str全部匹配完了，这就意味着str和rule一起到达终点那么就是符合条件返回true。那么如果str还有未匹配字符那么就应该返回false。所以第五空填iStr >= lStr。

第二题程序编码题

输入任意一种物质，要求输出其每种元素的数量。

比如

输入 CaCO3，其组成分别为 Ca：1，C：1，O：3，输出 Ca1C1O3

输入 Fe2(SO4)3，其组成分别为 Fe：2，S：3，O：12，输出 Fe2S3O12

（注意：元素名称首字母大写，剩余字母都小写；括号括起来表示括号中的结构作为整体出现多少次）

代码实现：

public static string CountElement(string data)
{
    StringBuilder ans = new StringBuilder();//进行字符串拼接
    Dictionary<string, int> element = new Dictionary<string, int>();//记录元素和其对应的次数
    List<string> lst = new List<string>();//按顺序记录元素
    List<int> lstNum = new List<int>();//按顺序记录每次元素在此刻出现的次数
    Stack<int> s = new Stack<int>();//存储括号开始的位置
    for(int i = 0; i < data.Length; ++i)
    {
        if(data[i]>='A'&& data[i] <= 'Z')
        {
            int tmp = i;
            ++i;
            while(i < data.Length &&(data[i]<='z'&& data[i] >='a'))
            {
                ++i;
            }
            string str = data.Substring(tmp, i - tmp);
            if(!element.ContainsKey(str))
                    {
                        element.Add(str, 0);                        
                    }
            lst.Add(str);
            if (i < data.Length && (data[i] >= '0' && data[i] <= '9'))
            {
                int sum = 0;
                while (i < data.Length && (data[i] >= '0' && data[i] <= '9'))
                {
                    sum = sum * 10 + data[i] - '0';
                    ++i;
                }
                element[str] += sum;
                lstNum.Add(sum);
            }
            else
            {
                element[str] += 1;
                lstNum.Add(1);
            }
            --i;//回档，不然会跳过一个字符
        }
        else if(data[i] == '(')//记录下括号开始的元素下标
        {
            s.Push(lst.Count);
        }
        else if(data[i]  == ')')//表示一个括号结束了可以进行计算了
        {
            ++i;
            int sum;
            if (i < data.Length && (data[i] >= '0' && data[i] <= '9'))
            {
                sum = 0;
                while (i < data.Length && (data[i] >= '0' && data[i] <= '9'))
                {
                    sum = sum * 10 + data[i] - '0';
                    ++i;
                }
            }
            else
            {
                continue;
            }
            sum--;
            for(int j = s.Pop(); j < lst.Count; ++j)
            {
                element[lst[j]] += sum * lstNum[j];
                lstNum[j] += sum * lstNum[j];
            }
            --i;//回档，不然会跳过一个字符
        }
    }
    for(int i = 0; i < lst.Count; ++i)
    {
        if(element.ContainsKey(lst[i]))//元素拼接一次就够了，其他地方出现的相同元素就不管它了。
        {
            ans.Append(lst[i] + element[lst[i]]);
            element.Remove(lst[i]);
        }
    }
    return ans.ToString();
}

唉，没什么好说的。这就是暴力解。

前言

第一题 程序填空题

第二题 程序编码题

第一题程序填空题

第二题程序编码题