括号匹配的时候，如果出三个大括号，一个中括号，再一个大括号这样就会报错，有时候一直循环，有时候CRT检测到应用程序在堆缓冲区结束后写入内存。这是为什么？（断点每次在paren函数最后出错）
main：
#include<iostream>
using namespace std;
#include "Stack.h"
#include<string>
//括号匹配（（），[]，{}）
bool paren(const char exp[],int lo,int hi)
{
Stack<char> S;
for(int i=lo;i<hi;i++)
{
switch(exp[i])
{
case '(':
case '[':
case '{':
S.push(exp[i]);
break;
case ')':
if(S.empty()||S.pop()!='(')
return false;
break;
case ']':
if(S.empty()||S.pop()!='[')
return false;
break;
case '}':
if(S.empty()||S.pop()!='{')
return false;
break;
default:
break;
}
}
return S.empty();
}
int main()
{
Stack<int> stack;
int num;
int flag=1;
//栈操作
while(flag){
cout<<"入栈请输入1，出栈请输入2,退出请输入0"<<endl;
cin>>flag;
switch(flag)
{
case 1:
cout<<"请输入入栈数字："<<endl;
cin>>num;
stack.push(num);
cout<<"栈顶数据为："<<stack.top()<<endl;
if(stack.empty())
{
cout<<"栈为空！"<<endl;
break;
}
else
{
cout<<"栈不为空"<<endl;
break;
}
case 2:if(!stack.empty())
{
stack.pop();
if(stack.empty())
{
cout<<"栈为空！"<<endl;
break;
}
else
{
cout<<"栈顶数据为："<<stack.top()<<endl;
cout<<"栈不为空"<<endl;
break;
}
}
else
{
cout<<"栈为空！"<<endl;
break;
}
case 0:break;
default:
cout<<"输入不合法！请重新输入"<<endl;
}
}
//括号匹配
flag=1;
string v;
while(flag)
{
cout<<"检查括号是否匹配请输入1，否则输入0"<<endl;
cin>>flag;
if(flag==0||flag==1)
{
if(flag==1){
cout<<"请输入括号："<<endl;
cin>>v;
char* k=new char[v.size()];
strcpy(k,v.c_str());
if(paren(k,0,v.size()))
cout<<"括号匹配！"<<endl;
else
cout<<"括号不匹配！"<<endl;
}
}
else
cout<<"输入不合法！请重新输入"<<endl;
}
return 0;
}
stack.h：
#ifndef __Stack_H__
#define __Stack_H__
#include "Vector.h"
template <typename T>
class Stack:public Vector<T>{//向量尾为栈顶
public:
void push(T const &e){
insert(size(),e);
}
T pop(){
return remove(size()-1);
}
T& top(){
return(*this)[size()-1];
}
};
#endif
vector.h:
#ifndef __Vector_H__
#define __Vector_H__
#include <iostream>
#include <ctime>
#include<stdlib.h>
using namespace std;
typedef int Rank; //秩
#define DEFAULT_CAPABILITY 3 //默认的初始容量（实际应用中可设置为更大）
template <typename T>
class Vector
{
protected:
Rank _size;int _capability;T* _elem;
void expand();
void shrink();
public:
Vector(int c=DEFAULT_CAPABILITY,int s=0,T v=0)//构造
{_elem=new T[_capability=c];for(_size=0;_size<s;_elem[_size++]=v);}
~Vector(){delete []_elem;}//析构
T& operator[] (Rank r);
Rank size() const{return _size;};
bool empty(){return !size();}
Rank insert(Rank r,T const& e);
Rank insert(T const& e){return insert(_size,e);}
void show();
T remove(Rank r);
int remove(Rank lo,Rank hi);
Rank find (T const& e){return find(e,0,_size);}
Rank find (T const &e,Rank lo,Rank hi);
void swap(T &a,T &b);
void BubbleSort_down(T A[],int n);
void BubbleSort_up(T A[],int n);
void mergeSort(Rank lo,Rank hi);
void merge(Rank lo,Rank mi,Rank hi);
};
//扩容
template <typename T>
void Vector<T>::expand()
{
if(_capability<DEFAULT_CAPABILITY)
_capability=DEFAULT_CAPABILITY;
if(_size<_capability)
return;
T* _OldElem=_elem;
_elem=new T[_capability<<=_capability];
for(int i=0;i<_size;i++)
_elem[i]=_OldElem[i];
delete [] _OldElem;
}
//缩容
template <typename T>
void Vector<T>::shrink()
{
if(_capability<DEFAULT_CAPABILITY<<1)
return;
if(_size>_capability>>2)
return;
T* _OldElem=_elem;
_elem=new T[_capability>>=_capability];
for(int i=0;i<_size;i++)
_elem[i]=_OldElem[i];
delete [] _OldElem;
}
template <typename T>
T& Vector<T>::operator[] (Rank r) //重载下标操作符
{
return _elem[r];
} // assert: 0 <= r < _size
//展示
template<typename T>
void Vector<T>::show()
{
for(int i=0;i<_size;i++)
cout<<_elem[i]<<" ";
cout<<endl;
}
//插入
template<typename T>
Rank Vector<T>::insert(Rank r,T const& e)
{
expand();
if(r<0||r>_size)
{cout<<"ERROR!"<<endl;return -1;}
for(int i=_size;i>r;i--)
_elem[i]=_elem[i-1];
_elem[r]=e;
_size++;
return r;
}
//区间删除
template<typename T>
int Vector<T>::remove(Rank lo,Rank hi)
{
if(hi==lo)
return 0;
while(hi<_size)
_elem[lo++]=_elem[hi++];
_size=lo;
shrink();
return hi-lo;
}
//单个删除
template<typename T>
T Vector<T>::remove(Rank r)
{
T e=_elem[r];
remove(r,r+1);
return e;
}
//区间查找
template<typename T>
Rank Vector<T>::find (T const &e,Rank lo,Rank hi)
{
while((lo<hi--)&&(e!=_elem[hi]));
return hi;
}
//交换
template<typename T>
void Vector<T>::swap(T &a,T &b)
{
T c;
c=a;
a=b;
b=c;
}
//冒泡降序
template <typename T>
void Vector<T>::BubbleSort_down(T A[],int n)
{
bool sorted=false;
while(!sorted)
{
sorted=true;
for(int i=0;i<n-1;i++)
{
if(A[i]<A[i+1])
{
swap(A[i],A[i+1]);
sorted=false;
}
}
n--;
}
}
//冒泡升序
template <typename T>
void Vector<T>::BubbleSort_up(T A[],int n)
{
bool sorted=false;
while(!sorted)
{
sorted=true;
for(int i=0;i<n-1;i++)
{
if(A[i]>A[i+1])
{
swap(A[i],A[i+1]);
sorted=false;
}
}
n--;
}
}
//归并排序
template <typename T>
void Vector<T>::mergeSort(Rank lo,Rank hi)
{
if(hi-lo<2)return;
Rank mi=(hi+lo)>>1;
mergeSort(lo,mi);
mergeSort(mi,hi);
merge(lo,mi,hi);
}
//归并
template <typename T>
void Vector<T>::merge(Rank lo,Rank mi,Rank hi)
{
T* A=_elem+lo;
int lb=mi-lo;
T* B=new T[lb];
for(Rank i=0;i<lb;i++)
B[i]=A[i];
int lc=hi-mi;
T* C=_elem+mi;
for(Rank i=0,j=0,k=0;(j<lb)||(k<lc);)
{
//cout<<A[i]<<" "<<B[j]<<" "<<C[k]<<" ";
if((j<lb)&&(!(k<lc)||B[j]<=C[k]))
A[i++]=B[j++];
if((k<lc)&&(!(j<lb)||C[k]<B[j]))
A[i++]=C[k++];
//cout<<A[i]<<" "<<B[j]<<" "<<C[k]<<" ";
}
delete [] B;
}
#endif
