题目
假设以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
TIM图片20191101110559.png
