| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2910 人关注过本帖
标题:求助 关于栈的编程
只看楼主 加入收藏
buhongwei
Rank: 1
来 自:1111
等 级:新手上路
帖 子:11
专家分:0
注 册:2008-10-31
收藏
 问题点数:0 回复次数:11 
求助 关于栈的编程
假设一个算法表达式中可以包括:圆括号“(”和“)”、方括号“[”和“]”以及花括号“{”和“}”,且这3种括号可按任意的次序嵌套使用,设计一程序,判别给定表达式中所含括号是否配对。
本人对栈不是很熟,希望大家帮帮忙!
搜索更多相关主题的帖子: 表达式 
2008-11-01 17:05
multiple1902
Rank: 8Rank: 8
等 级:贵宾
威 望:42
帖 子:4881
专家分:671
注 册:2007-2-9
收藏
得分:0 
先简化一下,只有小括号,你打算怎么检测?

设置一个top=0,从左向右扫描字符串,遇到左括号就top+=1,遇到右括号就top-=1,任何时候top不应该为负数。原理是什么?

情况复杂一些,现在不止一种括号了,不应该单纯地用一个top了。那么分成top1,top2,top3分别记录分别加减一,对吗? ()[]  ([)] 那么应该怎么办?

设置一个数组(先进后出,实际上就是栈),栈顶元素记录当前如果会遇到右括号的话应该是哪个,很显然只会有一个。遇到左括号就压栈,遇到右括号就判断并且弹栈。弹栈遇到下溢出也说明括号不匹配。
2008-11-01 19:06
笨鸟先飞%
Rank: 1
等 级:新手上路
帖 子:20
专家分:0
注 册:2008-10-31
收藏
得分:0 
   可是这个简化的思路怎样确保实现其余括号"[]  ([)]" 是否配对的判断呢
2008-11-01 20:08
multiple1902
Rank: 8Rank: 8
等 级:贵宾
威 望:42
帖 子:4881
专家分:671
注 册:2007-2-9
收藏
得分:0 
[bo][un]笨鸟先飞%[/un] 在 2008-11-1 20:08 的发言:[/bo]

   可是这个简化的思路怎样确保实现其余括号"[]  ([)]" 是否配对的判断呢

栈里元素类型为左括号或者右括号,弹栈时不仅仅是top-=1,还要看当前栈顶元素是否符合遇到的右括号。
2008-11-01 20:31
langtaotian
Rank: 1
来 自:河南鹤壁
等 级:新手上路
帖 子:3
专家分:0
注 册:2008-11-1
收藏
得分:0 
迷惑
栈的原则是先进后出,假设不可避免的是“(”和“)”中间加一个“[”又要,即是像这种情况“([)]”怎样解决?请问这样的算法会有什么实际用处。

波涛汹涌,大浪滔天
2008-11-01 22:55
multiple1902
Rank: 8Rank: 8
等 级:贵宾
威 望:42
帖 子:4881
专家分:671
注 册:2007-2-9
收藏
得分:0 
[bo][un]langtaotian[/un] 在 2008-11-1 22:55 的发言:[/bo]

栈的原则是先进后出,假设不可避免的是“(”和“)”中间加一个“[”又要,即是像这种情况“([)]”怎样解决?请问这样的算法会有什么实际用处。

这样,程序遇到右括号就要弹栈,弹栈的时候发现栈顶元素是"["或者"]",刚压进去的,那么发现小括号不是中括号,那么就报错。

实际用途似乎很大。
2008-11-02 08:01
langtaotian
Rank: 1
来 自:河南鹤壁
等 级:新手上路
帖 子:3
专家分:0
注 册:2008-11-1
收藏
得分:0 
了解了,谢谢
非常感谢,版主能帮忙举个实例吗?那样更有利于理解用处。麻烦了!

波涛汹涌,大浪滔天
2008-11-02 13:56
multiple1902
Rank: 8Rank: 8
等 级:贵宾
威 望:42
帖 子:4881
专家分:671
注 册:2007-2-9
收藏
得分:0 
比如检查出栈序列是否合法……
2008-11-02 15:25
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
这是写的括号匹配的算法,用了三个堆栈:
#include"LinkedStack.h"
#include<string.h>

////////////////////////////////////////////////
//bracketMatch()函数  表达式圆,方,花括号匹配
////////////////////////////////////////////////
bool bracketMatch()
{
    //定义三个分别用于存放圆,方,花三中括号的堆栈
    LinkedStack<char> LS1;
    LinkedStack<char> LS2;
    LinkedStack<char> LS3;

    //存放输入的表达式字符串
    char* exp=new char[50];
    cout<<"请输入要进行括号匹配的表达式:";
    cin>>exp;

    char t;//暂存取出的括号字符
    char x;//暂存弹出的括号字符
    //对表达式中的三种括号进行匹配
    for(unsigned i=0;i<=strlen(exp)-1;i++)
    {
        t=exp[i];
        //如果都是左括号,则全部压入堆栈
        if(t=='(')
            LS1.Push(t);
        else if(t=='[')
            LS2.Push(t);
        else if(t=='{')
            LS3.Push(t);
        //如果是右括号,则全部弹栈进行匹配
        //在弹栈前如果有一个堆栈为空,则说明不匹配
        else if(t==')')
        {
            if(LS1.IsEmpty())
            {
                cout<<"不匹配!"<<endl;
                return false;
            }
            LS1.Pop(x);
        }
        else if(t==']')
        {
            if(LS2.IsEmpty())
            {
                cout<<"不匹配!"<<endl;
                return false;
            }
            LS2.Pop(x);
        }
        else if(t=='}')
        {
            if(LS3.IsEmpty())
            {
                cout<<"不匹配!"<<endl;
                return false;
            }
            LS3.Pop(x);
        }
        else
            //继续循环
            continue;
    }
    //如果三个括号栈都已经为空了则说明匹配
    if(LS1.IsEmpty() && LS2.IsEmpty() && LS3.IsEmpty())
    {
        cout<<"匹配!"<<endl;
        return true;
    }
    //有一个不空都不能匹配
    else
    {
        cout<<"不匹配!"<<endl;
        return  false;
    }
};
//////////////////////////bracketMatch()函数结束
2008-11-02 18:06
很远的那颗星
Rank: 2
等 级:新手上路
威 望:4
帖 子:544
专家分:0
注 册:2008-6-30
收藏
得分:0 
这个程序不用栈也就几行代码...

Fighting~~~~~~~~
2008-11-02 18:22
快速回复:求助 关于栈的编程
数据加载中...
 
   



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

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