Question

数据结构（C++版）栈与队的的应用（括号匹配问题），要求在下面的问题补充。急求源代码啊，用类定义的。

括号匹配问题
在算述表达式中，可能出现嵌套的大、中、小括号，设计一个算法，可以判断给定的表达式串中的括号是否是匹配的。
要求：首先，分别先定义一个栈和一个队；其次，将表达式串中的各种括号字符依次入队（其它字符不予考虑）；最后利用栈来判断队中的括号是否是匹配的。
无论是什么括号，最后出现的左括号，必须与其后最先出现的右括号匹配，这符合栈的后进先出的特点，故我们可以用栈和进行匹配性判断。
根据要求，串(括号)  队  栈
操作接口：bool match(char *s)
主要操作：
队，栈初始化
括号字符入队
出队为左括号：进栈
出队为右括号：弹栈
匹配？

Answer 1

#include<iostream>
using namespace std;

class Stack
{
public:
int size;
int top;
char *stack;
Stack(int m);
bool push(char item);//入栈
bool pop();//出栈
bool isempty();//是否为空
void clear();//清空栈
int Size();//栈中元素个数
~Stack();
char Top();
};
#include<iostream>

using namespace std;

Stack::Stack(int m){
top=-1;
stack=new char[m];
size = 0;
}

void Stack::clear(){
delete []stack;
size = 0;
stack=NULL;
}

Stack::~Stack(){
clear();
}

bool Stack ::push(char item){
top++;
stack[top]=item;
size++;
return true;
}

bool Stack::isempty(){
if(stack == NULL)
return true;
else
return false;
}

bool Stack::pop(){
if(isempty()){
cout<<"栈为空，不能执行出栈操作！"<<endl;
return false;
}
else{
top--;
size--;
return true;
}
}

int Stack::Size(){
return size;
}
char Stack::Top()
{
return stack[top];
}
#include<iostream>

using namespace std;
int main()
{
Stack s(20);
char a[50];
char *st = a;
int b=0;
cout<<"请输入你要检查的字符串："<<endl;
cin>>a;
while((*st)!='\0'){b++;
if((*st) == '('||(*st) == '{'||(*st) == '['){
cout<<endl;
cout<<*st<<" 为分隔符左半边"<<endl;
s.push((*st));
}
else if((*st) == '/'&&(*(st+1)) == '*'){
cout<<endl;
cout<<*st<<*(st+1)<<" 为分隔符左半边"<<endl;
s.push((*st));
s.push(*(st+1));
}

else if((*st) == ')'||(*st) == '}'||(*st) == ']'){
if(((*st) ==')'&& (s.Top() =='('))||((*st) =='}'&& (s.Top() =='{'))||((*st) ==']'&& (s.Top() =='['))){
cout<<*st<<" 为分隔符右半边"<<endl;
s.pop();
cout<<"匹配"<<endl;
cout<<endl;}
else {
cout<<*st<<" 为分隔符右半边"<<endl;
cout<<"但 "<<(*st)<<"不匹配"<<endl;
cout<<"第"<<b<<"位"<<endl<<endl;
}
}
else {if((*st) == '*'&&(*(st+1)) == '/'){
if(((*st)=='*')&&((s.Top())=='*')&&((*(st+1))=='/')){
cout<<*st<<*(st+1)<<" 为分隔符左半边"<<endl;
s.pop();
s.pop();
cout<<"匹配"<<endl;}
else{
cout<<*st<<*(st+1)<<" 为分隔符右半边"<<endl;
cout<<"但 "<<(*st)<<*(st+1)<<"不匹配"<<endl;
cout<<"第"<<b<<"位"<<endl<<endl;
}
}
}
st++;
}
if(s.size == 0){
cout<<"====================================="<<endl;
cout<<"分隔符匹配正确！"<<endl;
cout<<"====================================="<<endl;}
else
{
cout<<"====================================="<<endl;
cout<<"分隔符不匹配，请检查输入字符！"<<endl;
cout<<"====================================="<<endl;
}
return 0;
system("pause") ;

}