数据结构编程题(c语言)

Question

设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算法判断其中的括号是否匹配。
提示：本题使用一个运算符栈st，当遇到的‘（’、‘[’、或‘{’时进栈，当遇到‘}’、‘]’、‘）’时判断栈顶是否为相应的括号，若是退栈继续执行；否则算法结束

Answer 1

因为你这个题目是到所输入符号跟栈顶元素不匹配时才结束的.
所以用顺序栈有可能发生上溢现象，因此在这里我用链式栈来解决这个问题
代码如下：
#include <stdio.h>
#include <stdlib.h>
#define len sizeof(stack)
typedef struct node
{
char c;
struct node* next;
}stack,*link;
link push(link s,char c); //进栈
link pop(link s); //出栈
int main ()
{
int flag=1; //初始化为1，表示输入的符号是匹配的
char c,top;
link s=NULL; //置空栈
while(1)
{
scanf("%c",&c);
switch(c)
{
case '[':
case '{':
case '(':
s=push(s,c);
break;
case ']':
case '}':
case ')':
top=s->c; //取得栈顶跟c比较
if((top=='['&&c==']')||(top=='{'&&c=='}')||(top=='('&&c==')')) //判断栈顶元素是否与c相同
s=pop(s);
else
flag=0; //不想同则改变标志flag的值
break;
}
if(!flag) //如果flag非真,则表示符号不匹配,显示相关信息并退出,否则继续输入
{
printf("符号不匹配!\n");
break;
}
}
return 0;
}
link push(link s,char c)
{
link p;
p=(link)malloc(len);
//进栈操作其实用的就是不带头结点的头插法建立一个单链表
p->c=c;
p->next=s;
s=p; //更新栈顶
return s; //返回新栈顶
}
link pop(link s)
{
link p;
p=s; //保存原栈顶
s=s->next; //更新栈顶
free(p); //删除原栈顶
return s;
}

Answer 2

可以先读取栈顶元素，用if..else语句来判断该括号的类型，从而找出应该匹配的括号类型，在读入下一个元素的时候，判断是否为应该匹配的类型。大概的代码如下：
gettop(&st,&e);
if(e=='(')
ch=')';
else
if(e='[')
ch=']';
else
if(e=='{')
ch='}';
else
printf("error!\n");
ch1=getelement();
if(ch==ch1)
push(&st,ch1);
else
printf("error");

Answer 3

#include <stdio.h>
#define N 20
/*本题使用一个运算符栈st,
当遇到的([{入栈,当)]}时
判断栈顶是否为相应的括号，
若是退栈继续执行;
否则算法结束 */
char st[N];
int i = 0;

bool push(char x)
{
if(i>=N)
return 0;
st[i++] = x;
return 1;
}
bool pop(char *p)
{
if(i<0)
{
return false;
}
*p = st[i--];
return true;
}

void main()
{
char c;
char *p = &c;
bool flag = 1;
c=getchar();
while(c!='\n')
{
if(c=='(' || c=='[' || c=='{')
{
if(!push(c))
continue;
}
else
if(!pop(p))
if(*p==c)
continue;
else
{
flag = 0;
break;
}
c=getchar();
}
if(flag)
printf("对称\n");
else
printf("不对称\n");
}
完整的写了遍本回答被提问者采纳