| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6138 人关注过本帖
标题:[讨论]括号匹配的检验
只看楼主 加入收藏
love_hcy
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2006-12-24
收藏
 问题点数:0 回复次数:13 
[讨论]括号匹配的检验
看到一道堆栈的题:
括号匹配的检验。
其中有个思想:
期待的急迫程度。
属实有些不理解。

这个题的意思应该是能检验出 小括号 和 中括号 的顺序。
比如[([][])]为正确格式,[(])、(( )])为不正确的格式。

自己写了个,但是只能实现一种括号的检验。

高手帮帮忙。期待的急迫程度应该怎么实现呢?
或者如何实现多种括号匹配的检验。非常感谢。^^
搜索更多相关主题的帖子: 括号 检验 
2007-02-12 20:50
mp3aaa
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:2013
专家分:8
注 册:2006-2-15
收藏
得分:0 
你着个提是表达是的计算是吧

羊肉串 葡萄干 哈密瓜!!
2007-02-12 21:59
mp3aaa
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:2013
专家分:8
注 册:2006-2-15
收藏
得分:0 

其实这个提 没有中括号大括号之分 就只有是() 就是先算内括号 在算外括号
你说的这个问题是非常麻烦的如果你能看懂下面的代码的话 你就可以明白了
如果你还是不明白,你就说一声 我会在给你解释的详细一些的
\*下面这个程序是我原来学数据结构的时候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编辑过]


羊肉串 葡萄干 哈密瓜!!
2007-02-12 22:02
☆註⊙諨☆
Rank: 1
等 级:新手上路
帖 子:73
专家分:0
注 册:2006-10-7
收藏
得分:0 
楼上的你挺强悍呀。

2007-02-13 09:34
delpiero
Rank: 1
等 级:新手上路
帖 子:61
专家分:0
注 册:2007-2-8
收藏
得分:0 
小白了吧人家mp3aaa可是我们斑竹啊

2007-02-13 09:37
love_hcy
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2006-12-24
收藏
得分:0 

谢谢三楼的班竹。不过你好像理解错了。
这个题是检验括号的匹配。不过后来我想通了。
自己写了下算法。不知道还有没有什么遗漏的。

不匹配的情况:
   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编辑过]


原来时间真的会不够。原來一切真的都已經來不及。
2007-02-13 10:21
mp3aaa
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:2013
专家分:8
注 册:2006-2-15
收藏
得分:0 
以下是引用love_hcy在2007-2-13 10:21:55的发言:

谢谢三楼的班竹。不过你好像理解错了。
这个题是检验括号的匹配。不过后来我想通了。
自己写了下算法。不知道还有没有什么遗漏的。

不匹配的情况:
  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-02-13 15:25
love_hcy
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2006-12-24
收藏
得分:0 
应该是这个样子:
while(ch!=='\n')

原来时间真的会不够。原來一切真的都已經來不及。
2007-02-13 17:30
mp3aaa
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:2013
专家分:8
注 册:2006-2-15
收藏
得分:0 
以下是引用love_hcy在2007-2-13 17:30:23的发言:
应该是这个样子:
while(ch!=='\n')


不是拉
while(ch!='\n')
{
}
这样的话如果你输入‘(’ while只循环一次,你自己试一试吧


羊肉串 葡萄干 哈密瓜!!
2007-02-13 17:39
渚薰
Rank: 6Rank: 6
等 级:贵宾
威 望:22
帖 子:1132
专家分:0
注 册:2006-8-6
收藏
得分:0 
原理很简单
数据结构是一个栈
遇到左括号,括号进栈
遇到一个右括号,栈顶括号出栈,只到输入结束,检查栈是否空
只是最简单的括号匹配坚持
如果还要检查表达式是否正确,就必须用LL(1)分析程序了

个人ajax技术专题站: " target="_blank">http://www. 我不会闲你烦,只会闲你不够烦!
2007-02-13 18:42
快速回复:[讨论]括号匹配的检验
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021863 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved