Question

编写一个测试程序，检查一个C语言程序中括号的配对情况。

要求：
1. 包括“{、}”和“（、）”以及[、]。
2. 利用堆栈将左括号入栈，遇到右括号时出栈进行匹配。
3. 给出相应的正确和错误信息。
4. 入栈和出栈函数分别为Push()和Pop()。
5. 结果输出到屏幕上和结果文件中。

Answer 1

头文件：（另存为SeqStack.h）
typedef struct
{
DataType stack[MaxStackSize];
int top;
} SeqStack;

void StackInitiate(SeqStack *S) /*初始化顺序堆栈S*/
{
S->top = 0; /*定义初始栈顶下标值*/
}

int StackNotEmpty(SeqStack S)
/*判顺序堆栈S非空否，非空则返回1，否则返回0*/
{
if(S.top <= 0) return 0;
else return 1;
}

int StackPush(SeqStack *S, DataType x)
/*把数据元素值x压入顺序堆栈S，入栈成功则返回1，否则返回0 */
{
if(S->top >= MaxStackSize)
{
printf("堆栈已满无法插入! \n");
return 0;
}
else
{
S->stack[S->top] = x;
S->top ++;
return 1;
}
}

int StackPop(SeqStack *S, DataType *d)
/*弹出顺序堆栈S的栈顶数据元素值到参数d ，出栈成功则返回1，否则返回0*/
{
if(S->top <= 0)
{
printf("堆栈已空无数据元素出栈! \n");
return 0;
}
else
{
S->top --;
*d = S->stack[S->top];
return 1;
}
}

int StackTop(SeqStack S, DataType *d)
/*取顺序堆栈S的当前栈顶数据元素值到参数d ，成功则返回1，否则返回0*/
{
if(S.top <= 0)
{
printf("堆栈已空! \n");
return 0;
}
else
{
*d = S.stack[S.top - 1];
return 1;
}
}

括号问题
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define MaxStackSize 100
typedef char DataType;
#include "SeqStack.h"

void ExpIsCorrect(char exp[], int n)
//判断有n个字符的字符串exp左右括号是否配对正确
{
SeqStack myStack; //定义链式堆栈
int i;
char c;

StackInitiate(&myStack);
for(i = 0; i < n; i++)
{
if((exp[i] == '(') || (exp[i] == '[') || (exp[i] == '{'))
StackPush(&myStack, exp[i]); //入栈

else if(exp[i] == ')' && StackNotEmpty(myStack)
&& StackTop(myStack, &c) && c == '(')
StackPop(&myStack, &c); //出栈
else if(exp[i] == ')' && StackNotEmpty(myStack)
&& StackTop(myStack, &c) && c != '(')
{
printf("左右括号配对次序不正确！\n");
return;
}

else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack, &c) && c == '[')
StackPop(&myStack, &c); //出栈
else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack, &c) && c != '[')
{
printf("左右括号配对次序不正确！\n");
return;
}

else if(exp[i] == '}' && StackNotEmpty(myStack)
&& StackTop(myStack, &c) && c == '{')
StackPop(&myStack, &c); //出栈
else if(exp[i] == '}' && StackNotEmpty(myStack)
&& StackTop(myStack, &c) && c != '{')
{
printf("左右括号配对次序不正确！\n");
return;
}

else if(((exp[i] == ')') || (exp[i] == ']') || (exp[i] == '}'))
&& !StackNotEmpty(myStack))
{
printf("右括号多于左括号！\n");
return;
}
}

if(StackNotEmpty(myStack))
printf("左括号多于右括号！\n");
else
printf("左右括号匹配正确！\n");
}

void main(void)
{
char a[] = "(())abc{[)(]}"; //测试例子1。左右括号配对次序不正确
char b[] = "(()))abc{[]}"; //测试例子2。右括号多于左括号
char c[] = "(()()abc{[]}"; //测试例子3。左括号多于右括号
char d[] = "(())abc{[]}"; //测试例子4。左右括号匹配正确
int n1 = strlen(a);
int n2 = strlen(b);
int n3 = strlen(c);
int n4 = strlen(d);

ExpIsCorrect(a, n1);
ExpIsCorrect(b, n2);
ExpIsCorrect(c, n3);
ExpIsCorrect(d, n4);
}

二者放于同一目录下即可

Answer 2

#include <stdio.h>
const int MAX_N=1000; //堆栈最大深度/文件最大长度
typedef struct
{
int top;
char data[MAX_N];
char Pop() //出栈
{
if(top<0) //堆栈为空
return -1;
else
return data[top--];
}

bool Push(char elem) //入栈
{
if(top==MAX_N-1) //堆栈满
return false;
else
{
data[++top]=elem;
return true;
}
}

char Peek() //查看栈顶元素
{
if(top<0) //堆栈为空
return -1;
else
return data[top];
}
}Stack;

int main(int argc, char *argv[])
{
Stack stack;
char text[MAX_N],filename[MAX_N];
int i;
FILE *outfile;

printf("输入要匹配括号的文本：");
while(gets(text)!=NULL)
{
stack.top=-1;
for(i=0;text[i]!='\0';i++)
{
if(text[i]=='{'||text[i]=='('||text[i]=='[')
stack.Push(text[i]);
else if(text[i]=='}'||text[i]==')'||text[i]==']')
{
if((stack.Peek()=='{'&&text[i]=='}')||(stack.Peek()=='('&&text[i]==')')||(stack.Peek()=='['&&text[i]==']'))
stack.Pop();
else
break;
}
}
printf("输入保存此次匹配结果的文件名：");
gets(filename);

outfile=fopen(filename,"w");
fprintf(outfile,"%s\n",text);

if(text[i]=='\0'&&stack.top==-1)
fprintf(outfile,"匹配成功！\n"),printf("匹配成功！\n");
else
fprintf(outfile,"匹配失败！\n"),printf("匹配失败！\n");

printf("输入要匹配括号的文本：");

}
return 0;
}

/*
测试数据：

int main(){ int data[];return}
1.txt

for(i=0;i<N;i++){while(1){data[i]++}}
2.txt

[[[{}]]
3.txt

{{{())}}}
4.txt

()()((())
5.txt

*/