這一期的內(nèi)容已經(jīng)過(guò)半议街，部分同學(xué)開(kāi)始覺(jué)得吃力割捅。如果這時(shí)候放棄奶躯，那前邊的努力就白費(fèi)了。今天我們來(lái)看看上一篇中的課后題亿驾。

1. 題目

給出一組代數(shù)表達(dá)式嘹黔，請(qǐng)編程判斷出他們的括號(hào)是否配對(duì)正確。

10
[a+b)-(d+e]
(a+b))+((d-e)
(a+b)-[c+d
[a+(b+c)]*(a+b]
(a-1+b)-(b+c)
x-[a*(b+c))]
a+(b+c+(d-(e+m))
a+b+[c-d*e-(a-b)-c]
[a+b-d]+e）
[a-(b+)+[d-a]-b]

第一行中的10表示共有10個(gè)表達(dá)式需要判斷莫瞬。下面的每一行有一個(gè)表達(dá)式儡蔓。要求把這組數(shù)據(jù)原樣保存在文件input.txt中，通過(guò)讀文件的方式讀入數(shù)據(jù)完成判斷疼邀。

原題只有5個(gè)表達(dá)式喂江，這里我又加入了5個(gè)新的，有一些特殊的情況需要添加旁振。

2. 分析

這道題從功能上講需要做兩件事：

• 第一件：把保存在input.txt文件中的數(shù)據(jù)讀入程序中
• 第二件：掃描每行字符串获询，判斷是否所有的括號(hào)都匹配

是不是看起來(lái)沒(méi)那么復(fù)雜呢？下面我們就來(lái)看如何實(shí)現(xiàn)這兩個(gè)功能拐袜。

3. 讀數(shù)據(jù)

3.1 基本方法

說(shuō)到讀數(shù)據(jù)吉嚣，我們本能地想到C語(yǔ)言教科書(shū)中文件操作的那一章，用基本的打開(kāi)文件蹬铺，讀取數(shù)據(jù)的方法就能解決問(wèn)題尝哆。這個(gè)方法完全正確。如果你對(duì)文件的基本操作還有問(wèn)題甜攀，請(qǐng)參考我之前的文章21天C語(yǔ)言代碼訓(xùn)練營(yíng)（第十五天）秋泄。

這里分享一段Aha_斌提交作業(yè)中的代碼，請(qǐng)參考规阀。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//用宏去存儲(chǔ)文件路徑
#define FILE_PATH "input.txt" 

void main()
{
    FILE *fp;
    char str[50];//存儲(chǔ)從文件讀取的字符串
    int strNum;
    char ch;
    if ((fp = fopen(FILE_PATH, "r")) == NULL)
    {
        printf("System can`t find this file!\n");
        exit(0);
    }
    fscanf(fp, "%d", &strNum);//讀取要比較表達(dá)式的個(gè)數(shù)
    fscanf(fp, "%c", &ch);//讀取第一行的換行符
    while (strNum--)//當(dāng)表達(dá)式?jīng)]有比較完
    {
        fgets(str, 50, fp);//讀取一個(gè)表達(dá)式
        
        // 這里加入判斷str是否符合要求的代碼
    }
    system("PAUSE");
}

3.2 文件流重定向方法

這里我要介紹另外一種方法恒序，這是ACM比賽中常用的一種數(shù)據(jù)讀取方法。它的特點(diǎn)是把打開(kāi)的文件重定向到標(biāo)準(zhǔn)輸入流中姥敛，這樣我們就可以像讀取鍵盤(pán)輸入數(shù)據(jù)一樣讀入數(shù)據(jù)奸焙。

先看一下這段代碼：

int main()
{
    int n, i;
    int ret;
    char str[MAX_SIZE];
    FILE* fp;
    freopen_s(&fp, "input.txt", "r", stdin);
    if (fp == NULL)
    {
        ret = 0;
    }

    scanf("%d", &n);
    printf("%d\n", n);

    for (i = 0; i < n; i++)
    {
        scanf("%s", str);
        printf("%s\n", str);
    }
}

這段代碼的功能是把input.txt文件中的內(nèi)容讀入程序，之后打印在屏幕上彤敛。很容易發(fā)現(xiàn)，我們?cè)诖蜷_(kāi)文件并沒(méi)有使用大家熟悉的fopen()函數(shù)數(shù)了赌，而是用了這句話(huà)：

freopen_s(&fp, "input.txt", "r+", stdin);

這句話(huà)的作用是把input.txt文件用只讀方式打開(kāi)墨榄，之后重定向到stdin表示的標(biāo)準(zhǔn)輸入流中。當(dāng)fp為空時(shí)勿她，表示此文件不存在袄秩。在這之后，我們可以用scanf()函數(shù)像讀取鍵盤(pán)輸入那樣讀取文件內(nèi)容了。是不是很神奇之剧。

如不需要得到文件指針郭卫，我們還可以寫(xiě)成這樣：

freopen("input.txt", "r+", stdin);

這個(gè)形式是標(biāo)準(zhǔn)庫(kù)函數(shù)的寫(xiě)法。

我們來(lái)看看執(zhí)行結(jié)果：

4. 判斷括號(hào)匹配

4.1 常見(jiàn)方法

完成了作業(yè)的同學(xué)都采用了一種最容易想到的方法背稼，那就是分別統(tǒng)計(jì)[]()四個(gè)符號(hào)的個(gè)數(shù)贰军，之后比較個(gè)數(shù)是否相同，如果相同就說(shuō)明匹配蟹肘，如果不相同就說(shuō)明不匹配词疼。

但是這種方法有很多bug，比如))((這種問(wèn)題帘腹。還有我新加入的幾個(gè)公式都會(huì)判斷錯(cuò)誤贰盗。不過(guò)也不是完全不可能，只不過(guò)需要另外添加一些約束條件阳欲，多寫(xiě)一些代碼舵盈。有興趣的同學(xué)可以參考完成作業(yè)的代碼。

4.2 逐個(gè)匹配法

我們這里介紹一種大家沒(méi)有想到的算法球化。這個(gè)算法的思想是這樣的书释，從前到后遍歷表達(dá)式，忽略字母和運(yùn)算符赊窥，只關(guān)注括號(hào)爆惧。一旦遇到匹配成功的括號(hào)就整對(duì)刪掉，如果最后剩下半個(gè)括號(hào)（無(wú)論是左半邊還是右半邊）锨能，說(shuō)明不匹配扯再，否則就說(shuō)明是匹配的。

如圖址遇，我們利用一個(gè)數(shù)組來(lái)完成它熄阻，具體分為三個(gè)動(dòng)作：

• 遇到左括號(hào)寫(xiě)入數(shù)組
• 遇到右括號(hào)拿它和數(shù)組中最后一個(gè)括號(hào)做匹配
• 匹配成功兩個(gè)括號(hào)都刪除，繼續(xù)后面的動(dòng)作
• 匹配失敗直接跳出倔约，返回失敗

我們看看代碼如何實(shí)現(xiàn)：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define MAX_SIZE 100

char g_arr[MAX_SIZE];
int g_index;

int CheckChar(char ch)
{
    if (ch == '(')
    {
        g_arr[g_index++] = ch;
    }
    else if (ch == '[')
    {
        g_arr[g_index++] = ch;
    }
    else if (ch == ')')
    {
        if (g_arr[g_index - 1] == '(')
        {
            g_index--;
        }
        else
        {
            return 0;
        }
    }
    else if (ch == ']')
    {
        if (g_arr[g_index - 1] == '[')
        {
            g_index--;
        }
        else
        {
            return 0;
        }
    }
    else
    {
        // Do nothing
    }

    return 1;
}

int Check(char* pStr)
{
    int i;

    g_index = 0;
    
    for (i = 0; pStr[i] != '\0'; i++)
    {
        if (CheckChar(pStr[i]) == 0)
        {
            return 0;
        }
    }

    if (g_index == 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

5. 匹配算法分析

我們來(lái)仔細(xì)分析一下這段代碼秃殉，它一共做了三件事。

5.1 定義數(shù)據(jù)結(jié)構(gòu)

#define MAX_SIZE 100

int g_arr[MAX_SIZE];
int g_index;

數(shù)據(jù)結(jié)構(gòu)非常簡(jiǎn)單浸剩，就是一個(gè)大小為MAX_SIZE的一維字符數(shù)組钾军。我們用g_index這個(gè)變量保存這個(gè)數(shù)組的當(dāng)前下標(biāo)，也就是按順序存入內(nèi)容時(shí)最左邊的那個(gè)空位绢要。

這個(gè)數(shù)組的使用方法如圖所示吏恭，每插入一個(gè)字符g_index加1，標(biāo)記為一個(gè)新的空白位置重罪。刪除時(shí)動(dòng)作相反樱哼。

注意哀九，這里使用全局變量只是為了方便大家理解，真正的項(xiàng)目中并不鼓勵(lì)用全局變量的方式設(shè)計(jì)代碼搅幅。

5.2 判斷字符

int CheckChar(char ch)

這個(gè)函數(shù)主要負(fù)責(zé)使用g_arr進(jìn)行匹配動(dòng)作阅束。把表達(dá)式中的每個(gè)字符傳遞給參數(shù)ch，它會(huì)負(fù)責(zé)判斷這個(gè)符號(hào)是否符合要求茄唐。如果拿到的符號(hào)不是括號(hào)息裸，直接忽略掉。如果是左括號(hào)就存入數(shù)組琢融，如果是右括號(hào)就和數(shù)組中最后一個(gè)括號(hào)（g_arr[g_index - 1]）做匹配界牡。

這里重點(diǎn)要說(shuō)的是匹配成功后，需要把數(shù)組中最后一個(gè)字符刪掉漾抬。只用了一句話(huà)：

g_index--;

這句話(huà)用到了一個(gè)重要的思想宿亡，刪除最后一個(gè)元素只需要更新當(dāng)前下標(biāo)，并不用真的把那一位改成0纳令。我們?cè)诰S護(hù)g_arr這個(gè)數(shù)組時(shí)挽荠，其實(shí)看的是g_index的值，我們定義了它永遠(yuǎn)標(biāo)記的是第一個(gè)空著的可用位置平绩。如果g_index標(biāo)記了一個(gè)有內(nèi)容的位置圈匆，那么下一次寫(xiě)入時(shí)會(huì)通過(guò)g_arr[g_index++] = '(';這樣的語(yǔ)句把這塊內(nèi)容覆蓋掉。所以捏雌，更新g_index的方法和刪除這塊內(nèi)容的效果是完全一樣的跃赚。

5.3 處理字符串

int Check(char* pStr)

這個(gè)函數(shù)是為了方便我們循環(huán)處理每個(gè)表達(dá)式字符串。只要把表達(dá)式字符串傳遞給參數(shù)pStr性湿，它會(huì)通過(guò)調(diào)用CheckChar()函數(shù)逐個(gè)分析每個(gè)字符纬傲，直到判斷出結(jié)果。

函數(shù)最前面肤频，有這樣一行代碼：

g_index = 0;

按照前面講過(guò)的理論叹括，它其實(shí)完成的是g_arr數(shù)組清空的動(dòng)作。是不是很方便宵荒。

6. 功能整合

最后汁雷，我們需要把從文件中讀入的數(shù)據(jù)通過(guò)前面的功能進(jìn)行處理。代碼如下：

int main()
{
    int n, i;
    int ret;
    char str[50];
    FILE* fp;
    freopen_s(&fp, "input.txt", "r+", stdin);
    if (fp == NULL)
    {
        ret = 0;
    }

    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        scanf("%s", str);
        ret = Check(str);
        printf("%d\n", ret);
    }
}

執(zhí)行結(jié)果如下：

7. 課后作業(yè)

編程統(tǒng)計(jì)出input.txt文件保存的文章中报咳，每個(gè)單詞出現(xiàn)的次數(shù)侠讯。文章內(nèi)容如下：

In this chapter we will be looking at files and directories and how to manipulate them. We will learn how to create files, open them, read, write and close them. We'll also learn how programs can manipulate directories, to create, scan and delete them, for example. After the last chapter's diversion into shells, we now start programming in C.
Before proceeding to the way UNIX handles file I/O, we'll review the concepts associated with files, directories and devices. To manipulate files and directories, we need to make system calls (the UNIX parallel of the Windows API), but there also exists a whole range of library functions, the standard I/O library (stdio), to make file handling more efficient.

這段文字來(lái)自網(wǎng)絡(luò)。為了統(tǒng)計(jì)更有意義少孝，加入兩個(gè)條件：

• 統(tǒng)計(jì)過(guò)程中不考慮空格和標(biāo)點(diǎn)符號(hào)
• 不區(qū)分大小寫(xiě)（可以把所有字母轉(zhuǎn)成小寫(xiě)后參與統(tǒng)計(jì)）

我是天花板继低，讓我們一起在軟件開(kāi)發(fā)中自我迭代。
如有任何問(wèn)題稍走，歡迎與我聯(lián)系袁翁。

上一篇：天花板編程手把手計(jì)劃-第1期-第5天