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

2024-01-07 23:35:47

目录

一、实验目的

二、实验原理

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_numstack_op 分别存储操作数和操作符。
    • 遇到数字直接加入后缀表达式 exp_postfix 中。
    • 遇到左括号 '(' 直接入栈。
    • 遇到右括号 ')' 弹出操作符栈中的元素,直到遇到左括号 '(',并将这对括号之间的所有操作符加入后缀表达式。
    • 遇到运算符,根据优先级判断是否弹出栈中的运算符,直到满足条件为止。
    • 最终将剩余的操作符出栈。
  4. 后缀表达式计算:

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

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

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

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

文章来源:https://blog.csdn.net/weixin_58628068/article/details/135442786
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。