栈与队列题目
第一题
题目
问题描述】设计一个算法判别一个算术表达式的圆括号是否正确配对
【输入形式】一个以@为结尾的算术表达式
【输出形式】若配对,则输出圆括号的对数;否则输出no
【样例输入】
(a+b)/(c+d)@
【样例输出】
2
【样例说明】共有两对括号,输出2
#include <iostream>
using namespace std;template <class T>
class stack{ //这里不需要写<T> public: stack(int max);bool Push(T& a);bool Pop();T top();private:int max;int count;int front; T* element;
};template <class T>
stack<T>::stack(int max){element = new T[max]; //这里要写T类型的数组 front=-1;count=0;
}
template <class T>
bool stack<T>::Push(T& num){count++;front++;element[front]= num; //element怎么用?? return true;
}template <class T>
bool stack<T>::Pop(){front--;count--;return true;
}template <class T>
T stack<T>::top(){return element[front];
}int main(){string str;int flag=1,count=0;stack<char> s(10);getline(cin,str,'@');for(int i=0;i<str.length();i++){if(str[i]=='(')s.Push(str[i]);else if(str[i]==')'){if(s.top()=='('){s.Pop();count++;}else{flag=0;break;}}} if(flag==0)cout<<"no"<<endl;elsecout<<count<<endl;
}
样例不通过的点:
分析:
但是我欠缺考虑了多了左括号和多了右括号的情况!!!!
1.当左括号多余时,那么就是前面的括号全部抵消之后,但是最后栈里边还有元素
2.当右括号多余时,那么就是当右括号还想匹配时,却发现栈已经空了,这两种情况都是我需要考虑的,所以经过改进之后
代码如下
#include <iostream>
using namespace std;//只要理清楚了,就很简单的,说服自己,但是身体好累 template <class T>
class stack{ //这里不需要写<T> public: stack(int max);bool Push(T& a);bool Pop();T top();int Size();private:int max;int count;int front; T* element;
};template <class T>
stack<T>::stack(int max){element = new T[max]; //这里要写T类型的数组 front=-1;count=0;
}template <class T>
int stack<T>::Size(){return count;
}template <class T>
bool stack<T>::Push(T& num){count++;front++;element[front]= num; //element怎么用?? return true;
}template <class T>
bool stack<T>::Pop(){front--;count--;return true;
}template <class T>
T stack<T>::top(){return element[front];
}int main(){string str;int flag=1,count=0;stack<char> s(10);getline(cin,str,'@');for(int i=0;i<str.length();i++){if(str[i]=='(')s.Push(str[i]);else if(str[i]==')'){if(s.top()=='('){s.Pop();count++;}else if(s.Size()==0){flag=0;break;}else{flag=0;break;}}} if(s.Size()!=0)cout<<"no"<<endl; else if(flag==0)cout<<"no"<<endl;elsecout<<count<<endl;
}
最主要是改变了一下下边这样的两个判断输出语句
if(s.top()=='('){s.Pop();count++;}else if(s.Size()==0){flag=0;break;}else{flag=0;break;}if(s.Size()!=0)cout<<"no"<<endl;