7.栈

第一章自测&关键词回顾

视频

计算后缀表达式

遇到数字, 直接入栈
遇到符号, 弹出两个数字, 计算后, 再将结果入栈
- 注意❗: 第二个弹出的操作数操作符第一个弹出的操作数 是反的(因为在将中缀表达式转换为后缀表达式的过程中，操作数的顺序被保留了, 只是操作符的顺序变了)
  
  中转后
如果遇到了数字, 直接变后缀串; 如果是符号; 看优先级(处理见下图)
如果遇到了左括号, 入栈; 如果右括号; 出栈(直到栈内的左括号出栈为止)
最后, 将剩余的弹出即可

第二章手撕

第一节链表实现栈

// 单链表(有头,头节点存储栈的元素个数) 实现 栈
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

typedef int DataType;
typedef struct LinkStackNode {
    DataType data;
    struct LinkStackNode *next;
} LinkStackNode;

// 创建栈
LinkStackNode *initStack();
// 销毁
void destroy(LinkStackNode *stack);
// 遍历
void traverse(LinkStackNode *stack);
// 入栈
void push(LinkStackNode *stack, DataType data);
// 出栈
void pop(LinkStackNode *stack);
// 获取栈顶元素
DataType top(LinkStackNode *stack);
// 判空
bool empty(LinkStackNode *stack);
// 栈元素个数(突然发现,用有头的会好点😅)
int size(LinkStackNode *stack);

#include "stack.h"

// 创建栈
LinkStackNode *initStack() {
    // 初始没有数值, 返回表头即可
    LinkStackNode *stackHead = (LinkStackNode *)malloc(sizeof(LinkStackNode));
    stackHead->data = 0;
    stackHead->next = NULL;
    return stackHead;
}
// 入栈
void push(LinkStackNode *stack, DataType data) {
    LinkStackNode *newNode = (LinkStackNode *)malloc(sizeof(LinkStackNode));
    newNode->data = data;
    // 头插法
    newNode->next = stack->next;
    stack->next = newNode;

    stack->data++;  // 栈的大小++
}
// 销毁
void destroy(LinkStackNode *stack) {
    // 之前链表那块实现,都是借用2个临时变量;这里只用一个试试;
    while (stack->next) {
        //  这里相当于一直"头删"
        LinkStackNode *temp = stack->next;
        stack->next = stack->next->next;
        free(temp);
    }
    free(stack);  // 最后把"哨兵头"删掉
}
// 遍历
void traverse(LinkStackNode *stack) {
    LinkStackNode *pmove = stack->next;
    while (pmove) {
        printf("%d\n", pmove->data);
        pmove = pmove->next;
    }
    printf("End Size:%d\n", stack->data);
}
// 出栈
void pop(LinkStackNode *stack) {
    assert(stack->data && "illegal!!!! stack is empty!");
    // 头删
    LinkStackNode *temp = stack->next;  // 存储起来,等会释放
    stack->next = stack->next->next;    // 已经保证不为空了
    stack->data--;                      // 栈的大小--
    free(temp);
}
// 获取栈顶元素
DataType top(LinkStackNode *stack) {
    assert(stack->data && "illegal!!!! stack is empty!");
    return stack->next->data;
}
// 判空
bool empty(LinkStackNode *stack) { return stack->data==0; }
// 栈元素个数(突然发现,用有头的会好点😅)
int size(LinkStackNode *stack) { return stack->data; }

把你写的接口, 丢上去测测, AC就手搓的没问题题目LINK

#include "stack.h"

// https://www.luogu.com.cn/problem/U295781
void oj() {
    int n;
    scanf("%d", &n);

    LinkStackNode *stack = initStack();
    while (n--) {
        char instruction[100];
        scanf("%s", instruction);

        // 1.push x – 向栈顶插入一个数 x ；
        if (!strcmp(instruction, "push")) {
            int x;
            scanf("%d", &x);
            push(stack, x);
        }
        // 2.pop – 从栈顶弹出一个数；
        else if (!strcmp(instruction, "pop")) {
            pop(stack);
        }
        // 3.empty – 判断栈是否为空；
        else if (!strcmp(instruction, "empty")) {
            printf("%s\n", empty(stack) ? "YES" : "NO");
        }
        // 4.query – 查询栈顶元素。
        else if (!strcmp(instruction, "query")) {
            printf("%d\n", top(stack));
        }
    }
    destroy(stack);
}

int main() {
    oj();

    return 0;
}

第二节数组实现栈

把你写的接口, 丢上去测测, AC就手搓的没问题题目LINK

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

#define DataType int

typedef struct Stack {
    DataType *stack;
    int head;  // 永远指向栈顶
    int maxSize;
} Stack;

// 一.初始化
Stack *init(int maxSize) {
    Stack *myStack = (Stack *)malloc(sizeof(Stack));
    myStack->stack = (DataType *)malloc(sizeof(DataType) * maxSize);
    myStack->maxSize = maxSize;
    myStack->head = -1;
    return myStack;
}
// 二.压栈
void push(Stack *myStack, DataType data) {
    assert(!(myStack->head == myStack->maxSize - 1) && "Stack is over maxSize!");
    myStack->stack[++myStack->head] = data;
}
// 三.出栈
void pop(Stack *myStack) {
    assert(!(myStack->head == -1) && " illegal stack is empty");
    myStack->head--;
}
// 四.遍历
void traverse(Stack *myStack) {
    for (int i = myStack->head; i >= 0; i--) {
        printf("%d\n", myStack->stack[i]);
    }
    puts("END");
}
// 五.取栈顶元素
DataType top(Stack *myStack) {
    return myStack->stack[myStack->head];
}
// 六.判空
bool empty(Stack *myStack) {
    return myStack->head == -1;
}
// 七.栈的大小
int size(Stack *myStack) {
    return myStack->head + 1;
}

void oj(void);  // https://www.luogu.com.cn/problem/U295781
int main() {
    oj();
    return 0;
}

void oj(void) {
    int n;
    scanf("%d", &n);
    Stack *stack = init(1000);
    while (n--) {
        char instruction[100];
        scanf("%s", instruction);
        // 1.push x – 向栈顶插入一个数 x ；
        if (!strcmp(instruction, "push")) {
            int x;
            scanf("%d", &x);
            push(stack, x);
        }
        // 2.pop – 从栈顶弹出一个数；
        else if (!strcmp(instruction, "pop")) {
            pop(stack);
        }
        // 3.empty – 判断栈是否为空；
        else if (!strcmp(instruction, "empty")) {
            printf("%s\n", empty(stack) ? "YES" : "NO");
        }
        // 4.query – 查询栈顶元素。
        else if (!strcmp(instruction, "query")) {
            printf("%d\n", top(stack));
        }
    }
}

第三章相关应用

第一节括号匹配问题

力扣: 有效的括号

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

#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define N 10100
char stack[N];
int top = -1;
char leftParen[] = {'(', '[', '{'};
char rightParen[] = {')', ']', '}'};
/** 判断另一半的括号
 * aim: 栈中弹出的括号
 * x: 右括号
 */
bool isApart(char aim, char x) {
    // 1.如果x是左括号, 一定不对 2.如果x和aim不匹配, 也不对
    for (int i = 0; i < SIZE(leftParen); i++) {
        if (x == rightParen[i] && aim == leftParen[i]) {
            return true;
        }
    }
    return false;
}

bool isValid(char *s) {
    top = -1;
    for (int i = 0; i < strlen(s); i++) {
        // 判断左右括号(没有set数据结构)
        int flag = 0;  // 1表示是左括号, 0表示是右括号
        for (int j = 0; j < SIZE(leftParen); j++) {
            // case1: 左括号
            if (leftParen[j] == s[i]) {
                stack[++top] = s[i];
                flag = 1;
                break;
            }
        }
        // case2: 右括号
        if (top==-1||(!flag && !isApart(stack[top--], s[i])))
            return false;
    }
    return top==-1;
}

第二节表达式求值

/**在"栈"的应用中,都用数组栈,简单封装 */
// 1. 计算算术表达式
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define N 1000

char stack[N];  // 栈
int head = -1;

int isOperator(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;  // 1级操作符
        case '*':
        case '/':
            return 2;  // 2级操作符
        default:
            return -1;  // 不是操作符
    }
}

// 1.中缀表达式=>后缀表达式 (原始)
char *convertInfix2Postfix(char *infixExpression) {
    char *postfixExpression = (char *)malloc(sizeof(char) * N);
    char *pmove = postfixExpression;

    int i = 0;
    while (i < strlen(infixExpression)) {
        // case1:如果是数字,直接写入"后缀表达式"
        if (isdigit(infixExpression[i])) {
            // STEP1:读取完整数字
            while (isdigit(infixExpression[i])) {
                *pmove++ = infixExpression[i++];  // 等价于先赋值, 后将pmove++==>*pmove = infixExpression[i++]; pmove++;
            }
            // STEP2:添加空格
            *pmove++ = ' ';
            i++;  // 跳过(读取)空格
        } else {
            switch (infixExpression[i]) {
                case '(':  // case2:是(括号
                    stack[++head] = infixExpression[i];
                    break;
                case ')':  // case3:是)括号
                    while (stack[head] != '(') {
                        *pmove++ = stack[head--];
                        *pmove++ = ' ';  // 补空格
                    }
                    head--;  // 弹出'(',但不写入"后缀表达式"
                    break;
                default:  // case4:如果是操作符
                    // 请大哥出来(如果有); 否则就不会执行while,相当于自己直接进去
                    while (head != -1 && isOperator(stack[head]) >= isOperator(infixExpression[i])) {
                        *pmove++ = stack[head--];  // 读操作符
                        *pmove++ = ' ';            // 补空格
                    }
                    // 自己再进去
                    stack[++head] = infixExpression[i];
            }
            i += 2;  // 略过当前操作符及其后面的空格
        }
    }

    // 剩余的依次弹出,并写入
    while (head != -1) {
        *pmove++ = stack[head--];
        *pmove++ = ' ';  // 补空格
    }

    *pmove = '\0';  // 手动补一个\0

    return postfixExpression;
}

void testConversion(char *infixExpression, char *expectedPostfix) {
    char *postfixExpression = convertInfix2Postfix(infixExpression);
    printf("中缀表达式: %s\n", infixExpression);
    printf("转换后的后缀表达式: %s\n", postfixExpression);
    printf("期望的后缀表达式: %s\n", expectedPostfix);

    if (strcmp(postfixExpression, expectedPostfix) == 0) {
        printf("测试通过 ✓\n\n");
    } else {
        printf("测试失败 ✗\n\n");
    }

    // free(postfixExpression);  // 假设你的函数使用了动态内存分配
}

int main() {
    // 测试用例
    testConversion("3 + 4", "3 4 + ");
    testConversion("3 + 4 - 2", "3 4 + 2 - ");
    testConversion("3 + 4 * 2", "3 4 2 * + ");
    testConversion("( 3 + 4 ) * 2", "3 4 + 2 * ");
    testConversion("( ( 3 + 4 ) * 2 )", "3 4 + 2 * ");
    testConversion("9 + ( 3 - 1 ) * 3 + 10 / 2", "9 3 1 - 3 * + 10 2 / + ");
    testConversion("5", "5 ");
    testConversion("12 + 34", "12 34 + ");
    testConversion("1 + 2 * 3 / 4 - 5", "1 2 3 * 4 / + 5 - ");
    testConversion("1 - 2 - 3", "1 2 - 3 - ");
    testConversion("", "");

    return 0;
}

这个版本方便理解

// 1.中缀表达式=>后缀表达式 (原始)
char *convertInfix2Postfix(char *infixExpression) {
    char *postfixExpression = (char *)malloc(sizeof(char) * N);
    char *pmove = postfixExpression;

    int i = 0;
    while (i < strlen(infixExpression)) {
        // case1:如果是数字,直接写入"后缀表达式"
        if (isdigit(infixExpression[i])) {
            // STEP1:读取完整数字
            while (isdigit(infixExpression[i])) {
                *pmove++ = infixExpression[i++];  // 等价于先赋值, 后将pmove++==>*pmove = infixExpression[i++]; pmove++;
            }
            // STEP2:添加空格
            *pmove++ = ' ';
            i++;  // 跳过(读取)空格
        }
        // case2:如果是操作符
        else if (isOperator(infixExpression[i]) != -1) {
            if (head == -1)
                stack[++head] = infixExpression[i];
            else {
                // 把小弟"踩在"下面
                if (isOperator(stack[head]) < isOperator(infixExpression[i])) {
                    stack[++head] = infixExpression[i];
                }
                // 请大哥出来后,自己再进去
                else {
                    // 请大哥出来
                    while (head != -1 && isOperator(stack[head]) >= isOperator(infixExpression[i])) {
                        *pmove++ = stack[head--];  // 读操作符
                        *pmove++ = ' ';            // 补空格
                    }
                    // 自己再进去
                    stack[++head] = infixExpression[i];
                }
            }
            i += 2;  // 略过当前操作符及其后面的空格
        }
        // case3:是(括号
        else if (infixExpression[i] == '(') {
            stack[++head] = infixExpression[i];
            i += 2;
        }
        // case4:是)括号
        else if (infixExpression[i] == ')') {
            while (stack[head] != '(') {
                *pmove++ = stack[head--];
                *pmove++ = ' ';  // 补空格
            }
            head--;  // 弹出'(',但不写入"后缀表达式"
            i += 2;
        }
    }
    while (head != -1) {
        *pmove++ = stack[head--];
        *pmove++ = ' ';  // 补空格
    }

    *pmove = '\0';  // 手动补一个\0

    return postfixExpression;
}

力扣: 基础计算器

// 1. 计算算术表达式
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 300010
char stack[N];      // 中=>后的栈
int calcuStack[N];  // 计算"后缀表达式"的栈
int head = -1;
// https://www.luogu.com.cn/problem/P1175
// https://leetcode.com/problems/basic-calculator/solutions/1457045/c-explained-stacks-beginner-friendly-easy-to-understand/  [√]
// 获取"操作符"优先级; 如果不是字符返回-1
int isOperator(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;  // 1级操作符
        case '*':
        case '/':
            return 2;  // 2级操作符
        default:
            return -1;  // 不是操作符
    }
}

char *preProcessing(char *infixExpression) {
    // 1-(    -2) ===>  1-(     0-2)
    char *newExpression = (char *)malloc(sizeof(char) * N);
    int flag =1;  // flag=1 表示前一个为 +-()' '
    int j = 0;
    for (int i = 0; i < strlen(infixExpression); i++, j++) {
        if (infixExpression[i] == ' ') {  // 顺便把空格去了
            j--;
            continue;
        }
        if (infixExpression[i] == '-' && flag)
            newExpression[j++] = '0';
        newExpression[j] = infixExpression[i];
        flag = (infixExpression[i] == '-' || infixExpression[i] == '+' || infixExpression[i] == '(');
    }
    printf("%s\n", newExpression);
    newExpression[j] = '\0';
    return newExpression;
}

// 1.中缀表达式=>后缀表达式 (抽象版)
char *convertInfix2Postfix(char *infixExpression) {
    infixExpression = preProcessing(infixExpression);
    head = -1;
    char *postfixExpression = (char *)malloc(sizeof(char) * N);
    char *pmove = postfixExpression;

    int i = 0;
    while (i < strlen(infixExpression)) {
        if (infixExpression[i] == ' ') {
            i++;
            continue;
        }
        // case1:如果是数字,直接写入"后缀表达式"
        if (isdigit(infixExpression[i])) {
            // STEP1:读取完整数字
            while (isdigit(infixExpression[i])) {
                *pmove++ = infixExpression[i++];  // 等价于先赋值, 后将pmove++==>*pmove = infixExpression[i++]; pmove++;
            }
            // STEP2:添加空格
            *pmove++ = ' ';
        } else {
            switch (infixExpression[i]) {
                case '(':  // case2:是(括号
                    stack[++head] = infixExpression[i];
                    break;
                case ')':  // case3:是)括号
                    while (stack[head] != '(') {
                        *pmove++ = stack[head--];
                        *pmove++ = ' ';  // 补空格
                    }
                    head--;  // 弹出'(',但不写入"后缀表达式"
                    break;
                default:  // case4:如果是操作符
                    // 请大哥出来(如果有); 否则就不会执行while,相当于自己直接进去
                    while (head != -1 && isOperator(stack[head]) >= isOperator(infixExpression[i])) {
                        *pmove++ = stack[head--];  // 读操作符
                        *pmove++ = ' ';            // 补空格
                    }
                    // 自己再进去
                    stack[++head] = infixExpression[i];
            }
            i++;
        }
    }

    // 剩余的依次弹出,并写入
    while (head != -1) {
        *pmove++ = stack[head--];
        *pmove++ = ' ';  // 补空格
    }

    *pmove = '\0';  // 手动补一个\0

    return postfixExpression;
}

// 计算指定"操作符"计算后的结果
int myCalculate(int a, int b, char op) {
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        default:
            return 0;
    }
}
// 2.计算后缀表达式 (9 3 1 - 3 * + 10 2 / +)
int executePostfixExp(char *postfixExpress) {
    head = -1;  // 清空栈
    int i = 0;
    while (i < strlen(postfixExpress)) {
        // case1:如果是数字
        if (isdigit(postfixExpress[i])) {
            char temp[100] = "";
            while (isdigit(postfixExpress[i])) {
                char partNum[2];
                partNum[0] = postfixExpress[i++];
                partNum[1] = '\0';  // 这样转为字符串
                strcat(temp, partNum);
            }
            calcuStack[++head] = atoi(temp);
            i++;  // 跳过空格
        } else {
            int b = calcuStack[head--];  // 注意次序(是反的)
            int a = calcuStack[head--];
            char op = postfixExpress[i];
            calcuStack[++head] = myCalculate(a, b, op);
            i += 2;  // 跳过"操作符"和"空格"
        }
    }
    return calcuStack[head--];
}

int calculate(char *s) {
    char *postfixExpression = convertInfix2Postfix(s);
    // printf("%s\n", postfixExpression);
    int ans = executePostfixExp(postfixExpression);
    return ans;
}

int main() {
    char infixExpression[N];           //  2-1 + 2
    scanf("%[^\n]", infixExpression);  // TODO %[^\n] 是 C 语言 scanf 的扫描集（scanset）用法
    getchar();                         // 吸收输入缓冲区的换行符
    char *postfixExpression = convertInfix2Postfix(infixExpression);
    printf("%s\n", postfixExpression);
    int ans = executePostfixExp(postfixExpression);
    printf("%d", ans);
    return 0;
}

3.2.2 中缀表达式和前缀表达式

这个考的少(没考过)

转化: ①翻转中缀表达式, 注意如果’(‘要变为’)’, 反之亦然; ②然后像处理中转后的方式一样, 处理翻转后的前缀表达式

计算: ①处理和计算后缀一样 ②只是从i=strelen(perfixExpression)-1开始遍历(从前缀表达式的字符串末尾开始计算)

其他: 两个都可以用来对表达式求值, 推荐后缀表达式的求值方式

居然能找到这来, 真是厉害~

第一章自测&关键词回顾

第二章手撕

第一节链表实现栈

第二节数组实现栈

第三章相关应用

第一节括号匹配问题

第二节表达式求值

3.2.1 中缀表达式和后缀表达式

3.2.2 中缀表达式和前缀表达式

第四章上手真题

第五章比赛怎么用

居然能找到这来, 真是厉害~

7.栈

第一章 自测&关键词回顾

第二章 手撕

第一节 链表实现栈

第二节 数组实现栈

第三章 相关应用

第一节 括号匹配问题

第二节 表达式求值

3.2.1 中缀表达式和后缀表达式

3.2.2 中缀表达式和前缀表达式

第四章 上手真题

第五章 比赛怎么用

第一章自测&关键词回顾

第二章手撕

第一节链表实现栈

第二节数组实现栈

第三章相关应用

第一节括号匹配问题

第二节表达式求值

第四章上手真题

第五章比赛怎么用