C语言：栈（含括号匹配）仅供初学者

根据提供的文件信息，本文将对C语言中的栈及其在括号匹配问题中的应用进行详细的解析。此内容适合初学者理解栈的基本概念、实现方法及如何使用栈解决实际问题。 ### C语言栈的基本概念 栈是一种特殊的线性表，只允许在一端进行插入或删除操作，该端称为栈顶。与之相对的另一端称为栈底。当栈为空时，栈顶和栈底是指向同一位置的。栈遵循后进先出（Last In First Out, LIFO）的原则。 ### 栈的结构定义 在代码中，作者定义了一个名为`SqStack`的数据结构来表示顺序栈： ```c typedef char SElemType; typedef struct { SElemType* base; SElemType* top; int stacksize; } SqStack; ``` - `SElemType`: 栈元素类型，在这里被定义为`char`。 - `base`: 指向栈底的指针。 - `top`: 指向栈顶的指针。 - `stacksize`: 栈当前的大小。 ### 栈的操作实现 #### 初始化栈 `InitStack` 函数`InitStack`用于初始化一个空栈。首先分配足够大小的空间用于存放栈元素，并设置栈顶指针和栈的当前大小： ```c Status InitStack(SqStack& s) { s.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if (s.base == NULL) exit(OVERFLOW); s.top = s.base; s.stacksize = STACK_INIT_SIZE; return OK; } ``` - `STACK_INIT_SIZE`: 定义了初始栈空间大小。 #### 销毁栈 `DestoryStack` 销毁栈即释放栈所占用的内存： ```c Status DestoryStack(SqStack& s) { if (s.base) free(s.base); s.top = s.base = NULL; s.stacksize = 0; return OK; } ``` #### 清空栈 `ClearStack` 清空栈即将栈顶指针重置到栈底的位置： ```c Status ClearStack(SqStack& s) { s.top = s.base; return OK; } ``` #### 判断栈是否为空 `StackEmpty` 通过比较栈顶指针和栈底指针是否相同来判断栈是否为空： ```c Status StackEmpty(SqStack s) { if (s.top == s.base) return TRUE; return FLASE; } ``` #### 获取栈的长度 `StackLength` 栈的长度即栈顶指针与栈底指针之间的距离： ```c int StackLength(SqStack s) { return s.top - s.base; } ``` #### 获取栈顶元素 `GetTop` 获取栈顶元素，但不将其弹出： ```c Status GetTop(SqStack s, SElemType& e) { if (s.top == s.base) return ERROR; e = *(s.top - 1); return OK; } ``` #### 入栈 `Push` 将元素压入栈中。如果栈已满，则动态扩展栈的存储空间： ```c Status Push(SqStack& s, SElemType e) { if (s.top - s.base >= s.stacksize) { if (!(s.base = (SElemType*)realloc(s.base, (s.stacksize + STACKINCREMENT) * sizeof(SElemType)))) exit(OVERFLOW); s.top = s.base + s.stacksize; s.stacksize += STACKINCREMENT; } *s.top++ = e; return OK; } ``` #### 出栈 `Pop` 移除栈顶元素并返回其值： ```c Status Pop(SqStack& s /*, SElemType& e */) { if (s.top == s.base) return ERROR; // e = *--s.top; s.top--; return OK; } ``` #### 打印所有栈元素 `PrintALLElem` 遍历栈底到栈顶的所有元素并打印出来： ```c void PrintALLElem(SqStack s) { SElemType* p; for (p = s.base; p < s.top; p++) printf("%d", *p); printf("\n"); } ``` ### 括号匹配问题的应用 接下来是程序的主要部分，用于解决括号匹配问题。程序读取一行包含括号的字符串，利用栈的特性来检查括号是否正确配对： 1. **初始化栈**：调用`InitStack`函数初始化栈。 2. **读取输入**：使用`scanf`读取一串包含括号的字符。 3. **遍历字符串**： - 逐个检查每个字符： - 如果遇到左括号（'(','[','{'），则将其压入栈中。 - 如果遇到右括号（']','}',')'），则检查栈顶是否为对应的左括号，如果是，则出栈；如果不是，则表示括号不匹配。 4. **判断结果**： - 如果栈为空，表示所有的括号都正确配对。 - 如果栈不为空，表示存在未匹配的括号。 通过以上步骤，我们不仅了解了栈的基本操作，还学会了如何利用栈解决实际问题——括号匹配。这对于理解和掌握栈这一数据结构至关重要。