T1

队列循环列表表示栈
假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），请完成下列任务：
1: 队列初始化，成功返回真，否则返回假

bool init_queue(LinkQueue LQ);
2: 入队列，成功返回真，否则返回假：
bool enter_queue(LinkQueue *LQ, ElemType x);
3: 出队列，成功返回真，且x为出队的值，否则返回假
bool leave_queue(LinkQueue *LQ, ElemType *x);

相关定义如下：

typedef struct _QueueNode {
ElemType data; /数据域/
struct _QueueNode next; /*指针域/
}LinkQueueNode, *LinkQueue;

解析

Code

/*
 * 完成人　：岳昕峰(201909******4)
 * 完成时间：2020-03-26, Thu, 10:34:14
 * 最高分数：100
 */


#include "list.h" // 请不要删除，否则检查不通过
#include <stdio.h>
#include <stdlib.h>

bool init_queue(LinkQueue* LQ)
{
    *LQ = (LinkQueue)malloc(sizeof(LinkQueueNode));
    if (*LQ == NULL) {
        return 0;
    }
    (*LQ)->next = *LQ;
    return 1;
}

bool enter_queue(LinkQueue* LQ, ElemType x)
{
    if (*LQ == NULL) {
        return 0;
    }
    LinkQueueNode* p = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
    if (!p) {
        return 0;
    } else {
        p->data = x;
        p->next = (*LQ)->next;
        (*LQ)->next = p;
        *LQ = p;
        return 1;
    }
}

bool leave_queue(LinkQueue* LQ, ElemType* x)
{
    LinkQueue rear = (*LQ);
    if (rear->next == rear)
        return 0;
    (*x) = rear->next->next->data;
    if (rear->next->next == rear) {
        (*LQ) = (*LQ)->next;
        free(rear);
        (*LQ)->next = (*LQ);
        return 1;
    }
    LinkQueue temp = rear->next->next;
    rear->next->next = temp->next;
    free(temp);
    return 1;
}

T2

栈后缀表达式计算
请使用已定义好的栈完成后缀表达式计算：
(1)如果是操作数，直接入栈
(2)如果是操作符op，连续出栈两次，得到操作数x 和 y,计算 x op y，并将结果入栈。
后缀表达式示例如下：
9 3 1 - 3 * + 10 2 / +
13 445 + 51 / 6 -
操作数、操作符之间由空格隔开，操作符有 +，-，*, /, %共 5 种符号，所有操作数都为整型。
栈的定义如下：
#define Stack_Size 50
typedef struct{
```
ElemType elem[Stack_Size];
int top;
```
}Stack;

bool push(Stack* S, ElemType x);
bool pop(Stack* S, ElemType *x);
void init_stack(Stack *S);

其中，栈初始化的实现为：

void init_stack(Stack *S){
S->top = -1;
}

需要完成的函数定义为：

int compute_reverse_polish_notation(char *str);
函数接收一个字符指针，该指针指向一个字符串形式的后缀表达式，函数返回该表达式的计算结果。

解析

Code

/*
 * 完成人　：岳昕峰(201909******4)
 * 完成时间：2020-03-23, Mon, 19:19:11
 * 最高分数：100
 */


#include "list.h" // 请不要删除，否则检查不通过
#include <stdio.h>
#include <stdlib.h>

int compute_reverse_polish_notation(char* str)
{
    Stack s;
    init_stack(&s);
    int num = 0;
    while (*str != 0) {
        while (*str == ' ')
            str++;
        if (*str == 0) {
            break;
        }
        if (*str == '+') {
            int a, b;
            pop(&s, &a);
            pop(&s, &b);
            push(&s, a + b);
            str++;
        } else if (*str == '-') {
            int a, b;
            pop(&s, &a);
            pop(&s, &b);
            push(&s, b - a);
            str++;
        } else if (*str == '*') {
            int a, b;
            pop(&s, &a);
            pop(&s, &b);
            push(&s, a * b);
            str++;
        } else if (*str == '/') {
            int a, b;
            pop(&s, &a);
            pop(&s, &b);
            push(&s, b / a);
            str++;
        } else if (*str == '%') {
            int a, b;
            pop(&s, &a);
            pop(&s, &b);
            push(&s, b % a);
            str++;
        } else {
            int x = 0;
            do {
                x = x * 10 + *str - '0';
                str++;
            } while (*str >= '0' && *str <= '9' && *str != 0);
            push(&s, x);
        }
    }
    pop(&s, &num);
    return num;
}