c语言使用字母I和O分别表示PUSH和POP操作。堆栈的初始状态和结束状态都应为空,一个PUSH和POP操作序列仅由I和O组成的序列表示。这种序列只有在具有可操作性时才是合法的,否则就是非法的。写一个算法来判断下列序列是否合法。
时间: 2024-05-14 10:12:25 浏览: 15
可以使用一个计数器来模拟堆栈的状态,当遇到字母I时,将计数器加1表示入栈,当遇到字母O时,将计数器减1表示出栈。如果计数器小于0,说明出现了非法的POP操作,如果计数器大于0,说明堆栈没有完全出栈,也是非法的。最后判断计数器是否为0即可。
具体实现如下:
```c
#include <stdio.h>
int main() {
char str[100];
int count = 0;
printf("请输入操作序列:");
scanf("%s", str);
for (int i = 0; str[i] != '\0'; i++) {
if (str[i] == 'I') {
count++;
} else if (str[i] == 'O') {
count--;
}
if (count < 0) {
printf("非法操作序列\n");
return 0;
}
}
if (count == 0) {
printf("合法操作序列\n");
} else {
printf("非法操作序列\n");
}
return 0;
}
```
测试样例:
输入:IOIOIOI
输出:合法操作序列
输入:IOIIOO
输出:非法操作序列
相关问题
c语言实现堆栈的初始化,压栈,出栈,判空操作
堆栈(Stack)是一种线性数据结构,具有“后进先出”的特点,可以使用数组或链表来实现。下面是使用数组实现堆栈的初始化、压栈、出栈和判空操作的C语言代码:
```c
#include <stdio.h>
#define MAXSIZE 100 // 定义栈的最大长度
typedef struct {
int data[MAXSIZE]; // 存储元素的数组
int top; // 栈顶指针
} Stack;
// 初始化堆栈
void InitStack(Stack *S) {
S->top = -1; // 栈顶指针初始化为-1
}
// 判断堆栈是否为空
int IsEmpty(Stack *S) {
if (S->top == -1) {
return 1; // 栈为空
} else {
return 0; // 栈不为空
}
}
// 压栈操作
void Push(Stack *S, int x) {
if (S->top == MAXSIZE - 1) {
printf("栈已满,无法插入元素!\n");
return;
}
S->data[++S->top] = x;
}
// 出栈操作
int Pop(Stack *S) {
if (S->top == -1) {
printf("栈已空,无法删除元素!\n");
return -1;
}
return S->data[S->top--];
}
```
使用方法:
```c
int main() {
Stack S;
InitStack(&S); // 初始化堆栈
Push(&S, 1); // 压入元素1
Push(&S, 2); // 压入元素2
int x = Pop(&S); // 出栈,x的值为2
printf("%d\n", x);
x = Pop(&S); // 出栈,x的值为1
printf("%d\n", x);
x = Pop(&S); // 栈已空,无法删除元素!
return 0;
}
```
要求编写功能函数实现堆栈的定义,分别基于顺序栈和链栈:输入元素,编写进栈函数push();编写出栈函数pop();编写判断栈满和栈空的函数 ;遍历栈,并输出元素;实现十进制到二进制的转换。c语言实现完整代码
基于顺序栈的实现:
```
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 // 定义栈的最大容量
typedef struct{
int data[MAXSIZE]; // 存储栈元素
int top; // 栈顶指针
}SqStack;
// 初始化栈
void InitStack(SqStack *S)
{
S->top = -1;
}
// 进栈
int Push(SqStack *S, int elem)
{
if(S->top == MAXSIZE-1) // 判断栈是否已满
return 0;
S->top++; // 栈顶指针加1
S->data[S->top] = elem; // 将元素压入栈顶
return 1;
}
// 出栈
int Pop(SqStack *S, int *elem)
{
if(S->top == -1) // 判断栈是否为空
return 0;
*elem = S->data[S->top];// 将栈顶元素弹出
S->top--; // 栈顶指针减1
return 1;
}
// 判断栈是否为空
int IsEmpty(SqStack S)
{
if(S.top == -1)
return 1;
return 0;
}
// 判断栈是否已满
int IsFull(SqStack S)
{
if(S.top == MAXSIZE-1)
return 1;
return 0;
}
// 遍历栈,并输出元素
void Traverse(SqStack S)
{
int i;
for(i=S.top; i>=0; i--)
printf("%d ", S.data[i]);
printf("\n");
}
// 十进制转二进制
void DecToBin(int dec)
{
SqStack S;
InitStack(&S);
while(dec){
Push(&S, dec%2);
dec /= 2;
}
while(!IsEmpty(S)){
int elem;
Pop(&S, &elem);
printf("%d", elem);
}
}
int main()
{
int elem;
SqStack S;
InitStack(&S);
Push(&S, 1);
Push(&S, 2);
Push(&S, 3);
Pop(&S, &elem);
Traverse(S);
DecToBin(10);
return 0;
}
```
基于链栈的实现:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
int data; // 存储栈元素
struct LNode *next; // 指向下一个结点的指针
}LNode, *LinkStack;
// 初始化栈
void InitStack(LinkStack *S)
{
*S = NULL;
}
// 进栈
int Push(LinkStack *S, int elem)
{
LNode *p = (LNode*)malloc(sizeof(LNode)); // 创建新结点
p->data = elem;
p->next = *S;
*S = p;
return 1;
}
// 出栈
int Pop(LinkStack *S, int *elem)
{
if(*S == NULL)
return 0;
LNode *p = *S;
*elem = p->data;
*S = p->next;
free(p);
return 1;
}
// 判断栈是否为空
int IsEmpty(LinkStack S)
{
if(S == NULL)
return 1;
return 0;
}
// 遍历栈,并输出元素
void Traverse(LinkStack S)
{
LNode *p = S;
while(p){
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 十进制转二进制
void DecToBin(int dec)
{
LinkStack S;
InitStack(&S);
while(dec){
Push(&S, dec%2);
dec /= 2;
}
while(!IsEmpty(S)){
int elem;
Pop(&S, &elem);
printf("%d", elem);
}
}
int main()
{
int elem;
LinkStack S;
InitStack(&S);
Push(&S, 1);
Push(&S, 2);
Push(&S, 3);
Pop(&S, &elem);
Traverse(S);
DecToBin(10);
return 0;
}
```
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)