栈和队列算法设计题（二）

题目

假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作顺序可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

算法思想

假定被判定的操作序列存入字符串数组中A中，从数组中的第一个元素开始对数组中的元素逐一进行判断，直到字符串末尾。如果当前字符为“I”，则入栈j次数增1，如果为“O”，则出栈次数增1.在判断过程中，如果出现k大于j，则序列非法，不比继续判断，返回false；在到达字符串末尾后，如果k不等于j，则序列非法，返回false；否则序列合法，返回true。

完整代码

#include <iostream>
#define MAXSIZE 100
using namespace std;

//假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作顺序可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
//写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。 

bool Judge(char A[]){
    //判断A中的输入输出序列是否是合法序列。如果是，返回true，否则返回false
    int i = 0;                                     //i为下标 
    int j = 0;
    int k = 0;                                     //j和k分别为I和字母O的个数 
    while(A[i] != '\0'){                           //未到字符数组尾时判断序列是否合法 
        switch(A[i]){
            case 'I' :
                j ++;                              //入栈次数增1 
                break;
            case 'O' :
                k ++;
            if(k > j){
                cout << "序列非法" << endl;
                return false;
            }
        }
        i ++;                                      //不论A[i]是‘I’或‘O’，指针i均后移 
    }
    if(k != j){
        cout << "序列非法" << endl;
        return false;
    }
    else{
        cout << "序列合法" << endl;
        return true;
    }
}

int main(){
    char A[MAXSIZE];
    int n;
    cout << "Input the length:";
    cin >> n;
    cout << "Input the elements:" << endl;
    for(int i = 0; i < n; i ++){
        cin >> A[i];
    }
    Judge(A);
    return 0;
}

结果显示

TIM图片20191101110559.png