数据结构——栈的应用_数据结构-栈的应用

栈结构固有的“后进先出”特性，使得栈成为程序设计中的有用工具，下文将讨论几个栈应用的典型例子，本文各经典案例的代码实现均采用顺序栈的结构，如有需要，在理解算法思想的基础上，不难将其推导为链栈结构实现，本文不过多赘述。

一、数制转换

十进制数N与其他d进制数的转换是计算机实现计算的基本问题，一个数制转换的简单算法基于以下原理：

N = ( N / d ) *  d + N % d

采用栈结构实现上述数制转换的逻辑表示：

 假设现在要编辑一个程序满足以下要求：对于输入的任意一个非负十进制整数，打印输出其对应的八进制数。由于采用除留余数法的计算过程是从低位到高位的顺序依次产生八进制的各个数位；而打印通常从高位向低位依次打印。因此可想，将计算过程中的得到的各个八进制数位依次进栈，则按照出栈序列依次打印输出的即为与输入对应的八进制数。

算法函数的代码实现：（可直接运行）

//此算法实现采用顺序栈
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
#pragma warning(disable: 4996)
 
#define Stack_Init_Size 10
#define Stack_Add_Size 5
 
typedef int ElemType;
typedef struct Stack
{
	ElemType* data;
	int size;
	int capacity;
}Stack;
 
//栈的初始化
void StackInit(Stack* S)
{
	S->data = (ElemType*)malloc(sizeof(ElemType) * Stack_Init_Size);
	if (NULL == S->data)
	{
		printf("空间申请失败\n");
		exit(0);
	}
	S->size = 0;
	S->capacity = Stack_Init_Size;
}
//检查当前栈是否已满，若满则进行扩容
void CapacityCheck(Stack* S)
{
	assert(S);
	if (S->size >= S->capacity) //当前栈满，需进行扩容
	{
		S->data = (ElemType*)realloc(S->data, sizeof(ElemType) * (S->capacity + Stack_Add_Size));
		if (NULL == S->data)
		{
			printf("空间扩容失败\n");
			exit(0);
		}
		S->capacity += Stack_Add_Size;
	}
}
//入栈
void StackPush(Stack* S, ElemType e)
{
	CapacityCheck(S);
	S->data[S->size++] = e;
 
}
//判断栈是否为空
int StackEmpty(Stack* S)
{
	return S->size == 0;
}
//出栈操作
void StackPop(Stack* S, ElemType* e)
{
	assert(S);
	if (StackEmpty(S))
	{
		printf("当前栈为空\n");
		return;
	}
	*e = S->data[--S->size];
 
}
//数制转换
void conversion(Stack* S)
{
	StackInit(S);
	int num = 0;
	printf("请输入需要进行转换的十进制数:> ");
	scanf("%d", &num);
	while (num)
	{
		StackPush(S, num % 8);
		num /= 8;
	}
	printf("转换为八进制数为:> ");
	while (!StackEmpty(S))
	{
		ElemType e;
		StackPop(S,&e);
		printf("%d",e);
	}
	printf("\n");
}
 
int main()
{
	Stack S;
	conversion(&S);
	return 0;
}

二、括号匹配

假设表达式中允许包含两种括号：圆括号（）和方括号[]，其嵌套的顺序随意，采用栈结构的出栈与入栈的操作实现括号的匹配。

括号匹配算法：在算法中设置一个栈，每读入一个括号，若为右括号，则或者使置于栈最顶端的最迫切期待消除的数据元素得以消解，或者是不合法的情况；若都为左括号，则作为一个最迫切待消除的数据元素压入栈顶，使栈中原有数据元素的待消解的紧迫性都下降一级。最终通过判断栈最终的空栈情况来确定括号是否匹配。

具体代码实现如下：

//括号匹配问题
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
#pragma warning(disable: 4996)
 
#define Stack_Init_Size 10
#define Stack_Add_Size 5
 
//定义栈的结构体
typedef char ElemType;
typedef struct Stack
{
	ElemType* data;
	int size;
	int capacity;
}Stack;
 
//栈的初始化
void StackInit(Stack* S)
{
	S->data = (ElemType*)malloc(sizeof(ElemType) * Stack_Init_Size);
	if (NULL == S->data)
	{
		printf("空间申请失败\n");
		exit(0);
	}
	S->capacity = Stack_Init_Size;
	S->size = 0;
}
//判断栈中是否为空 1-表示为空 0-表示非空
int IsEmpty(Stack* S)
{
	return S->size == 0;
}
 
ElemType GetTop(Stack* S)
{
	assert(S);
	if (IsEmpty(S))
	{
		return;
	}
	return S->data[S->size - 1];
}
//判断栈是否满，若满则扩容
void CapacityCheck(Stack* S)
{
	if (S->size >= S->capacity)
	{
		S->data = (ElemType*)realloc(S->data, sizeof(ElemType) * (S->capacity + Stack_Add_Size));
		if (NULL == S->data)
		{
			printf("空间扩容失败\n");
			exit(0);
		}
		S->capacity += Stack_Add_Size;
	}
}
//入栈
void StackPush(Stack* S, ElemType* e)
{
	assert(S);
	CapacityCheck(S);
	S->data[S->size++] = e;
 
}
//出栈
void StackPop(Stack* S)
{
	assert(S);
	if (!IsEmpty(S))
	{
		S->size--;
		return;
	}
}
//栈销毁
void StackDestory(Stack* S)
{
	assert(S);
	if (S->data != NULL)
	{
		free(S->data);
		S->data = NULL;
	}
	S->capacity = 0;
	S->size = 0;
}
void isValid(Stack* S)
{
	StackInit(S);
	ElemType ch = { 0 };
	printf("请输入括号:> ");
	while ((ch = getchar()) != EOF)
	{
		if(ch != '\n')
		{
			ElemType temp_01 = GetTop(S);
			StackPush(S, ch);
			ElemType temp_02 = GetTop(S);
			if ((temp_01 == '(' && temp_02 == ')') || (temp_01 == '[' && temp_02 == ']'))
			{
				StackPop(S);
				StackPop(S);
			}
		}
		else
		{
			break;
		}
	}
 
	if (IsEmpty(S))
	{
		StackDestory(S);
		printf("括号匹配成功\n");
	}
	else
	{
		StackDestory(S);
		printf("括号匹配失败\n");
	}
}
 
int main()
{
	Stack S;
	isValid(&S);
}

三、行编辑程序

一个简单的行编辑程序的功能：接收用户从终端输入的程序或数据，并存入用户的数据区。

由于用户在终端进行输入时，不能保证不出差错，因此在行编辑程序中，通常采用，设置一个输入缓冲区，用以接收用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出现差错，并在有错误时及时进行更正。

例如：当用户发现刚刚键入的一个字符是错误的时，可以补入一个退格符’#‘，以表示前一个字符无效；如果本行之间键入的差错较多或难以补救，则可以补入一个退行符’@‘，以表示当前行的字符无效。 

注意：Windows环境下，通过键盘输入ctrl+z表示EOF结束终止符！

//行编辑程序
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
#define Stack_Init_Size 10
#define Stack_Add_Size 5
 
//定义栈结构
typedef char ElemType;
typedef struct Stack
{
	ElemType* data;
	int size;
	int capacity;
}Stack;
 
//栈的初始化
void StackInit(Stack* S)
{
	S->data = (ElemType*)malloc(sizeof(ElemType) * Stack_Init_Size);
	if (NULL == S->data)
	{
		printf("空间申请失败\n");
		exit(0);
	}
	S->size = 0;
	S->capacity = Stack_Init_Size;
}
//栈的判空操作
int IsEmpty(Stack* S)
{
	return S->size == 0;
}
//出栈
void StackPop(Stack* S)
{
	assert(S);
	if (IsEmpty(S))
	{
		return;
	}
	S->size--;
}
 
//清空栈栈中内容
void StackClear(Stack* S)
{
	assert(S);
	if (IsEmpty(S))
	{
		return;
	}
	S->size = 0;
}
 
//栈的扩容判断
void CapacityCheck(Stack* S)
{
	if (S->size >= S->capacity)
	{
		S->data = (ElemType*)realloc(S->data, sizeof(ElemType) * (S->capacity + Stack_Add_Size));
		if (NULL == S->data)
		{
			printf("栈空间扩容失败\n");
			exit(0);
		}
		S->capacity += Stack_Add_Size;
	}
}
//入栈
void StackPush(Stack* S, ElemType data)
{
	assert(S);
	CapacityCheck(S);
	S->data[S->size++] = data;
}
//销毁栈
void StackDestory(Stack* S)
{
	assert(S);
	if (NULL != S->data)
	{
		free(S->data);
		S->data = NULL;
	}
	S->capacity = 0;
	S->size = 0;
}
//打印当前栈中的文本文件
void StackPrint(Stack* S)
{
	assert(S);
	if (IsEmpty(S))
	{
		return;
	}
	printf("当前行文本为:> %s\n", S->data);
}
void LineEdit(Stack* S)
{
	StackInit(S);
	ElemType ch = { 0 };
	printf("请输入文本内容:> ");
	ch = getchar();
	while (ch != EOF)
	{
		while (ch != EOF && ch != '\n')
		{
			switch (ch)
			{
			case '#' :
				StackPop(S);
				break;
			case '@':
				StackClear(S);
				break;
			default:
				StackPush(S, ch);
			}
			ch = getchar();
		}
		StackPush(S, '\0');
		StackPrint(S);
		StackClear(S);
		if (ch != EOF)
		{
			printf("请输入文本内容:> ");
			ch = getchar();
		}
	}
	StackDestory(S);
}
 
int main()
{
	Stack S;
	LineEdit(&S);
}

四、表达式求值

表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个的经典例子。本文介绍一种简单直观、广为使用的算法——“算符优先算法”。

要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先应该能正确解释表达式。

例如要对算术表达式求值，首先要了解四则运算的规则。即：

1. 先乘除，后加减
2. 从左到右算
3. 先括号内，后括号外

算符优先算法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。

任何一个表达式都是由操作数、运算符、和界限符组成的，称之为单词。一般的，操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符‘#’等。本文仅就只包含加减乘除四则运算的简单算术表达式的求值问题展开讨论。

为了实现算符优先算法，可以使用两个工作栈。一个叫做OPTR，用以寄存运算符；另一个称之为OPND，用以寄存操作数或运算结果。算法的基本思想如下：

1. 首先置操作数栈为空栈，表达式起始符‘#’为运算符栈的栈底元素；
2. 依次读入表达式中的各个字符，若为操作数即进入OPND栈，若为运算符则和OPTR栈的栈顶运算符比较优先权后做相应的操作，直至整个表达式求值完毕，即OPTR栈的栈顶和当前读入的字符均为‘#’。

表达式求值算法的代码实现如下：

学生党受限于时间原因，本章内容后续几天逐步更新完毕，望见谅！！！