devbox
码创造者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【学习笔记】数据结构（三）

作者：码创造者 | 2024-06-30 00:38:40

赞

踩

【学习笔记】数据结构（三）

栈和队列

文章目录

3.1 栈 - Stack

3.1.1 抽象数据类型栈的定义

栈(stack)是限定仅在表尾进行插人或删除操作的线性表。栈又称为后进先出(last in first out)的线性表(简称 LIFO 结构)。

表尾端称为栈顶(top)，表头端称为栈底(bottom)。

不含元素的空表称为空栈。

在这里插入图片描述

栈的抽象数据类型的定义：

在这里插入图片描述

3.1.2 栈的表示和实现

顺序栈 , 即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。通常的top=0表示空栈。

由于栈在使用过程中所需最大空间的大小很难估计，因此,一般来说,在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是:先为栈分配一个基本容量,然后在应用过程中,当栈的空间不够使用时再逐段扩大。为此,可设定两个常量：STACK_INIT_SIZE(存储空间初始分配量)和STACKINCREMENT(存储空间分配增量)。

typedef struct {
	SElemType * base;
	SElemType * top;
	int stacksize; //指示栈的当前可使用的最大容量
}SqStack;

  • 1
  • 2
  • 3
  • 4
  • 5

栈的初始化操作为：

  • 按设定的初始分配量进行第一次存储分配；

  • 称base为栈底指针, 在顺序栈中,它始终指向栈底的位置, 若base的值为 NULL, 则表明栈结构不存在。

  • 称top为栈顶指针,其初值指向栈底,即top=base可作为栈空的标记，每当插人新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。

在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量

#define OK 1 //完成
#define OVERFLOW -1 //失败
#define ERROR -2 //错误

typedef int Status;
typedef struct {
	int* base; // 在栈构造之前和销毁之后，base的值为NULL
	int* top; // 栈顶指针
	int stacksize; //指示栈的当前可使用的最大容量
}SqStack;

Status InitStack(SqStack* S) {
	// 构造一个空栈S
	S->base = (int*) malloc(STACK_INIT_SIZE * sizeof(int));
	if (!S->base) exit(OVERFLOW);
	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;
	return OK;
}

Status Push(SqStack* S, int e) {
	// 插入元素 e为新的栈顶元素
	if (S->top - S->base >= S->stacksize) { //栈满，追加存储空间
		S->base = (int*)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(int));
		if (!S->base) exit(OVERFLOW);
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}
	*S->top++ = e;
	return OK;
}

Status Pop(SqStack* S, int* e) {
	// 若栈不空,则删除s的栈顶元素,用e返回其值,并返回OK;否则返回 ERROR
	if (S->top == S->base) return ERROR;
	*e = *--S->top;
	return OK;
}

Status GetTop(SqStack S, int* e) {
	// 若栈不空, 则用e返回s的栈顶元素, 并返回0K; 否则返回ERROR
	if (S.top == S.base) return ERROR;
	*e = *(S.top - 1);
	return OK;
}

Status DestroyStack(SqStack* S) {
	// 销毁栈S
	free(S->base);
	S->base = NULL;
	S->top = NULL;
	S->stacksize = 0;
	return OK;
}

int main() {
	SqStack S;
	if (InitStack(&S) != OK) {
		printf("Stack initialization failed.\n");
		return OVERFLOW;
	}
	int e; // 使用一个整数变量而不是指针
	Push(&S, 1);
	Push(&S, 2);
	Push(&S, 3);
	Push(&S, 4);
	Status status = Pop(&S, &e);
	if (status == OK) {
		// 删除的元素
		printf("Popped element: %d\n", e);
	}
	else {
		printf("Error: Stack is empty.\n");
	}
	if (GetTop(S, &e) == OK) {
		// 此时栈顶的元素
		printf("Top element: %d\n", e);
	}
	DestroyStack(&S);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88

使用数组实现一个栈

#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 101
int A[MAX_SIZE];
int top = -1;

void Push(int x)
{
	if (top == MAX_SIZE - 1)
	{
		printf("Error:stack overflow\n"); 
		return;
	}
	A[++top] = x;
}

void Pop() {
	if (top == -1) {
		printf("Error: No element to pop\n");
		return;
	}
	top--;
}

int Top()
{
	if (top != -1)
	{
		return A[top];
	}	
}

void Print()
{
	int i;
	printf("Stack: ");
	for (i = 0; i <= top; i++) {
		printf("%d ", A[i]);
	}
	printf("\n");
}

int main() {
	Push(2); Print(); 
	Push(5); Print(); 
	Push(10); Print(); 
	Pop(); Print(); 
	Push(12); Print();
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

使用链表实现一个栈

#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
typedef struct Node {
	int data;
	struct Node* link;
}Node;
struct Node* top;

void Push(int x) {
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->data = x;
	temp->link = top;
	top = temp;
}

void Pop() {
	Node* temp;
	if (top == NULL) return;
	temp = top;
	top = top->link;
	free(temp);
}

int Top() {
	return top->data;
}

bool IsEmpty() {
	if (top == NULL) {
		return true;
	}
	return false;
}

void Print() {
	Node* temp = top;
	printf("List: ");
	while (temp != NULL) {
		printf("%d ", temp->data);
		temp = temp->link;
	}
	printf("\n");
}

int main() {
	top = NULL;
	printf("%d \n", IsEmpty());
	Push(2);
	Push(4);
	Push(1);
	Print();
	Pop();
	Print();
	printf("%d \n", Top());
	printf("%d \n", IsEmpty());
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

3.2 栈的应用举例

3.2.1 数制转换

十进制数N和其他d进制数的转换
N = ( N  div  d ) × d + N   m o d   d  (其中：div为整除运算，mod为求余运算) N = (N \text{ div } d) \times d + N \bmod d \text{ (其中：div为整除运算，mod为求余运算)} N=(N div d)×d+Nmodd (其中：div为整除运算，mod为求余运算)
在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量

#define OK 1 //完成
#define OVERFLOW -1 //失败
#define ERROR -2 //错误

typedef int Status;
typedef struct {
	int* base; // 在栈构造之前和销毁之后，base的值为NULL
	int* top; // 栈顶指针
	int stacksize; //指示栈的当前可使用的最大容量
}SqStack;

Status InitStack(SqStack* S) {
	// 构造一个空栈S
	S->base = (int*) malloc(STACK_INIT_SIZE * sizeof(int));
	if (!S->base) exit(OVERFLOW);
	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;
	return OK;
}

Status StackEmpty(SqStack S) {
	return (S.top == S.base) ? OK : ERROR;
}

Status Push(SqStack* S, int e) {
	// 插入元素 e为新的栈顶元素
	if (S->top - S->base >= S->stacksize) { //栈满，追加存储空间
		S->base = (int*)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(int));
		if (!S->base) exit(OVERFLOW);
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}
	*S->top++ = e;
	return OK;
}

Status Pop(SqStack* S, int* e) {
	// 若栈不空,则删除s的栈顶元素,用e返回其值,并返回OK;否则返回 ERROR
	if (S->top == S->base) return ERROR;
	*e = *--S->top;
	return OK;
}

Status GetTop(SqStack S, int* e) {
	// 若栈不空, 则用e返回s的栈顶元素, 并返回0K; 否则返回ERROR
	if (S.top == S.base) return ERROR;
	*e = *(S.top - 1);
	return OK;
}

Status DestroyStack(SqStack* S) {
	// 销毁栈S
	free(S->base);
	S->base = NULL;
	S->top = NULL;
	S->stacksize = 0;
	return OK;
}

void conversion() {
	SqStack S;
	if (InitStack(&S) != OK) {
		printf("Stack initialization failed.\n");
	}
	int e, N;
	printf("请输入一个十进制数：");
	int num = scanf("%d", &N);
	if (num == 1) {
		while (N) {
			Push(&S, N % 8);
			N = N / 8;
		}
		while (StackEmpty(S) != OK) {
			Pop(&S, &e);
			printf("%d", e);
		}
		DestroyStack(&S);
	}
	
}

int main() {
	conversion();
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92

3.2.2 括号匹配的检验

算法的设计思想:

  1. 凡出现左括弧，则进栈;

  2. 凡出现右括弧，首先检查栈是否空；

  • 若栈空，则表明“右括弧”多了
  • 否则和栈顶元素比较
    • 若相匹配，则“左括弧出栈”
    • 否则不匹配
  1. 表达式检验结束时

  • 若栈空， 则匹配正确

  • 否则表明“左括弧”多了

#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>

#define OVERFLOW -1

#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量

typedef struct {
    char* base;
    char* top;
    int stackSize;
} Stack;

void InitStack(Stack* s) {
    s->base = (char*)malloc(100 * sizeof(char));
    if (!s->base) exit(1); // 分配内存失败
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}

void Push(Stack* s, char elem) {
    if (s->top - s->base >= s->stackSize) { // 栈满，需要扩容
        s->base = (char*)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(char));
        if (!s->base) exit(OVERFLOW); // 扩容失败
        s->top = s->base + s->stackSize;
        s->stackSize += STACKINCREMENT;
    }
    *(s->top++) = elem;
}

char Pop(Stack* s) {
    if (s->top == s->base) return '\0'; // 栈空
    return *(--s->top);
}

int StackEmpty(Stack s) {
    return s.top == s.base;
}

void DestroyStack(Stack* s) {
    free(s->base);
    s->base = NULL;
    s->top = NULL;
    s->stackSize = 0;
}

int CheckBrackets(const char* str) {
    Stack s;
    InitStack(&s);
    char c, topChar;

    while (*str) {
        switch (*str) {
        case '(':
        case '[':
        case '{':
            Push(&s, *str);
            break;
        case ')':
        case ']':
        case '}':
            if (StackEmpty(s)) {
                DestroyStack(&s);
                return 0; // 没有匹配的左括号
            }
            topChar = Pop(&s);
            if ((topChar == '(' && *str != ')') ||
                (topChar == '[' && *str != ']') ||
                (topChar == '{' && *str != '}')) {
                DestroyStack(&s);
                return 0; // 括号不匹配
            }
            break;
        }
        str++;
    }

    int isEmpty = StackEmpty(s);
    DestroyStack(&s);
    return isEmpty; // 如果栈为空，所有括号正确匹配
}

int main() {
    char expression[100];
    printf("Enter an expression: ");
    scanf("%99s", expression);

    if (CheckBrackets(expression)) {
        printf("The brackets are correctly matched.\n");
    }
    else {
        printf("The brackets are not matched.\n");
    }

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98

3.2.3 迷宫求解

迷宫路径算法的基本思想是:

  • 若当前位置“可通”，则纳入路径继续前进
  • 若当前位置“不可通”，则后退,换向探索
  • 若四周均“不可通”，则从路径中删除
#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100  // 堆栈最大容量
#define MAZE_SIZE 5  // 迷宫大小

#define OK 1 //完成
#define OVERFLOW -1 //失败
#define ERROR -2 //错误

typedef struct {
    int x;
    int y;
} PosType;

typedef struct {
    int ord;  // 通道块在路径上的序号
    PosType seat; // 通道块在迷宫中的坐标位置
    int di; // 从此通道块走向下一通道块的方向
} SElemType; // 栈的元素类型

typedef struct {
    SElemType* base;
    SElemType* top;
    int stacksize;
} Stack;

typedef int Status;
typedef int MazeType[MAZE_SIZE][MAZE_SIZE];


void InitStack(Stack* S) {
    S->base = (SElemType*)malloc(MAXSIZE * sizeof(SElemType));
    if (!S->base) exit(ERROR);
    S->top = S->base;
    S->stacksize = MAXSIZE;
}

Status Push(Stack* S, SElemType e) {
    if (S->top - S->base >= S->stacksize) {
        S->base = (SElemType*)realloc(S->base, (S->stacksize + 10) * sizeof(SElemType));
        if (!S->base) exit(ERROR);
        S->top = S->base + S->stacksize;
        S->stacksize += 10;
    }
    *S->top++ = e;
    return OK;
}


Status Pop(Stack* S, SElemType* e) {
    if (S->top == S->base) return ERROR;
    *e = *--S->top;
    return OK;
}

Status StackEmpty(Stack s) {
    return s.top == s.base;
}

// 检查当前位置是否可以通过
Status Pass(MazeType maze, PosType curpos) {
    // 检查坐标是否在迷宫范围内
    if (curpos.x < 0 || curpos.x >= MAZE_SIZE || curpos.y < 0 || curpos.y >= MAZE_SIZE) {
        return ERROR;  // 超出边界，不可通过
    }
    return maze[curpos.x][curpos.y] == 0;  // 返回1如果是通道，0如果是墙或已访问
}

// 留下足迹，标记位置已访问
Status FootPrint(MazeType maze, PosType curpos) {
    // 检查坐标是否在迷宫范围内
    if (curpos.x >= 0 && curpos.x < MAZE_SIZE && curpos.y >= 0 && curpos.y < MAZE_SIZE) {
        maze[curpos.x][curpos.y] = -1;  // 使用-1标记已访问
    }
}

// 标记位置为死胡同
void MarkPrint(MazeType maze, PosType pos) {
    // 检查坐标是否在迷宫范围内
    if (pos.x >= 0 && pos.x < MAZE_SIZE && pos.y >= 0 && pos.y < MAZE_SIZE) {
        maze[pos.x][pos.y] = 2;  // 使用2标记为死胡同
    }
}

PosType NextPos(PosType pos, int di) {
    PosType next = pos;
    switch (di) {
    case 1: next.y++; break;  // 向东
    case 2: next.x++; break;  // 向南
    case 3: next.y--; break;  // 向西
    case 4: next.x--; break;  // 向北
    }
    return next;
}

Status MazePath(MazeType maze, PosType start, PosType end) {
    // 若迷宫 maze 中存在从入口 start 到出口 end 的通道，则求得一条存放在栈中（从栈底到栈顶），并返回 TRUE; 否则返回 FALSE
    Stack s;
    InitStack(&s);
    PosType curpos = start; // 设定“当前位置”为“入口位置”
    int curstep = 1; // 探索第一步
    SElemType pop_elem;
    do {
        if (Pass(maze, curpos) == 1) { // 当前位置可以通过，即是未曾走到过的通道块
            FootPrint(maze, curpos); // 留下足迹
            SElemType e = { curstep, curpos, 1 };
            Push(&s, e); //  加入路径
            if (curpos.x == end.x && curpos.y == end.y) //  到达终点（出口）
                return OK;
            curpos = NextPos(curpos, 1);// 下一位置是当前位置的东邻
            curstep++;// 探索下一步
        }
        else { // 当前位置不能通过
            if (!StackEmpty(s)) {
                Pop(&s, &pop_elem);
                while (pop_elem.di == 4 && !StackEmpty(s)) {
                    MarkPrint(maze, pop_elem.seat); // 留下不能通过的标记，并退回一步
                    Pop(&s, &pop_elem);
                }
                if (pop_elem.di < 4) {
                    pop_elem.di++;
                    Push(&s, pop_elem); // 换下一个方向探索
                    curpos = NextPos(pop_elem.seat, pop_elem.di); // 设定当前位置是该新方向上的相邻块
                }
            }
        }
    } while (!StackEmpty(s));
}

int main() {
    MazeType maze = {
        {0, 1, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 0, 1, 0}
    };
    PosType start = { 0, 0 };
    PosType end = { 4, 4 };
    MazePath(maze, start, end);
    printf("\nAfter MarkPrint:\n");
    for (int i = 0; i < MAZE_SIZE; i++) {
        for (int j = 0; j < MAZE_SIZE; j++) {
            if (maze[i][j] == -1) {
                printf("(%d,%d) ", i, j);
            }
        }
        printf("\n");
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153

3.2.4 表达式求值 - 波兰、逆波兰

//10以内计算
#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>

#define OK 1 // 完成
#define OVERFLOW -1 // 失败
#define ERROR -2 // 错误
#define INF 1e9 // 不合法

#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量

typedef char SElemType;
typedef int Status;
typedef struct {
    SElemType* base;
    SElemType* top;
    int stackSize;
}Stack;

Status InitStack(Stack* S) {
    // 构造一个空栈S
    S->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!S->base) exit(OVERFLOW);
    S->top = S->base;
    S->stackSize = STACK_INIT_SIZE;
    return OK;
}

Status Push(Stack* S, char e) {
    // 插入元素 e为新的栈顶元素
    if (S->top - S->base >= S->stackSize) { //栈满，追加存储空间
        S->base = (SElemType*)realloc(S->base, (S->stackSize + STACKINCREMENT) * sizeof(SElemType));
        if (!S->base) exit(OVERFLOW);
        S->top = S->base + S->stackSize;
        S->stackSize += STACKINCREMENT;
    }
    *S->top++ = e;
    return OK;
}

Status Pop(Stack* S, char* e) {
    // 若栈不空,则删除s的栈顶元素,用e返回其值,并返回OK;否则返回 ERROR
    if (S->top == S->base) return ERROR;
    *e = *--S->top;
    return OK;
}

Status DestroyStack(Stack* S) {
    // 销毁栈S
    free(S->base);
    S->base = NULL;
    S->top = NULL;
    S->stackSize = 0;
    return OK;
}

char GetTop(Stack S) {
    if (S.top == S.base) return ERROR;
    SElemType e = *(S.top - 1);
    return e;
}

int In(char c, const char* OP) {
    // 使用 strchr 函数检查 c 是否在 OP 字符串中
    return strchr(OP, c) != NULL;
}

char Precede(char a, char b)
{
    char x[10] = { '+','-','*','/','(',')','#' };
    char OP[10][10] = { {'>','>','<','<','<','>','>'},
                        {'>','>','<','<','<','>','>'},
                        {'>','>','>','>','<','>','>'},
                        {'>','>','>','>','<','>','>'},
                        {'<','<','<','<','<','=',' '},
                        {'>','>','>','>',' ','>','>'},
                        {'<','<','<','<','<',' ','='} };
    for (int i = 0; i < 7; i++)
    {
        if (a == x[i]) 
        {
            a = i;
        }
        if (b == x[i]) 
        {
            b = i;
        }
    }
    return OP[a][b];
}


char Operate(char p, char theta, char q)
{
    if (theta == '+')return p + q;
    else if (theta == '-')return q - p;
    else if (theta == '*')return p * q;
    else if (theta == '/')
    {
        if (p == 0)
        {
            printf("输入不合法！");
            return INF;
        }
        return q / p;
    }
    else return INF;
}

char EvaluateExpression() {
    // 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，
    // OP 为运算符集合。
    const char* OP = "+-*/()#";
    char x;
    char theta, p, q;
    Stack OPTR, OPND;
    InitStack(&OPTR);
    Push(&OPTR, '#');
    InitStack(&OPND);
    char c = getchar();
    while (c != '#' || GetTop(OPTR) != '#') {
        printf("OPTR:"); for (int i = 0; i < OPTR.top - OPTR.base; i++)printf("%c ", OPTR.base[i]); puts("");
        printf("OPND:"); for (int i = 0; i < OPND.top - OPND.base; i++)printf("%d ", OPND.base[i]); puts("\n");

        if (!In(c, OP)) {  // 不是运算符则进栈OPND
            Push(&OPND, c - '0');
            c = getchar();
        } 
        else {
            switch (Precede(GetTop(OPTR), c))
            {
            case'<': // 栈顶元素优先权低
                Push(&OPTR, c);
                c = getchar();
                break;
            case'=': // 脱括号并接收下一字符
                Pop(&OPTR, &x);
                c = getchar();
                break;
            case'>': // 退栈并将运算结果入栈
                Pop(&OPTR, &theta);
                Pop(&OPND, &p);
                Pop(&OPND, &q);
                Push(&OPND, Operate(p, theta, q));
                break;
            default:
                break;
            }
        }
    }
    char res = GetTop(OPND);
    DestroyStack(&OPTR);
    DestroyStack(&OPND);
    return res;
}

int main() {
    printf("请输入一串表达式，以等号“#”结尾：");
    printf("最终结果为：%d", EvaluateExpression());
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163

⭐️ 中缀、前缀、后缀

Order of operation:

  1. Parentheses (){} []

  2. Exponents (right to lett ) ^

  3. Multiplication and division (left to right)

  4. Addition and Subtraction (left to right)

中缀表达式 Infix : 运算符在运算数的中间

  • ​ <operand><operator><operand>
  • ​ 缺点：关系符号优先级和结合，所以对计算机来说却不好操作，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式)

前缀表达式 - 波兰表达式 Prefix

  • ​ <operator><operand><operand>

  • ​ 中缀表达式：(a + b) * c - d 转换为 前缀表达式（波兰表达式）：- * + a b c d

  • ​ 特点：一个操作数只能和一个操作符进行结合, 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式

  • ​ 前缀表达式的计算机求值:

    • 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

    • 例如：(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:

      • 从右至左扫描，将6、5、4、3压入堆栈
      • 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
      • 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
      • 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

后缀表达式 - 逆波兰表达式 Postfix

  • ​ <operand><operand><operator>
  • ​ 中缀表达式 ：(a + b) * c - d 转换为 后缀表达式（逆波兰表达式）：a b + c * d -
  • ​ 特点： 运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现 且紧靠它的两个操作数构成一个最小表达式
  • ​ 后缀表达式的计算机求值：
    • 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
    • 例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
      • 从左至右扫描，将3和4压入堆栈；
      • 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
      • 将5入栈；
      • 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
      • 将6入栈；
      • 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/码创造者/article/detail/770850
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。