主题:[原创]急!!请大家帮个忙......数据结构
morganlv
[专家分:0] 发布于 2008-01-12 20:47:00
这是数据结构题目如下:
判断表达式中的圆括号是否匹配???
回复列表 (共5个回复)
沙发
justforfun626 [专家分:18460] 发布于 2008-01-12 22:46:00
What work have you done so far?
What do you not understand?
What question do you have?
Thanks!
板凳
morganlv [专家分:0] 发布于 2008-01-13 12:31:00
我不懂这题什么意思啊.你跟我分析分析啊
3 楼
justforfun626 [专家分:18460] 发布于 2008-01-13 23:28:00
匹配
((A+B)/C)/D
Not 匹配
((A+B/C)/D
((A+B)/)C)/D
)(A+B)/C)/D
4 楼
zscw126net [专家分:10] 发布于 2008-01-14 21:17:00
#include<stdio.h>
#include<stdlib.h>
#define STACKINCREAMENT 10
#define STACK_INIT_SIZE 100
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int status ;
typedef char SElemtype;
typedef struct
{
SElemtype *base;
SElemtype *top;
status stacksize;
}sqstack;
status Initstack(sqstack &s);
status Gettop(sqstack s,SElemtype &e);
status push(sqstack &s,SElemtype e);
status pop(sqstack &s,SElemtype &e);
status stackempty(sqstack &s);
status clearstack(sqstack &s);
status match(sqstack &s,char *str);
void main()
{
char str[25],enter;
sqstack s;
Initstack(s);
printf("请输入括号的表达式:");
scanf("%s",str);
scanf("%c",&enter);
match(s,str);
}
status Initstack(sqstack &s)
{
s.base=(SElemtype *)malloc(STACK_INIT_SIZE*sizeof(SElemtype));
if(!s.base) exit(OVERFLOW);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE ;
return OK;
}
status Gettop(sqstack s,SElemtype &e)
{
if(s.top==s.base) return ERROR;
e=*(s.top-1);
return OK;
}
status push(sqstack &s,SElemtype e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(SElemtype *)realloc(s.base,(s.stacksize+STACKINCREAMENT)*sizeof(SElemtype));
if(!s.base)
exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREAMENT;
}
*s.top++=e;
return OK;
}
status pop(sqstack &s,SElemtype &e)
{
if(s.top==s.base)
return ERROR;
e=*--s.top;
return OK;
}
status stackempty(sqstack &s)
{
if(s.top==s.base)
return OK;
return ERROR;
}
status clearstack(sqstack &s)
{
if(s.top==s.base) return ERROR;
s.top=s.base;
return OK;
}
status match(sqstack &s,char *str)
{
int i=0,flag=0;
SElemtype e;
while(str[i]!='\0')
{
switch(str[i])
{
case '(':push(s,str[i]);break;
case '[':push(s,str[i]);break;
case '<':push(s,str[i]);break;
case ')':
{
pop(s,e);
if(e!='(')
flag=1;
}break;
case ']':
{
pop(s,e);
if(e!='[')
flag=1;
}break;
case '>':
{
pop(s,e);
if(e!='<')
flag=1;
}break;
default:break;
}
if(flag)break;
i++;
}
if(!flag&&stackempty(s))
printf("括号匹配!\n");
else
printf("括号不匹配!\n");
return OK;
}
5 楼
justforfun626 [专家分:18460] 发布于 2008-01-15 01:15:00
To zscw126net and LZ:
You really don't need that complicated code.
One integer counter is enough, Left ( add 1, Right ) -1.
1) whenever counter become negative, not 匹配,
2) If end with non-zero, not 匹配
3) end zero, 匹配
我来回复