2.5学习总结（补）

题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

本题中运算符仅包含 +-*/+-*/。保证对于 // 运算除数不为 0。特别地，其中 // 运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。

如：3*(5-2)+73*(5-2)+7 对应的后缀表达式为：3.5.2.-*7.+@3.5.2.-*7.+@。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。

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

#define MAX_SIZE 100

// 定义一个栈结构
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}

// 入栈操作
void push(Stack* s, int value) {
    s->data[++(s->top)] = value;
}

// 出栈操作
int pop(Stack* s) {
    return s->data[(s->top)--];
}

// 获取栈顶元素
int peek(Stack* s) {
    return s->data[s->top];
}

// 计算后缀表达式的值
int evaluatePostfix(char* expression) {
    Stack s;
    initStack(&s);
    int num = 0;
    int i = 0;
    while (expression[i] != '@') {
        if (expression[i] >= '0' && expression[i] <= '9') {
            // 提取操作数
            num = 0;
            while (expression[i] >= '0' && expression[i] <= '9') {
                num = num * 10 + (expression[i] - '0');
                i++;
            }
            push(&s, num);
        }
        else if (expression[i] == '.') {
            // 操作数结束，跳过
            i++;
        }
        else {
            // 遇到运算符
            int operand2 = pop(&s);
            int operand1 = pop(&s);
            switch (expression[i]) {
            case '+':
                push(&s, operand1 + operand2);
                break;
            case '-':
                push(&s, operand1 - operand2);
                break;
            case '*':
                push(&s, operand1 * operand2);
                break;
            case '/':
                push(&s, operand1 / operand2);
                break;
            }
            i++;
        }
    }
    return peek(&s);
}

int main() {
    char expression[MAX_SIZE];
    scanf("%s", expression);
    int result = evaluatePostfix(expression);
    printf("%d\n", result);
    return 0;
}

题目描述

一个学校里老师要将班上 NN 个同学排成一列，同学被编号为 1∼N1∼N，他采取如下的方法：

1. 先将 11 号同学安排进队列，这时队列中只有他一个人；

2. 2∼N2∼N 号同学依次入列，编号为 ii 的同学入列方式为：老师指定编号为 ii 的同学站在编号为 1∼(i−1)1∼(i−1) 中某位同学（即之前已经入列的同学）的左边或右边；

3. 从队列中去掉 MM 个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

输入格式

第一行一个整数 NN，表示了有 NN 个同学。

第 2∼N2∼N 行，第 ii 行包含两个整数 k,pk,p，其中 kk 为小于 ii 的正整数，pp 为 00 或者 11。若 pp 为 00，则表示将 ii 号同学插入到 kk 号同学的左边，pp 为 11 则表示插入到右边。

第 N+1N+1 行为一个整数 MM，表示去掉的同学数目。

接下来 MM 行，每行一个正整数 xx，表示将 xx 号同学从队列中移去，如果 xx 号同学已经不在队列中则忽略这一条指令。

#include <stdio.h>

#define mx 100010

// 定义结构体表示每个同学的信息
typedef struct {
    int l, r;  // 每个同学的“左右手” 
    int d;     // 表示同学是否输出 
} T;

T t[mx] = { 0 };

// 新增同学的函数
void add(int i, int k, int f) {
    if (f == 1) {  // 左
        t[k].r = t[i].r;
        t[k].l = i;
        t[i].r = k;
        t[t[k].r].l = k;
    }
    else {  // 右
        t[k].r = i;
        t[k].l = t[i].l;
        t[i].l = k;
        t[t[k].l].r = k;
    }
}

int main() {
    int n, m;
    int x, k, f;

    // 读取同学总数
    scanf("%d", &n);

    // 初始化编号为 0 的虚拟节点
    t[0].r = 0;
    t[0].l = 0;

    // 将编号为 1 的同学插入到编号为 0 的虚拟节点的左边
    add(0, 1,1);

    // 依次插入剩余的同学
    for (int i = 2; i <= n; i++) {
        scanf("%d %d", &x, &f);
        add(x, i, f);
    }

    // 读取要移除的同学数量
    scanf("%d", &m);

    // 标记要移除的同学
    while (m--) {
        scanf("%d", &x);
        t[x].d = 1;  // 将该同学标记为不输出 
    }

    // 输出未标记的同学
    for (int i = t[0].r; i; i = t[i].r) {
        if (t[i].d == 0) {  // 输出未标记的 
            printf("%d ", i);
        }
    }

    printf("\n");

    return 0;
}