PTA-学校-数据结构（括号匹配、进制转换、用链栈实现将非负的十进制数转换为指定的进制数、在一个数组中实现两个堆栈）

1-1 括号匹配

分数 4

作者 黄龙军

单位 绍兴文理学院

要求实现函数，借助如下自定义栈SqStack判断一个中、小括符[、]、(、)组成的字符串中的括弧是否匹配，是则返回true，否则返回false。例如，[[()]]、([[()]])、(()[[]])是匹配的，而(((、()]、 ([(]))是不匹配的。

typedef char ElemType;                    // 为char取别名ElemType
struct SqStack{
    ElemType  *base;                      // 顺序栈的首地址，动态数组的首地址
    int top;                              // 栈顶指针，栈非空时，为栈顶元素的下标(从0开始)
    void Init( );                         // 初始化栈
    ElemType GetTop();                    // 取栈顶元素    
    void Push(ElemType e);                // 入栈
    void Pop();                           // 出栈
    bool Empty();                         // 判断空栈
};

函数接口定义：

bool matching(string exp);

其中参数 exp是一个仅包含中、小括符[、]、(、)的字符串。

裁判测试程序样例：

#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    while(cin>>s){
        if (matching(s)) cout<<"yes\n";
        else cout<<"no\n";
    } 
    return 0;
}

输入样例：

()[]
[()]
[(()]]
[(])

输出样例：

yes
yes
no
no

解析

bool matching(string exp) {
    SqStack stack;
    stack.Init();

    for (char c : exp) {
        if (c == '(' || c == '[') {
            stack.Push(c);
        }
        else {
            if (stack.Empty()) {
                return false;
            }
            char top = stack.GetTop();
            if ((c == ')' && top == '(') || (c == ']' && top == '[')) {
                stack.Pop();
            }
            else {
                return false;
            }
        }
    }
    if (stack.Empty()) {
        return true;
    }
    else {
        return false;
    }
}

注意

for (char c : exp) 是 C++11 引入的范围 for 循环（也叫 foreach 循环），用于遍历容器或字符串中的每个元素，语法简洁直观。

针对你的代码场景：

在 matching 函数中，exp 是一个 string 类型（字符串），for (char c : exp) 的作用是：逐个取出字符串 exp 中的每个字符，依次赋值给变量 c，并执行循环体内的代码。

举例说明：

假设 exp = "()[]"，循环会依次执行 4 次：

1. 第 1 次：c = '('（字符串第 0 个字符）
2. 第 2 次：c = ')'（字符串第 1 个字符）
3. 第 3 次：c = '['（字符串第 2 个字符）
4. 第 4 次：c = ']'（字符串第 3 个字符）

循环结束后，所有字符都被遍历完毕。

与传统 for 循环的对比：

传统遍历字符串的方式需要通过下标访问：

for (int i = 0; i < exp.size(); i++) {
    char c = exp[i];  // 通过下标 i 取出第 i 个字符
    // 循环体操作
}

范围 for 循环 for (char c : exp) 本质上是上述代码的简化版，无需手动管理下标，更简洁且不易出错，尤其适合遍历整个容器 / 字符串的场景。

注意点：

• 循环变量 c 是字符串中字符的副本，如果需要修改原字符串中的字符，需使用引用 char& c。
• 循环会遍历字符串中的所有字符，无法跳过或反向遍历（如需复杂遍历，仍需用传统 for 循环）。

在你的括号匹配代码中，只需依次检查每个字符，范围 for 循环是最合适的选择，让代码更简洁易读。

1-2 进制转换

分数 4

作者 YJ

单位 西南石油大学

设计一个顺序栈，并利用该顺序栈将给定的十进制整整数转换为二进制输出。

函数接口定义：

Status SPush( SqStack &s,ElemType x);
Status SPop( SqStack &s,int &e );

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;

typedef struct{
    ElemType *data;    //存储元素的数组
    int top;           //栈顶指针
    int stacksize;       //栈最大容量
}SqStack;

void CreateStack(SqStack &s)
{
    s.data= (ElemType *)malloc(MaxSize*sizeof(ElemType));
        s.top=0;
    s.stacksize=MaxSize;
}

Status SPush( SqStack &s, ElemType x );  
Status SPop( SqStack &s,int &e );

int main()
{
    SqStack s;
    int N,e;
    CreateStack(s);
    scanf("%d", &N);
    while (N) {
        if(SPush(s,N%2))
           N=N/2;
        else{ 
            printf("stack is overflow!\n");
           return 0;
      }
    }
while(SPop(s,e))
   printf("%d",e);
printf("\n");
return 0;
}
/* 请在这里填写答案 */

输入样例：

1023

输出样例：

1111111111

解析

Status SPush(SqStack& s, ElemType x) {
    if (s.top == s.stacksize) {
        return ERROR;
    }
    else {
        s.data[s.top] = x;
        s.top++;
        return OK;
    }
}
Status SPop(SqStack& s, int& e) {
    if (s.top == 0) {
        return ERROR;
    }
    else {
        s.top--;
        e = s.data[s.top];
        return OK;
    }
}

注意

因 top 指向栈顶元素的下一个位置（如入栈 1 个元素后，top=1，栈顶元素在下标 0 处），此时取 s.data[s.top] 会访问到未赋值的内存（top 位置无元素），导致输出错误。

正确逻辑应先 top--，再取 s.data[top]（因为 top-- 后才指向栈顶元素）。

1-3 用链栈实现将非负的十进制数转换为指定的进制数

分数 3

作者 CUIT通信DS课程组

单位 成都信息工程大学

利用链序栈将输入的非负的十进制数N转换为指定的d（二、八或十六）进制数。

链栈的定义如下：

typedef struct SNode
{  
     DataType data;      // 数据域
     struct SNode *next; // 指向后继结点的指针域
}SNode,*LinkStack;    

函数接口定义：

int DecimalConvert(LinkStack s, int dec, int scale);

函数参数说明：形参–s、dec、scale，其中，s是存放转换后的scale进制数的各位数字，dec 主函数输入的待转换的十进制数，scale是指定的数制（只能是2、8或16）。 函数返回值：1，表示函数执行完成；0，表示函数未成功执行。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;
typedef struct SNode
{
    DataType data;        // 数据域
    struct SNode* next;        // 指向后继结点的指针域
}SNode, * LinkStack;

int InitLinkStack(LinkStack* top)
{  /* 初始化链栈 */
    *top = (LinkStack)malloc(sizeof(SNode));
    if (*top == NULL)
    {
        printf("初始化链栈出错");
        return 0;
    }
    (*top)->next = NULL;
    return  1;
}
int LinkStackEmpty(LinkStack top)
{ /* 判栈空函数 */
    if (top->next == NULL)
        return 1;
    else
        return 0;
}
int LinkStackPush(LinkStack top, DataType e)
{ /* 压栈函数 */
    SNode* p;
    p = (SNode*)malloc(sizeof(SNode));
    if (!p)
    {
        printf("入栈操作出错！\n");
        return 0;
    }
    p->data = e;
    p->next = top->next;
    top->next = p;
    return 1;
}
int LinkStackPop(LinkStack top, DataType* e)
{ /* 弹栈函数 */
    SNode* p;
    if (!top->next)
    {
        printf("栈已空，无法完成出栈操作！\n");
        return 0;
    }
    p = top->next;
    top->next = p->next;
    *e = p->data;
    free(p);
    return 1;
}
/* 本题要求函数 */
int DecimalConvert(LinkStack s, int dec, int scale);
int main()
{
    LinkStack s;
    char ch[] = "0123456789ABCDEF";  //二、八、十六进制所使用的数字
    unsigned dec, scale;
    DataType tmp;

    InitLinkStack(&s);
    scanf("%d %d", &dec, &scale);  // 某些编译器要求此处改为scanf_s

    if (DecimalConvert(s, dec, scale))
    {
        printf("十进制数:%d,转换为:%d进制数,结果为:", dec, scale);
        while (!LinkStackEmpty(s))
        {
            LinkStackPop(s, &tmp);
            printf("%c", ch[tmp]);
        }
    }
    else
        printf("数制转换未成功！");

    return 0;
}
/* 请在这里填写答案 */

输入样例：

20 2

输出样例：

十进制数:20,转换为:2进制数,结果为:10100

输入样例：

20 8

输出样例：

十进制数:20,转换为:8进制数,结果为:24

输入样例：

20 16

输出样例：

十进制数:20,转换为:16进制数,结果为:14

解析

int DecimalConvert(LinkStack s, int dec, int scale) {
    LinkStack q = s;
    if (dec == 0) {
        LinkStackPush(s, 0);
        return 1;
    }
    if (scale != 2 && scale != 8 && scale != 16) {
        return 0;
    }
    int check = dec;
    int in = 1;
    while (check != 0) {
        in = check % scale;
        check = check / scale;
        LinkStackPush(s, in);
    }
    return 1;
}

注意

函数题可以直接使用题目给的函数

1-4 在一个数组中实现两个堆栈

分数 4

作者 陈越

单位 浙江大学

本题要求在一个数组中实现两个堆栈。

函数接口定义：

Stack CreateStack( int MaxSize );
bool Push( Stack S, ElementType X, int Tag );
ElementType Pop( Stack S, int Tag );

其中Tag是堆栈编号，取1或2；MaxSize堆栈数组的规模；Stack结构定义如下：

typedef int Position;
struct SNode {
    ElementType *Data;
    Position Top1, Top2;
    int MaxSize;
};
typedef struct SNode *Stack;

注意：如果堆栈已满，Push函数必须输出“Stack Full”并且返回false；如果某堆栈是空的，则Pop函数必须输出“Stack Tag Empty”（其中Tag是该堆栈的编号），并且返回ERROR。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

#define ERROR 1e8
typedef int ElementType;
typedef enum { push, pop, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
struct SNode {
    ElementType *Data;
    Position Top1, Top2;
    int MaxSize;
};
typedef struct SNode *Stack;

Stack CreateStack( int MaxSize );
bool Push( Stack S, ElementType X, int Tag );
ElementType Pop( Stack S, int Tag );

Operation GetOp();  /* details omitted */
void PrintStack( Stack S, int Tag ); /* details omitted */

int main()
{
    int N, Tag, X;
    Stack S;
    int done = 0;

    scanf("%d", &N);
    S = CreateStack(N);
    while ( !done ) {
        switch( GetOp() ) {
        case push: 
            scanf("%d %d", &Tag, &X);
            if (!Push(S, X, Tag)) printf("Stack %d is Full!\n", Tag);
            break;
        case pop:
            scanf("%d", &Tag);
            X = Pop(S, Tag);
            if ( X==ERROR ) printf("Stack %d is Empty!\n", Tag);
            break;
        case end:
            PrintStack(S, 1);
            PrintStack(S, 2);
            done = 1;
            break;
        }
    }
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

5
Push 1 1
Pop 2
Push 2 11
Push 1 2
Push 2 12
Pop 1
Push 2 13
Push 2 14
Push 1 3
Pop 2
End

输出样例：

Stack 2 Empty
Stack 2 is Empty!
Stack Full
Stack 1 is Full!
Pop from Stack 1: 1
Pop from Stack 2: 13 12 11

解析

/* 你的代码将被嵌在这里 */
Stack CreateStack(int MaxSize) {
    Stack p = (Stack)malloc(sizeof(struct SNode));
    p->Data = (ElementType*)malloc(MaxSize * sizeof(ElementType));
    p->MaxSize = MaxSize;
    p->Top1 = -1;
    p->Top2 = MaxSize;
    return p;
}
bool Push(Stack S, ElementType X, int Tag) {
    if (S->Top1 + 1 == S->Top2) {
        printf("Stack Full\n");
        return false;
    }
    if (Tag == 1) {
        S->Top1++;
        S->Data[S->Top1] = X;
    }
    else if(Tag == 2) {
        S->Top2--;
        S->Data[S->Top2] = X;
    }
    else {
        return false;
    }
    return true;
}
ElementType Pop(Stack S, int Tag) {
    if (Tag == 1) {
        if (S->Top1 == -1) {
            printf("Stack %d Empty\n", Tag);
            return ERROR;
        }
        else {
            int t;
            t = S->Data[S->Top1];
            S->Top1--;
            return t;
        }
    }
    else if (Tag == 2) {
        if (S->Top2 == S->MaxSize) {
            printf("Stack %d Empty\n", Tag);
            return ERROR;
        }
        else {
            int t;
            t = S->Data[S->Top2];
            S->Top2++;
            return t;
        }
    }
    else {
        return ERROR;
    }
}

注意

两个栈是从数组两边开始的，所以top1和top2一个是-1一个是MAXSIZE

栈满条件是top1+1==top2