一、算法思路
1、从第一个字符开始扫描；
2、当遇到普通字符时忽略，当遇到左符号时压入栈中；
3、当遇到有字符时，从栈中弹出栈顶符号；
4、进行匹配：
①匹配成功：继续读入下一个字符；
②匹配失败：立即停止，并报错；
5、结束：
①成功：所有的字符扫描完毕，且栈为空。
②失败：匹配失败或所有的字符扫描完毕但栈非空。
二、算法框架：
scanner(string)
{
创建栈S；
i = 0；
while( string[i] != '\0' )
{
if( string[i]为左符号 )
{
push(S,string[i]);
}
if(string[i]为右符号)
{
c = pop[S];
if(c与string[i]不匹配)
{
报错，立即停止循环；
}
}
i++;
}
if( (size(S) == 0) && (string[i] == '\0') )
{
匹配成功；
}
else
{
匹配失败，报错；
}
}
三、代码实现：
#include <stdio.h>
#include <stdlib.h>
#include "LinkStack.h" //栈
#include "Scanner.h"
//判断是否为左符号
int Isleft(char c)
{
int ret = 0;
switch(c)
{
case '<' :
case '(' :
case '[' :
case '{' :
case '\'' :
case '\"' :
ret = 1;
break;
default :
ret = 0;
break;
}
return ret;
}
//判断是否为右符号
int Isright(char c)
{
int ret = 0;
switch(c)
{
case '>' :
case ')' :
case ']' :
case '}' :
case '\'' :
case '\"' :
ret = 1;
break;
default :
ret = 0;
break;
}
return ret;
}
//判断是否匹配
int Ismatch(char right, char left)
{
int ret = 0;
switch(right)
{
case '>' :
ret = (left == '<');
break;
case ')' :
ret = (left == '(');
break;
case ']' :
ret = (left == '[');
break;
case '}' :
ret = (left == '{');
break;
case '\'' :
ret = (left == '\'');
break;
case '\"' :
ret = (left == '\"');
break;
default :
ret = 0;
break;
}
return ret;
}
int Scanner(const char* code)
{
LinkStack* stack = LinkStack_Create();
int ret = 0; //定义一个返回值
int i = 0; //定义一个循环变量
while(code[i] != '\0')
{
if( Isleft(code[i]) )
LinkStack_Push(stack, (void*)(code + i));
if( Isright(code[i]) )
{
char* left = (char*)LinkStack_Pop(stack);
if( (left == NULL) || !Ismatch(code[i], *left) )
{
printf("%c dose not match!\n", code[i]);
ret = 0;
break;
}
}
i++;
}
if( (LinkStack_Size(stack) ==0) && (code[i]) == '\0' )
{
printf("Succeed!\n");
ret = 1;
}
else
{
printf("Invialid\n");
ret = 0;
}
LinkStack_Destroy(stack);
return ret;
}
| 
转播
