#include<iostream>
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#define maxsize 100
using namespace std;
typedef struct node
{
char data;
struct node *next;
}lnode ,*linkstack;
void init(linkstack *top)
{
if( ( (*top)=(linkstack)malloc(sizeof(lnode)) )==NULL )//(给*top分配一个存储空间让top指向这个空间）
exit(-1);
(*top)->next=NULL;
}
int empty(linkstack top)
{
if(top->next==NULL)
return 1;
else
return 0;
}
int get(linkstack top,char *e)
{
lnode *p;
p=top->next;
if(!p)
{
cout<<"栈已空！";
return 0;
}
else
{
*e=p->data;
return 1;
}
}
int push(linkstack top,char e)
{
lnode *p;
if( (p=(linkstack)malloc(sizeof(lnode)))==NULL )//(给*top分配一个存储空间让top指向这个空间）
{
printf("分配内存失败");
exit(-1);
return 0;
}
p->data=e;
p->next=top->next;
top->next=p;
return 1;
}
int pop(linkstack top,char *e)
{
linkstack p=top->next;
if(p==NULL)
{
cout<<"栈已空！";
return 0;
}
top->next=p->next;
*e=p->data;
free(p);
return 1;
}
int length(linkstack top)
{
int i=0;
lnode *p=top;
while(p->next!=NULL)
{
p=p->next;
i++;
}
return i;
}
void clear(linkstack top)
{
lnode *p,*q;
p=top;
while(!p)
{
q=p;
p=p->next;
free(q);
}
}
int match(char e,char ch)
{
if(e=='(' && ch==')')
return 1;
else if(e=='['&&ch==']')
return 1;
else if(e=='{'&&ch=='}')
return 1;
else
return 0;
}
int main()
{
linkstack s;
lnode *p;
int i,len;
char e;
string ch="{4*(8-3)-[(7*2)*5-9]}*3-9*(5-2)";
len=ch.length();
init(&s);
cout<<"将带括号的表达式依次入栈！"<<endl;
cout<<"{4*(8-3)-[(7*2)*5-9]}*3-9*(5-2)"<<endl;
for(i=0;i<len;i++)
{
switch(ch[i])
{
case '(':
case '[':
case '{':
push(s,ch[i]);
break;
case ')':
case ']':
case '}':
if(empty(s))
{
cout<<"缺少左括号"<<endl;
return 0;
}
else
{
get(s,&e);
if(match(e,ch[i]))
{
pop(s,&e);
}
else
{
cout<<"左右括号不匹配";
return 0;
}
}
}
}
if(empty(s))
printf("阔号匹配！");
else
cout<<"缺少右括号！";
}