数据结构实验1：栈和队列的应用

目录

一、实验目的

二、实验原理

1.1栈的基本操作

1.1.1 栈的定义

1.1.2?初始化栈

1.1.3?压栈（Push）

1.1.4 出栈（Pop）

1.1.5?判空（isEmpty）

1.1.6??查看栈顶元素（Top）

1.1.7 获取栈的大小（Size）

2.1栈的应用

三、实验内容

中缀表达式的计算?

原理

代码

截图

分析

---

一、实验目的

1、理解并掌握栈和队列的逻辑结构和存储结构;理解栈和队列的相关基本运算;

2、编程对相关算法进行验证;

3、学会利用栈和队列解决实际问题。

二、实验原理

栈（Stack）是一种基本的数据结构，它遵循先进后出（Last In, First Out，LIFO）的原则。这意味着最后进入栈的元素是第一个被移除的，而最先进入栈的元素是最后被移除的。栈常常被用于管理函数调用、表达式求值、内存管理等各种应用场景。

1.1栈的基本操作

1.1.1 栈的定义

#include<iostream>
#define MAX_SIZE 100//最大为100个元素，且为全局变量


typedef struct{
	int data[MAX_SIZE];//这里定义的是int型数组，也可以定义其他类型的数组
	int top;//栈顶，指向末尾元素的起始地址
}Stack;

可以把栈当作一个数组看待，data数组最多储存100个元素，从0~99，top的范围为-1~98

若对结构体定义不清晰，可以参考?https://blog.csdn.net/weixin_58628068/article/details/135318742

1.1.2?初始化栈

void Initialize(Stack *stack) {//参数为指针
	stack->top = -1;//由于栈底指向末尾元素的起始地址，空栈没有元素，则指向-1
}

1.1.3?压栈（Push）

将元素添加到栈的顶部。

void Push(Stack* stack, int elem) {
	if (stack->top >= (MAX_SIZE - 1)) {//若超出栈的表示范围
		cout << "栈满，无法添加元素";
	}
	else {
		stack->data[++stack->top] = elem;
	}
}

top的范围为-1~98，且top是从-1开始的，数组是从0开始的，则应该先自增再赋值。

1.1.4 出栈（Pop）

从栈的顶部移除元素，并返回。

int Pop(Stack* stack) {
	if (stack->top == -1) {//如果栈为空
		cout << "栈为空，无元素";
        return -1；
	}
	else {
		int c=stack->data[stack->top];
        stack->top--;
        return c;
	}
}

数组从0开始，top是从-1开始，则应该+1，得到所需元素后应该指针-1

补充一下++x与x++的区别

一个是先对x加1再使用x的值

一个是先使用x的值再对x加1

--x与x--同理

1.1.5?判空（isEmpty）

?检查栈是否为空。

int IsEmpty(Stack* stack) {
	if (stack->top == -1) {//如果为空，则返回1
		return 1;
	}
	else {//否则返回0
		return 0;
	}
}

1.1.6??查看栈顶元素（Top）

返回栈顶元素，但不改变栈，与Pop操作有区别。

int Top(Stack* stack) {
	if (stack->top == -1) {//如果栈为空
		cout << "栈为空，无元素";
		return -1;
	}
	else {
		return stack->data[stack->top];
	}
}

注意Pop中是--，对top的值进行了改变，并未对top的值进行改变。

1.1.7 获取栈的大小（Size）

int Size(Stack* stack) {
	return stack->top+1;
}

数组从0开始，top是从-1开始，所以应该+1。

2.1栈的应用

栈的应用：

• 函数调用： 函数调用时，局部变量和函数参数被推入栈，函数执行完毕后再从栈中弹出。
• 表达式求值： 中缀表达式转换为后缀表达式，然后通过栈进行求值。
• 内存管理： 操作系统使用栈来管理函数调用和局部变量。
• Undo功能： 许多应用程序使用栈来实现撤销操作。

三、实验内容

中缀表达式的计算?

1、【问题描述】输入一个中缀表达式，将其转换为后缀表达式，然后对后缀表达 式进行求值。运算符包括“+”、“-”、“*”“/”、“(”“) ”、“#”，参加运算的数为小于 10 的自然数。

2、【输入要求】多组数据，每组数据一行，对应一个算术表达式，每个表达式均 以“#”结尾。当表达式只有一个“#”时，输入结束。 1

3、【输出要求】对于每组数据输出 2 行，第一行为中缀表达式对应的后缀式，第 2 行为后缀求值的运算结果。

原理

1. 遍历中缀表达式： 从左到右扫描中缀表达式中的每个字符。

2. 操作数处理： 遇到操作数时，直接输出到后缀表达式。

3. 运算符处理：

   • 如果遇到左括号 '('，将其推入运算符栈。
   • 如果遇到右括号 ')'，则将运算符栈中的运算符弹出并输出到后缀表达式，直到遇到左括号 '('。左括号 '(' 不输出到后缀表达式，而是从栈中弹出。
   • 如果遇到其他运算符，比较其优先级与运算符栈栈顶的运算符优先级：
     • 如果当前运算符的优先级小于或等于栈顶运算符的优先级，将栈顶运算符弹出并输出到后缀表达式，然后将当前运算符推入运算符栈。
     • 如果当前运算符的优先级大于栈顶运算符的优先级，将当前运算符推入运算符栈。

4. 表达式结束处理： 遍历完中缀表达式后，将运算符栈中的所有运算符依次弹出并输出到后缀表达式。

5. 计算后缀表达式： 使用一个栈来计算后缀表达式。

   • 遍历后缀表达式中的每个字符：
     • 如果是操作数，将其推入操作数栈。
     • 如果是运算符，从操作数栈中弹出足够的操作数，执行相应的运算，将结果推入操作数栈。

6. 最终结果： 在计算完成后，操作数栈中的唯一元素即为最终结果。

代码

#include<iostream>
using namespace std;

#define MAX_SIZE 100
char op_list[6] = { '+','-','*','/','(',')' };//操作符

typedef struct Stack {
	char data[MAX_SIZE];
	int top;
};

void Initialize(Stack* stack) {//参数为指针
	stack->top = -1;//由于栈底指向末尾元素的起始地址，空栈没有元素，则指向-1
}

void Push(Stack* stack, char elem) {
	if (stack->top >= (MAX_SIZE - 1)) {//若超出栈的表示范围
		cout << "栈满，无法添加元素";
	}
	else {
		stack->data[++stack->top] = elem;
	}
}

char Pop(Stack* stack) {
	if (stack->top == -1) {//如果栈为空
		cout << "栈为空，无元素";
		return  '#';
	}
	else {
		char c=stack->data[stack->top];
		stack->top--;
		return c;
	}
}
int IsEmpty(Stack* stack) {
	if (stack->top == -1) {//如果为空，则返回1
		return 1;
	}
	else {//否则返回0
		return 0;
	}
}

char Top(Stack* stack) {
	if (stack->top == -1) {//如果栈为空
		cout << "栈为空，无元素"<<endl;
		return '#';
	}
	else {
		return stack->data[stack->top];
	}
}

int Size(Stack stack) {
	return stack.top + 1;
}

int main() {
	int count = 0;//字符串大小
	int index = 0;//后缀表达式的起始值
	char exp_infix[MAX_SIZE] = {'\0'};//字符串中缀表达式
	char exp_postfix[MAX_SIZE] = { '\0' };//字符串后缀表达式
	Stack stack_num, stack_op;//操作数栈和操作符栈
	//初始化栈
	Initialize(&stack_num);
	Initialize(&stack_op);
	for (int i = 0; i < MAX_SIZE; i++) {
		cin >> exp_infix[i];
		if (exp_infix[i]=='#') {//输入结束
			break;
		}
		count++;
	}
	//cout << count << "个数" << endl;
	for(int i=0;i<count;i++){
		if ((exp_infix[i] <= '9') && (exp_infix[i] >= '0'))//如果输入的是数字，直接复制
		{
			exp_postfix[index++] = exp_infix[i];
			//cout << exp_infix[i] << "压入num栈中" << endl;
		}
		else {//如果为操作符
			if (exp_infix[i] == '(') {//如果是 ( ，直接入操作符栈
				//cout << "遇到 (" << endl;
				Push(&stack_op, '(');
			}
			else if (exp_infix[i] == ')') {//如果是 ) ，则从操作符的栈顶到栈底，从栈顶到最近的一个（之间的所有操作符压出；
				//cout << "遇到 )" << endl;
				while (Top(&stack_op) != '(') {
					//cout << "栈顶为" << Top(&stack_op) << endl;
					char c = Pop(&stack_op);
					//cout << "出栈为" << c<<endl;
					exp_postfix[index++] = c;
				}
				Pop(&stack_op);//将 ( 出栈
				
			}
			else {//如果为 + - * /,将优先级大于等于它的压出,直到前面没有元素可以再压出，再入栈
				if ((exp_infix[i] == '*') || (exp_infix[i] == '/')) {//如果为*或者/,则需要压出*或者/
					//cout << "遇到" << exp_infix[i] << endl;
					while ((IsEmpty(&stack_op) == 0) && (Top(&stack_op) != '+') && (Top(&stack_op) != '-') && (Top(&stack_op) != '(')) {//如果栈为空或者遇到了小于等于*和/的元素，则不应该继续压出
						//cout << "出栈" << Top(&stack_op) << endl;
						char c = Pop(&stack_op);
						exp_postfix[index++] = c;
						//cout << "出栈为" << c << endl;
					}
					Push(&stack_op, exp_infix[i]);//入栈
				}
				else {//如果为+或者-，则除了（都应该出栈
					//cout << "遇到" << exp_infix[i] << endl;
					while ((IsEmpty(&stack_op) == 0) && (Top(&stack_op) != '(')) {//如果为空或者遇到了（，则停止出栈
						//cout << "出栈" << Top(&stack_op) << endl;
						char c = Pop(&stack_op);
						//cout << "出栈为" << c << endl;
						exp_postfix[index++] = c;
						
					}
					Push(&stack_op, exp_infix[i]);//入栈
				}
			}
		}
	}
	//判断op栈是否为空，若不为空，则全部出栈
	while (IsEmpty(&stack_op) == 0) {
		//cout << "出栈" << Top(&stack_op) << endl;
		char c = Pop(&stack_op);
		//cout << "出栈为" << c << endl;
		exp_postfix[index++] = c;
	}
	//cout << "index:" << index<< endl;
	for (int i = 0; i < index; i++) {
		cout << exp_postfix[i];
	}
	cout << endl;
	//计算
	//初始化栈
	Initialize(&stack_num);
	Initialize(&stack_op);
	int num = 0;
	for (int i = 0; i < index; i++) {
		if ((exp_postfix[i] <= '9') && (exp_postfix[i] >= '0'))//如果输入的是数字，直接压入操作数栈
		{
			Push(&stack_num, exp_postfix[i]);
		}
		else {//如果是操作符，则依次从操作数栈中依次取出两个数,a2 op a1=a3,a3压入栈中
			int a1 = int(Pop(&stack_num))-48;
			int a2 = int(Pop(&stack_num)) - 48;
			int a3;
			switch (exp_postfix[i]) {
			case'*':a3 = a2 * a1; break;
			case'/':a3 = a2 / a1; break;
			case'+':a3 = a2 + a1; break;
			case'-':a3 = a2 - a1; break;
			}
			if (IsEmpty(&stack_num) == 1) {//如果为空栈
				cout << a3;
			}
			Push(&stack_num, char(a3 + 48));
		}
	}
	return 0;
}

截图

分析

1. 数据结构定义：

   定义了一个结构体 Stack 用于表示栈，包含一个字符数组 data 作为栈的存储空间，以及一个整数 top 表示栈顶的索引。

2. 栈的基本操作：

   • Initialize: 初始化栈。
   • Push: 将元素压入栈中。
   • Pop: 弹出栈顶元素。
   • IsEmpty: 判断栈是否为空。
   • Top: 获取栈顶元素。
   • Size: 获取栈的大小。

3. 中缀表达式转后缀表达式：

   • 遍历输入的中缀表达式字符串 exp_infix。
   • 使用两个栈 stack_num 和 stack_op 分别存储操作数和操作符。
   • 遇到数字直接加入后缀表达式 exp_postfix 中。
   • 遇到左括号 '(' 直接入栈。
   • 遇到右括号 ')' 弹出操作符栈中的元素，直到遇到左括号 '('，并将这对括号之间的所有操作符加入后缀表达式。
   • 遇到运算符，根据优先级判断是否弹出栈中的运算符，直到满足条件为止。
   • 最终将剩余的操作符出栈。

4. 后缀表达式计算：

   • 遍历后缀表达式字符串 exp_postfix。
   • 遇到数字则入操作数栈。
   • 遇到操作符则从操作数栈中弹出两个数进行相应的运算，然后将结果入栈。
   • 最终操作数栈中的唯一元素即为计算结果。

5. 注意点：

   • 对于数字字符的处理，将字符转换为对应的数字，例如 int(a) - 48。
   • 将计算结果重新转换为字符入栈，例如 char(a3 + 48)。

6. 输出：

   • 输出转换后的后缀表达式。
   • 输出计算结果。

对于注释掉的代码，是为了简洁，如果不懂，请别注释掉，这个可以帮住同学们了解更详细的流程。?