Question

数据结构，栈的应用题目

设在一个算术表达式中允许使用三种括号：圆括号“（”和“）”、方括号“[”和“]花括号“{”和“}”。请设计一个算法，利用顺序栈结构来检查表达式中括号使用的合法性。即：左、右括号是否配对。每对括号之间可以嵌套，但不允许交叉。如 2+3*（4-{5+2}*3） 为配对；2+3*（4-{5+2 * 3} 为不配对。

Answer 1

#include <stdio.h>
#include <string.h>
typedef struct node_link{
char data;
struct node_link *next;
}node;
node *top=NULL;
void push(char data)
{
node *p;
p=(node *)malloc(sizeof(node));
if(!p){
printf("push failed.\n");
exit(0);
}
p->data=data;
p->next=top;
top=p;
}
int pop()
{
node *p;
int get;
p=top;
get=top->data;
top=top->next;
free(p);
return get;
}
int get_top()
{
if(!top)
{
printf("Stack is NULL.\n");
exit(0);
}
return top->data;
}
int macth_kuohao(char msg[])
{ int i=0;
for(i=0;i<strlen(msg);i++)
{ switch(msg[i])
{ case '{':
case '[':
case '(':push(msg[i]);break; /* 遇到'{','[',')'则压栈 */
case '}':
if(get_top()=='{'){ /* 取栈首元素比较 */
pop(); break; }
else return 0;
case ']':
if(get_top()=='[')
{
pop(); break; }
else
return 0;
case ')':
if(get_top()=='(')
{ pop();
break; }
else
return 0; }
}
if(is_empty()) /* 测试堆栈是否为空 */
return 1;
else return 0;}/* 打印堆栈 */
void print_stack()
{ node *p;
p=top;
if(!p)
{ printf("Stack is NULL.\n");
exit(0); }
while(p){ printf("%c",p->data);
p=p->next;}
} /* 测试堆栈是否为空 */
int is_empty()
{ if(!top) return 1;
else return 0;}
int main(void)
{ char a[100],b[4];
int i,d[4],count1,c[100],j=0;
b[0]='[';
b[1]=']';
b[2]='(';
b[3]=')';
d[0]=0;d[1]=0;d[2]=0;d[3]=0;
printf("Input:\n");
scanf("%s",a);
count1=strlen(a);
for(i=0;i<count1;i++)
{if(a[i]==b[0])<br/> {c[j]=0;j++;d[0]++;}
else if(a[i]==b[1])
{c[j]=1;j++;d[1]++;}
else if(a[i]==b[2])
{c[j]=2;j++;d[2]++;}
else if(a[i]==b[3])
{c[j]=3;j++;d[3]++;}}
if((d[0]+d[1]+d[2]+d[3])<=1)
{printf("符号不可能配对！");goto end;}

if(d[0]>d[1])
{printf("不匹配![多于]"); goto end;}
else if(d[0]<d[1])
{printf("不匹配![少于]");goto end;}
if(d[2]>d[3])
{printf("不匹配！(多于)"); goto end;}
else if(d[2]<d[3])
{ printf("不匹配!(少于)"); goto end;}
/*printf("\n%s\n",a); */
i=macth_kuohao(a);
if(i)
printf("理论上括号是配对的.\n");
else printf("左右括号配对次序不对!\n");
return 0;
end: printf("That's all");
getch();

}

Answer 2

String s = "i= ld.listIterator());"; //定义字符窜
String temp;
char c;
Stack stack = new Stack();

for(int i=0;i<s.length();i++){
c = s.charAt(i);
temp = Character.toString(c);
stack.push(temp); //压栈
}

int xiaoKH=0,zhongKH=0,daKH=0; //各个符号的初始数值
while(!stack.empty()){
temp = (String) stack.pop(); //当不为空,取出栈内容
if (temp.equalsIgnoreCase("(")){
xiaoKH++; //当有小括号,则+1
}else if(temp.equalsIgnoreCase(")")){
xiaoKH--; //当有另一边的,则-1
}
}

if (xiaoKH==0&zhongKH==0&daKH==0){
System.out.println("yes"); //判断是否为0,是的话就正确
}else{
System.out.println("no"); //这里可以分开写
} //正数表示没有左边,负数表示没有右边

Answer 3

交叉的情况就自己考虑下了.

Answer 4

编译原理的题目吧?