Problem Description
假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则成为非法序列。请编写一个对该操作序列的有效性进行判断，若有效输出1，无效输出0。
Input
有多组数据，每组为由I和O组成的序列，序列长度不超过50。
Output
操作序列有效输出1，无效输出0。
Sample Input
IOIIOIOO
IOOIOIIO
Sample Output
1
0
Hints
注意分析多种情况，栈在操作的开始和结束均要求为空。
#include <iostream>
#include<stdio.h>
#include<string.h>
const int MAX=51;
using namespace std;
class Stack {
private:
struct node {
char data;
node* next;
node() {
next=NULL;
}
};
node* head;
public:
Stack() {
head=new node;
}
void push(char c) {
node* s=new node;
s->data=c;
s->next=head;
head=s;
}
char pop() {
char c='\0';
if(head!=NULL) {
node* temp=head;
c=head->data;
head=head->next;
delete temp;
}
return c;
}
int Length() {
int length=0;
node* p=head;
while(p->next&&++length) {
p=p->next;
}
return length;
}
bool isEmpty() {
return head->next==NULL?true:false;
}
};
int main() {
char str[MAX];
while(cin>>str) {
Stack* stack=new Stack();
int flag=1;
for(int i=0; i<strlen(str); i++) {
if(str[i]!='O'&&str[i]!='I') {
flag=0;
break;
}
}
if(flag) {
for(int i=0; i<strlen(str); i++) {
if(str[i]=='I')
stack->push(str[i]);
else if(str[i]=='O') {
if(!stack->isEmpty())
stack->pop();
else {
flag=0;
break;
}
}
}
if(!stack->isEmpty())
flag=0;
}
if(flag)
cout<<"1"<<endl;
else
cout<<"0"<<endl;
delete stack;
}
return 0;
}
