C语言数据结构----栈的应用（程序的符号匹配检测）
本节主要讲利用栈来实现一个程序中的成对出现的符号的检测，完成一个类似编译器的符号检测的功能，采用的是链式栈。一、问题的提出以及解决方法
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 '\'':
补充：软件开发 , C语言 ,上一个：C模块回调Lua函数的两种方法
下一个：C语言对象化编程
- 更多C/C++疑问解答：
- 关于c++的cout输出的问题。
- 在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
- c++数据结构内部排序问题，整数排序
- 2012九月计算机二级C语言全国题库，，急求急求
- 如果assert只有一个字符串作为参数，是什么意思呢?
- C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
- 为什么用结构体编写的程序输入是，0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
- 为什么这个程序求不出公式？
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊