返回
编程
分类

不能出栈,//所要求的判断括号匹配的算法

日期: 2020-03-17 01:19 浏览次数 : 171

#include <iostream>
#include<assert.h>

编写一个算法,检查一个程序中的花括号,方括号和圆括号是否配对,若能够全部配对则返回1,否则返回0。

C++先序遍历非递归算法,可以进栈,不能出栈
#include
#include
#include"BinaryTree.h"
using namespace std;
const int stackIncreament = 20; //栈溢出时扩展空间增量
template
class SeqStack{
public:

#include<cstring>

Head.h:

 int top; SeqStack(int sz=50); //建立一个空栈 ~SeqStack(){delete[] elements;} void push(const T& x); //进栈要检查栈状态 bool pop; //出栈要检查栈状态 bool getTop; bool isEmpty() const { return ?true:false; } bool isFull() const { return (top==maxSize-1)?true:false; } int getSize() const { return top+1; } void makeEmpty(){ top=-1; } friend ostream& operator<< (ostream& os,SeqStack<T>& S); //重载<< private: //用顺序表的动态存储P46,顺序表的两种存储表示方式 T *elements; int maxSize; void overflowProcess();

#include<stdio.h>

#ifndef HEAD_H_INCLUDED

};

#include<stdlib.h>
using namespace std;
const int stackIncreament=20;     //栈溢出时扩展空间的增量
const int maxLength=100;       //最大字符串长度
template<class T>
class SeqStack
{
      private:
              T*elements;        //存放栈中元素的栈数组
              int top;           //栈顶指针
              int maxSize;       //栈最大可容纳元素
      public:
             SeqStack(int sz);    //建立一个空栈
             ~SeqStack(){delete[]elements;}    //析构函数
             void overflowProcess();    
             void Push(T& x);
             //如果Isfull(),则溢出处理;否则把x插入到栈顶
             bool Pop(T& x);
             bool IsEmpty(){return(top==-1)?true:false;}
             bool IsFull(){return(top==maxSize-1)?true:false;}
             int getSize()const{return top+1;}   
             void PrintMatchPairs(char *expression);
             friend ostream& operator<<(ostream& os,SeqStack<T>& s)
             {
                os<<"top="<<s.top<<endl;           
             for(int i=0;i<s.top;i++)
             {
              os<<i<<":"<<s.elements[i]<<endl; 
             }
             return os;
             }

#define HEAD_H_INCLUDED

template
SeqStack::SeqStack: top,maxSize{

        
};

#include<iostream>

elements=new T[maxSize];
assert(elements != NULL); //断言检查动态存储是否分配成功
}
template
void SeqStack::overflowProcess(){
T *newArray=new T[maxSize+stackIncreament];
assert(newArray != NULL);
maxSize=maxSize+stackIncreament;
delete[] elements;
elements=newArray;
}

template<class T>
SeqStack<T>::SeqStack(int sz)
//建立一个最大尺寸为sz的空栈,若分配不成功则错误处理
{
           top=-1;
           maxSize=sz;
           elements=new T[maxSize];
           assert(elements!=NULL);//断言:动态存储分配成功与否
}

struct LinkedNode

template
void SeqStack::push(const T& x){
if == true) overflowProcess(); //栈满进行溢出处理
elements[++top] = x;
必威官网亚洲体育 ,}

template <class T>
void SeqStack<T>::overflowProcess()
//扩充栈的存储空间
{
     T*newArray=new T[maxSize+stackIncreament];
     if(newArray==NULL)
     {
                       cout<<"存储分配失败!"<<endl;
                       exit(1);
     }
     for(int i=0;i<top;i++)
     {
             newArray[i]=elements;
     }
     maxSize=maxSize+stackIncreament;
     delete[]elements;
     elements=newArray;
}

{

template
bool SeqStack::pop{
if == true) return false;
x=elements[top--];

template <class T>
void SeqStack<T>::Push(T& x)
{
     if(IsFull()==true)
     overflowProcess();              //栈满则溢出处理
     elements[++top]=x;               //栈顶指针先+1,再进栈
}

    int data;

return true;

template <class T>
bool SeqStack<T>::Pop(T& x)
{
     if(IsEmpty()==true)
     return false;
     x=elements[top--];                     //栈顶指针退1
     return true;                      //退栈成功
}

    LinkedNode*next;

}

template <class T>
void PrintMatchPairs(char *expression)
//从左向右扫描左括号入栈,当扫描到第一个右括号时,将它与栈顶的左括号匹配,匹配成功删除该左括号
{
    SeqStack<int>s1(maxLength);            //栈s存储 ,建立一个空栈,以方便存储()括号
    SeqStack<int>s2(maxLength);             //存[]括号
    SeqStack<int>s3(maxLength);             //存{}括号
    int j;
    int length=strlen(expression);        //字符串的长度
    for(int i=1;i<length;i++)           //在表达式中搜索"("和")"
    {
        j=i-1;
        if(expression[i-1]=='(')       //左圆括号,位置进栈
        s1.Push(i);
        else if (expression[i-1]==')')  //右圆括号
        {
            if(s1.Pop(j)==true)         //栈不空,退栈成功
            cout<<j<<"与"<<i<<"匹配"<<endl;
            else
            cout<<"没有与第"<<i<<"个右圆括号匹配的左圆括号!"<<endl;
        }
        else if(expression[i-1]=='[')
  {
      s2.Push(i); 
  }
  else if (expression[i-1]==']') 
        {
            if(s2.Pop(j)==true)       
            cout<<j<<"与"<<i<<"匹配"<<endl;
            else
            cout<<"没有与第"<<i<<"个右中括号匹配的左中括号!"<<endl;
        }
        else if (expression[i-1]=='{')  
        {
            s3.Push(i);
        }
        else if (expression[i-1]=='}')  
        {
            if(s3.Pop(j)==true)         
            cout<<j<<"与"<<i<<"匹配"<<endl;
            else
            cout<<"没有与第"<<i<<"个右花括号匹配的左花括号!"<<endl;
        }
        while(s1.IsEmpty()==false)              //栈中还有左括号
       {
            s1.Pop(j);
            cout<<"没有与第"<<j<<"个左括号匹配的右括号!"<<endl;
       }
       while(s2.IsEmpty()==false)              
       {
            s2.Pop(j);
            cout<<"没有与第"<<j<<"个左括号匹配的右括号!"<<endl;
       }
       while(s3.IsEmpty()==false)             
       {
            s3.Pop(j);
            cout<<"没有与第"<<j<<"个左括号匹配的右括号!"<<endl;
       }
    }
}

};

template
bool SeqStack::getTop{
if==true) return false;
x=elements[top];
return true;
}

int main()
{
 SeqStack <int> S(10);
 char str1[100];   //字符数组
 cout<<"请输入一串带有括号的字符串:"<<endl;
 cin>>str1;
 cout<<"您输入的字符串是:"<<endl;
 cout<<str1;
 int length=strlen(str1);
 S.PrintMatchPairs(str1);
 system("repause");
 return 0;
}

 

template
ostream& operator<< (ostream& os,SeqStack& S){
os<<"top = "<<S.top<<endl;
os<<"栈中的元素为:"<<endl;
for(int i=0;i<=S.top;i++)
os<<i<<":"<<S.elements[i]<<endl;
return os;
}

-------------------------------- 作者在 2017-12-10 16:49:28 补充以下内容

求大神帮帮忙!

class LinkedStack//链式栈的类定义

****************************以上SeqStack.h*****************************************
#include
#include

{

#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
template
struct BinTreeNode{

public:

T data;BinTreeNode<T> *lchild,*rchild;BinTreeNode():lchild,rchild{ }BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T> *r=NULL):lchild,rchild,data{ }

    LinkedStack();

};
template
class BinaryTree{
private:
BinTreeNode *root;
public:
/*template
friend bool is_similar(BinTreeNode *p,BinTreeNode *q);
*/
BinaryTree():root{}//初始化一棵空树
BinaryTree{ root=new BinTreeNode; }//初始化一棵只有一个接点的树

    ~LinkedStack(){makeEmpty();};

BinTreeNode<T> * createBinTree();BinTreeNode<T> * preOrder(BinTreeNode<T> *p);BinTreeNode<T> * inOrder(BinTreeNode<T> *p);BinTreeNode<T> * postOrder(BinTreeNode<T> *p);BinTreeNode<T> * preOrderStack(BinTreeNode<T> *p);

    void Push(LinkedNode &);

};
template
BinTreeNode* BinaryTree::createBinTree(){
BinTreeNodet;
/
t=root;*/
T x;
cin>>x;
if
t=NULL;
else{

    int Pop();

 t=new BinTreeNode<T>; //t=new BinTreeNode<T>; t->lchild=createBinTree(); t->rchild=createBinTree();}return t;

    bool getTop(LinkedNode&x)const;

}
template
BinTreeNode * BinaryTree::preOrder(BinTreeNode *p){
if
cout<<'#';
else
cout<data;
if{
preOrder(p->lchild);
preOrder(p->rchild);
}
return p;
}
template
BinTreeNode * BinaryTree::inOrder(BinTreeNode *p){
if
inOrder(p->lchild);
if
cout<<'#';
else
cout<data;
if
inOrder(p->rchild);
return p;
}
template
BinTreeNode * BinaryTree::postOrder(BinTreeNode *p){
if{
postOrder(p->lchild);
postOrder(p->rchild);
}
if
cout<<'#';
else
cout<data;

    bool IsEmpty()const{return (top==NULL)?true:false;}

return p;

    int getSize()const;

}
template
BinTreeNode * BinaryTree::preOrderStack(BinTreeNode *p){
SeqStack> S;
if
cout<<'#';
else { //p不指向空树

    void makeEmpty();

while(p||S.top!=-1){if{S.push;cout<<p->data;p=p->lchild;}else{S.pop;p=p->rchild;}

    void print();

}
}

private:

return p;
}
********************************************以上BinaryTree**************************
#include
#include"SeqStack.h"

    LinkedNode *top;

int main(){

};

BinTreeNode<char> *p;/*SeqStack<BinTreeNode<char>> S;*/BinaryTree<char> B;cout<<"请输入一棵树B:"<<endl;p=B.createBinTree();cout<<endl;cout<<"先序遍历的结果为:"<<endl;B.preOrder;cout<<endl;cout<<"中序遍历的结果为:"<<endl;B.inOrder;cout<<endl;cout<<"后序遍历的结果为:"<<endl;B.postOrder;cout<<endl;cout<<"先序遍历的非递归形式结果为:"<<endl;B.preOrderStack;

 

system;
return 0;
}
**********************************************以上main函数*************************

 

#endif // HEAD_H_INCLUDED

 

Methods.cpp:

#include"head.h"

#include<iostream>

using namespace std;

LinkedStack::LinkedStack(){top=NULL;}

void  LinkedStack::makeEmpty()

{

    LinkedNode*p;

    while(top!=NULL)

    {

        p=top;top=top->next;delete p;

    }

}

void LinkedStack::Push(LinkedNode &x)

{

    LinkedNode *p=top;

    x.next=p;

    top=&x;

}

int LinkedStack::Pop()

{int data=top->data;

    LinkedNode*p=top;

    top=top->next;

    delete p;

    return data;

}

bool LinkedStack::getTop(LinkedNode&x)const

{

    if(IsEmpty()==true)return false;

    x=*top;

    return true;

}

int LinkedStack::getSize()const

{

    int k=0;

    LinkedNode*p=top;

    while(p!=NULL){p=p->next;k++;}

    return k;

}

void LinkedStack::print()

{

    cout<<"栈中元素个数="<<getSize()<<endl;

    LinkedNode*p=top;int i=0;

    while(p!=NULL)

    {

        cout<<++i<<":"<<p->data<<endl;

        p=p->next;

    }

}

 

 

Main.cpp:

#include"head.h"

#include <iostream>

#include<string.h>

using namespace std;

//所要求的判断括号匹配的算法

void PrintMatchedPairs(char *expression)

{

    LinkedStack s1;LinkedStack s2;LinkedStack s3;

    int j,length=strlen(expression);

    cout<<"对于小括号()的情况:"<<endl;

    for(int i=1;i<=length;i++)

    {

        if(expression[i-1]=='('){LinkedNode t;t.data=i;s1.Push(t);}//左括号,位置进栈

        else if(expression[i-1]==')')

        {

            if(s1.IsEmpty()==false){j=s1.Pop();cout<<j<<"与"<<i<<"匹配"<<endl;}

            else cout<<"没有与第"<<i<<"个右括号匹配的左括号!"<<endl;

        }

    }

    while(s1.IsEmpty()==false)

    {

        j=s1.Pop();

        cout<<"没有与第"<<j<<"个括号相匹配的右括号!"<<endl;

    }

 

    cout<<"对于中括号[]的情况:"<<endl;

    for(int i=1;i<=length;i++)

    {

        if(expression[i-1]=='['){LinkedNode t;t.data=i;s2.Push(t);}//左括号,位置进栈

        else if(expression[i-1]==']')

        {

            if(s2.IsEmpty()==false){j=s2.Pop();cout<<j<<"与"<<i<<"匹配"<<endl;}

            else cout<<"没有与第"<<i<<"个右括号匹配的左括号!"<<endl;

        }

    }

    while(s2.IsEmpty()==false)

    {

        j=s2.Pop();

        cout<<"没有与第"<<j<<"个括号相匹配的右括号!"<<endl;

    }

 

    cout<<"对于大括号{}的情况:"<<endl;

    for(int i=1;i<=length;i++)

    {

        if(expression[i-1]=='{'){LinkedNode t;t.data=i;s3.Push(t);}//左括号,位置进栈

        else if(expression[i-1]=='}')

        {

            if(s3.IsEmpty()==false){j=s3.Pop();cout<<j<<"与"<<i<<"匹配"<<endl;}

            else cout<<"没有与第"<<i<<"个右括号匹配的左括号!"<<endl;

        }

    }

    while(s3.IsEmpty()==false)

    {

        j=s3.Pop();

        cout<<"没有与第"<<j<<"个括号相匹配的右括号!"<<endl;

    }

}

int main()

{

    char s[100];

    cout<<"请输入要判断的带有三种括号的字符串"<<endl;

    cin>>s;

    PrintMatchedPairs(s);

    return 0;

}

 

 

运行结果:

必威官网亚洲体育 1

必威官网亚洲体育 2