本節主要講利用棧來實現一個程序中的成對出現的符號的檢測，完成一個類似編譯器的符號檢測的功能，采用的是鏈式棧。
一、問題的提出以及解決方法
1.假定有下面一段程序：
[cpp]
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int a[5][5];
int(*p)[5];
p = a[0];
printf ("%d", &a[3][3] - &p[3][3]);
}
這段程序中<>[]{}""這些符號都是成對出現的，假如不是成對出現，那麼我的程序在編譯的時候將會報錯。
2.我們即將要編寫的程序的主要目的就是來檢測程序中所出現的成對的符號是否都匹配。
3.解決方法：
假定我們要檢測的程序是上面的一段程序，那麼我們要把每一個字符都進行掃描，當程序遇見字母數字或者非成對的符號的時候直接忽略，當程序遇見了成對出現的符號的左符號時我們將左符號壓入棧。當掃描的過程中遇見右括號的時候，我們將棧頂元素彈出，進行匹配，如果匹配程序則繼續掃描，如果匹配失敗，則報錯。如果所有的都匹配成功，那麼棧為空且所有字符都掃描失敗。如果沒有匹配成功，那麼就是匹配失敗或者棧不為空。
4.算法框架
程序的算法框架如下：
二、具體程序的實現
1.程序的具體實現主要采用鏈式棧的數據結構，同時鏈式棧是通過復用單向鏈表來實現的，這些在點擊打開鏈接這篇博文中都有講解。所以算法實現的主要部分都是在主函數中實現的，也就是我所謂的上層函數。
2.首先采用在主函數中調用其他函數的方式來實現整個程序的運行。
[cpp]
int main()
{
char *a = "#include <stdio.h> #include <stdlib.h> int main () { int a[5][5]; int(*p)[5]; p = a[0]; printf (\"%d\", &a[3][3] - &p[3][3]); } ";
scan(a);
return 0;
}
定義的是一個字符串數組，將字符串數組的首地址傳遞給scan，這裡直接說字符串數組可能不太確切，關於字符和字符串的問題我始終沒有搞清楚，拖到了現在。
3.scan函數接部分
（1）scan函數接收的是字符串數組的指針
[cpp]
int scan (char *a)
（2）調用鏈式棧的函數進行建棧的操作，返回的是棧指針（因為以後只要涉及到棧的操作都要使用到棧指針）
[cpp]
LinkStack * stack = LinkStack_Create();
（3）因為程序的算法中已經說明，我們要不斷的掃描所有的字符，直到整個字符串結束，字符串結束的標志是'\0'，這裡采用while循環來實現
[cpp]
while (a[i] != '\0')
這裡通過傳遞進來的字符串數組的首地址，我們可以通過這個首地址來定義一個字符數組，然後進行操作。
（4）首先判定數組中的元素是否為成對匹配的符號的左符號，如果是左符號，那麼將左符號壓進棧。
[cpp]
if (left(a[i]) == 1)
{
LinkStack_Push(stack, (void*)(a + i));
}
在將左符號壓進棧的操作中，我們壓進棧的是數組元素的地址，這裡也是鏈式棧的可復用性的一個體現。
（5）接下來判定數組中的元素是否為成對匹配的符號的右符號，如果是右符號，那麼將棧頂元素彈出，並和相應的右符號進行比較。如果棧頂元素為空或者比較失敗，那麼將進行報錯。
[cpp]
if (right(a[i]) == 1)
{
char* bijiao = (char*)LinkStack_Pop(stack);
if ((bijiao == NULL) || !match(*bijiao, a[i]))
{
printf ("%c\n", a[i]);
ret = 0;
break;
}
}
（6）最後，成功的完成了檢測的條件是：棧頂為空且已經檢測到了最後一個結束符。
[cpp]
if (LinkStack_Top(stack) == NULL && a[i] == '\0')
{
printf ("編譯成功\n");
}
（7）程序執行的過程中還有其他幾個子函數
1)檢測是否為左符號的函數2)檢測是否為右符號的函數3)進行比較的函數
三、具體代碼
1.程序實現所復用的鏈式棧的詳細代碼請看點擊打開鏈接和點擊打開鏈接部分，這裡粘的是主函數的實現部分。由於是菜鳥，所以可能有的代碼部分寫的比較粗糙，望大家見諒。
2.主函數的實現部分代碼：
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include "1.h"
/*******************************************************************************
*函數名：left
*參數：char a 傳進來的數組元素
*返回值：int類型 如果是左側符號，那麼返回1，不是返回0
*功能：判斷傳進來的字符是否是左側字符
*******************************************************************************/
int left (char a)
{
int ret = 0;
switch(a)
{
case '<':
ret = 1;
break;
case '(':
ret = 1;
break;
case '[':
ret = 1;
break;
case '{':
ret = 1;
break;
case '\'':
ret = 1;
break;
case '\"':
ret = 1;
break;
default:
ret = 0;
break;
}
return ret;
}
/*******************************************************************************
*函數名：right
*參數：char a 傳進來的數組元素
*返回值：int類型 如果是右側符號，那麼返回1，不是返回0
*功能：判斷傳進來的字符是否是右側字符
*******************************************************************************/
int right (char a)
{
int ret = 0;
switch(a)
{
case '>':
case ')':
case ']':
case '}':
case '\'':
case '\"':
ret = 1;
break;
default:
ret = 0;
break;
}
return ret;
}
/*******************************************************************************
*函數名：right
*參數：char a 傳進來的數組元素
*返回值：int類型 如果是右側符號，那麼返回1，不是返回0
*功能：判斷傳進來的字符是否是右側字符
*******************************************************************************/
int match(char bijiao, char a)
{
int ret = 0;
int i = 0;
switch(bijiao)
{
case '<':
ret = (a == '>');
break;
case '(':
ret = (a == ')');
break;
case '[':
ret = (a == ']');
break;
case '{':
ret = (a == '}');
break;
case '\'':
ret = (a == '\'');
break;
case '\"':
ret = (a == '\"');
break;
default:
ret = 0;
break;
}
return ret;
}
/*******************************************************************************
*函數名：scan
*參數：char *a 傳進來的字符數組元素的地址
*返回值：int類型 如果是右側符號，那麼返回1，不是返回0
*功能：符號匹配算法的主要實現部分
*******************************************************************************/
int scan (char *a)
{
LinkStack * stack = LinkStack_Create();
int i = 0;
int ret = 0;
while (a[i] != '\0')
{
if (left(a[i]) == 1)
{
LinkStack_Push(stack, (void*)(a + i));
}
if (right(a[i]) == 1)
{
char* bijiao = (char*)LinkStack_Pop(stack);
if ((bijiao == NULL) || !match(*bijiao, a[i]))
{
printf ("%c\n", a[i]);
ret = 0;
break;
}
}
i++;
}
if (LinkStack_Top(stack) == NULL && a[i] == '\0')
{
printf ("編譯成功\n");
}
else
{
printf ("出現錯誤\n");
}
LinkStack_Destroy(stack);
return ret;
}
int main()
{
char *a = "#include <stdio.h> #include <stdlib.h> int main () { int a[5][5]; int(*p)[5]; p = a[0]; printf (\"%d\", &a[3][3] - &p[3][3]); } ";
scan(a);
return 0;
}
