括号匹配的检验。
其中有个思想:
期待的急迫程度。
属实有些不理解。
这个题的意思应该是能检验出 小括号 和 中括号 的顺序。
比如[([][])]为正确格式,[(])、(( )])为不正确的格式。
自己写了个,但是只能实现一种括号的检验。
高手帮帮忙。期待的急迫程度应该怎么实现呢?
或者如何实现多种括号匹配的检验。非常感谢。^^
其实这个提 没有中括号大括号之分 就只有是() 就是先算内括号 在算外括号
你说的这个问题是非常麻烦的如果你能看懂下面的代码的话 你就可以明白了
如果你还是不明白,你就说一声 我会在给你解释的详细一些的
\*下面这个程序是我原来学数据结构的时候nuciewth斑竹给我的代码*/
#include<stdio.h>
#define MAXSIZE 100
#include<string.h>
int is_operation(char op)/*判断是否为运算符*/
{
switch(op)
{
case'+':
case'-':
case'*':
case'/':return(1);
default:return(0);
}
}
int priority(char op)/*判断进栈各运算符的优先级*/
{
switch(op)
{
case'#':return(-1);
case'(':return(0);
case'+':
case'-':return(1);
case'*':
case'/':return(2);
default:return(-1);
}
}
void postfix(char e[],char f[])/*中缀转换成后缀表达式*/
{
int i=0,j=0;
char opst[100];/*栈*/
int top,t;
top=0;/*当前顶指针*/
opst[top]='#';top++;/*将#放在栈底作为运算结束标志*/
while(e[i]!='#')/*核心语句段*/
{
if((e[i]>='0'&&e[i]<='9')||e[i]=='.')
{
f[j++]=e[i];/*遇到数字和小数点直接写入后缀表达式*/
}
else
if(e[i]=='(')/*遇到左括号直接写入操作符栈*/
{
opst[top]=e[i];
top++;
}
else
if(e[i]==')')/*遇到右括号和其对应的左括号后的操作符全部写入后缀表达式*/
{
t=top-1;
while(opst[t]!='(')
{
f[j++]=opst[--top];
t=top-1;
}
top--;/*出栈*/
}
else
if(is_operation(e[i]))
{
f[j++]=' ';
while(priority(opst[top-1])>=priority(e[i]))
{
f[j++]=opst[--top];
}
opst[top]=e[i];
top++;/*当前元素进栈*/
}
i++;/*处理下一个元素*/
}
while(top)
{
f[j++]=opst[--top];
}
f[j]='\0';
}
float readnumber(char f[],int *i)/*将字符转换为数值*/
{
float x=0.0;
int k=0;/*用K标记小数部分的位数*/
while(f[*i]>='0'&&f[*i]<='9')/*处理整数部分*/
{
x=x*10+(f[*i]-'0');
(*i)++;
}
if(f[*i]=='.')/*处理小数部分*/
{
(*i)++;
while(f[*i]>='0'&&f[*i]<='9')
{
x=x*10+(f[*i]-'0');
(*i)++;
k++;
}
}
while(k!=0)
{
x=x/10.0;
k=k-1;
}
/*printf("%f\n",x);*/
return(x);
}
double evalpost(char f[])
{
double x1,x2,obst[100];/*栈*/
int i=0,top=0;
while(f[i]!='#')/*还有元素要被处理*/
{
if(f[i]>='0'&&f[i]<='9')
{
obst[top]=readnumber(f,&i);
top++;/*将操作数进栈*/
}
else
if(f[i]==' ')/*用空格将两操作数隔开*/
{
i++;
}
else
if(f[i]=='+')/*做加法运算*/
{
x2=obst[--top];/*第一个操作数出栈*/
x1=obst[--top];/*第二个操作数出栈*/
obst[top]=x1+x2;/*两操作数进行运算,并将所得结果进栈*/
/*printf("%f",obst[top]); */
top++;
i++;
}
else
if(f[i]=='-')/*做减法运算*/
{
x2=obst[--top];
x1=obst[--top];
obst[top]=x1-x2;
top++;
i++;
}
else
if(f[i]=='*')/*做乘法运算*/
{
x2=obst[--top];
x1=obst[--top];
obst[top]=x1*x2;
top++;
i++;
}
else
if(f[i]=='/')/*做除法运算*/
{
x2=obst[--top];
x1=obst[--top];
obst[top]=x1/x2;
top++;
i++;
}
}
return(obst[0]);/*环回最终运算结果*/
}
int main()
{
char e[MAXSIZE],f[MAXSIZE];/*定义两个字符数组*/
double sum;/*结果*/
printf("please input the numbers,end by '#':");/*输入被操作的中缀表达式*/
scanf("%s",e);
postfix(e,f);/*将中缀表达式转换成后缀表达式*/
printf("the postfix sort:");
puts(f);
sum=evalpost(f);/*做运算*/
printf("Output the rezult:%f",sum);/*打印结果*/
return(0);
}
[此贴子已经被作者于2007-2-12 22:27:13编辑过]
谢谢三楼的班竹。不过你好像理解错了。
这个题是检验括号的匹配。不过后来我想通了。
自己写了下算法。不知道还有没有什么遗漏的。
不匹配的情况:
1.来的右括弧非是所"期待"的;
2.来的是"不速之客";
3.直到结束,也没有到来所"期待"的。
这三种情况对应到栈的操作即为:
1.和栈顶的左括弧不相匹配;
2.栈中并没有左括弧等在哪里;
3.栈中还有左括弧没有等到和它相匹配的右括弧。
void Chack(){
//没有考虑垃圾数据的输入,约定只有()[ ]两种括号输入
InitStack(S); //构造空栈S
ch=getchar(); //接受第一个字符
while(ch!=='\n')
{
switch(ch){
case '( ':
case '[ ': Push(s,ch); break; //若为左括号,入栈
case ') ': if(StackEmpty(S))
{
pus("匹配不通过");
exit(1);
} //若第一个字符即为右括号,则一定不匹配
else{
GetTop(S,e);
if(e=='( ') Pop(S,e); //若匹配成功,删除栈顶元素
break;
}
case '] ': if(StackEmpty(S)){pus("匹配不通过");exit(1);}
else{
GetTop(S,e);
if(e=='[ ') Pop(S,e); //若匹配成功,删除栈顶元素
break;
}
}
ch=getchar();
}
if(StackEmpty(S)) puts("匹配通过"); //入栈出栈时都应为空,则匹配通过
else puts("匹配不通过");
}
[此贴子已经被作者于2007-2-13 20:57:03编辑过]
谢谢三楼的班竹。不过你好像理解错了。
这个题是检验括号的匹配。不过后来我想通了。
自己写了下算法。不知道还有没有什么遗漏的。
不匹配的情况:
1.来的右括弧非是所"期待"的;
2.来的是"不速之客";
3.直到结束,也没有到来所"期待"的。
这三种情况对应到栈的操作即为:
1.和栈顶的左括弧不相匹配;
2.栈中并没有左括弧等在哪里;
3.栈中还有左括弧没有等到和它相匹配的右括弧。
void Chack(){
//没有考虑垃圾数据的输入,约定只有()[ ]两种括号输入
InitStack(S); //构造空栈S
ch=getchar(); //接受第一个字符
while(ch!='\n')
{
switch(ch){
case '( ':
case '[ ': Push(s,ch); break; //若为左括号,入栈
case ') ': if(StackEmpty(S))
{
pus("匹配不通过");
exit(1);
} //若第一个字符即为右括号,则一定不匹配
else{
GetTop(S,e);
if(e=='( ') Pop(S,e); //若匹配成功,删除栈顶元素
break;
}
case '] ': if(StackEmpty(S)){pus("匹配不通过");exit(1);}
else{
GetTop(S,e);
if(e=='[ ') Pop(S,e); //若匹配成功,删除栈顶元素
break;
}
ch=getchar();
}
if(StackEmpty(S)) puts("匹配通过"); //入栈出栈时都应为空,则匹配通过
else puts("匹配不通过");
}
因为你给的函数不全所以我也没发调试
不过你的思路是对的
绿色的地方有错误 你自己调试一下吧