习题3.5

5．假设以Ⅰ和О分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和О组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
(1)下面所示的序列中哪些是合法的?
A.IOIIOIOO
B.IOOIOIIO
C.IIIOIOIO
D.IIIOOIOO
(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true,否则返回false（假定被判定的操作序列已存入一维数组中)。

(1)在入栈出栈的过程中，需要满足在入栈出栈序列的任一位置，入栈次数即“I”的个数,必须大于或等于出栈次数即“O”的个数，否则视作非法序列。经检验，A和D是合法序列，B和C是非法序列。

完整代码：

#include <iostream>
#include <string.h>
using namespace std;
typedef int Status;
typedef int TypeStack;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX 100 //栈空间初始大小

//顺序栈
typedef struct SqStack
{
    TypeStack *top;  //栈顶指针
    TypeStack *base; //栈底指针
    int size;        //当前栈空间的大小
} SqStack;


bool Judge(char *A);

bool EmptyStack(SqStack S)
{

    if (S.top == S.base)

        return true;

    else
        return false;
}

Status InitStack(SqStack &S)
{
    S.base = new TypeStack[MAX];
    if (!S.base)
        exit(OVERFLOW);
    S.top = S.base;
    S.size = MAX;
    return OK;
}

Status push(SqStack &S, TypeStack e)
{
    if (S.top - S.base == S.size)
    {
        cout << "栈满！" << endl;
        return ERROR;
    }
    *S.top = e;
    *S.top++;
    return OK;
}

Status Pop(SqStack &S, TypeStack &e)
{
    if (S.top == S.base)
    {
        cout << "栈为空" << endl;
        return ERROR;
    }
    *--S.top;
    e = *S.top;
    return OK;
}

TypeStack GetTop(SqStack S)
{
    if (S.top != S.base)
        return *(S.top - 1);
}

Status PrintStack(SqStack S)
{
    TypeStack *x = S.base;
    while (x < S.top)
    {
        cout << *x << " ";
        x++;
    }
    return OK;
}

Status somepush(SqStack &S)
{
    int num;
    int i = 0;
    TypeStack n;
    cout << "输入元素个数n,初始化栈" << endl;
    cin >> num;
    cout << "请依次输入元素:" << endl;
    while (1)
    {
        cin >> n;
        push(S, n);
        i++;
        if (i == num)
            break;
    }
}

int readchar(char *t)
{
   
   int i=0,num=0;
   char c;
   while (1)
   {
     t[i]=cin.get(); 
     
     i++;
     if(t[i-1]=='\n')
     {
        i--;
        break;
     }
     
   }
    num=i-1;
    return i;

}

int main()
{
    
    SqStack S;
    InitStack(S);
   char x[100];
   readchar(x);
   Judge(x);

    
    

    return 0;
}

bool Judge(char *A)
{
    int j=0;
    int i=0,k=0;
    j=k=0;
    while(A[i]!='\0')
    {
        switch(A[i])
        {
            case 'I':j++;break;
            case 'O':k++;
            if(k>j)
            {
                cout<<"序列非法"<<endl;
                return false;
            }
        }
        i++;

    }
    if(k!=j)
    {
        cout<<"非法序列"<<endl;
        return false;

    }
    else
    {
        cout<<"序列合法"<<endl;
        return true;
    }
}