数据结构(3.8)——栈的应用

栈在括号匹配中的应用

流程图

代码

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10typedef struct {char data[MaxSize];int top;
} SqStack;// 初始化栈
void InitStack(SqStack* S) {S->top = -1; // 初始化栈顶指针
}// 判空
bool StackEmpty(SqStack* S) {if (S->top == -1) {return true;} else {return false;}
}// 入栈
bool Push(SqStack* S, char x) {if (S->top == MaxSize - 1) { // 栈满,报错return false;} else {S->top = S->top + 1; // 指针先加1S->data[S->top] = x; // 新元素入栈return true;}
}// 出栈
bool Pop(SqStack* S, char* x) {if (StackEmpty(S)) {return false;} else {*x = S->data[S->top]; // 栈顶元素先出栈S->top = S->top - 1; // 指针减1return true;}
}// 括号匹配检查
bool bracketCheck(char str[], int length) {SqStack S;InitStack(&S); // 初始化一个栈for (int i = 0; i < length; i++) {if (str[i] == '(' || str[i] == '[' || str[i] == '{') {Push(&S, str[i]); // 扫描到左括号,入栈} else {if (StackEmpty(&S)) { // 扫描到右括号,且当前栈空return false; // 匹配失败}char topElem;Pop(&S, &topElem); // 栈顶元素出栈if (str[i] == ')' && topElem != '(') {return false;}if (str[i] == ']' && topElem != '[') {return false;}if (str[i] == '}' && topElem != '{') {return false;}}}return StackEmpty(&S); // 检索全部括号后,栈空说明匹配成功
}int main() {char str[] = "{([()])}";int length = sizeof(str) / sizeof(str[0]) - 1; // 计算字符串长度,减1是为了去掉结尾的'\0'if (bracketCheck(str, length)) {printf("括号匹配成功\n");} else {printf("括号匹配失败\n");}return 0;
}

栈在表达式求值中的应用

中缀、后缀、前缀表达式

中缀表达式

运算符在两个操作数中间:

  1. a + b
  2. a + b - c
  3. a + b - c * d

后缀表达式

运算符在两个操作数后面:

  1. ab +
  2. ab + c-或者a bc - +
  3. ab + cd * -

前缀表达式

运算符在两个操作数前面:

  1. + ab
  2. - + ab c
  3. - + ab * cd

中缀表达式转后缀表达式(手算)

  1. 确定中缀表达式中各个运算符的运算顺序
  2. 选择下一个运算符,按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数(若运算顺序不唯一,则后缀表达式也不唯一)
  3. 如果还有运算符没被处理,就继续2步骤

例:

转换成后缀表式:          15 7 11+ - / 3 *  2 11 + + -

"左优先"原则:只要左边的运算符能先计算,就优先计算左边的(可保证运算唯一)

中缀表达式转后缀表达式(机算)

代码示例:

要将中缀表达式转换为后缀表达式,可以按照以下步骤进行:

  1. 初始化一个空栈,用于保存暂时还不能确定运算顺序的运算符。
  2. 初始化一个空字符串,用于保存最终的后缀表达式。
  3. 从左到右扫描中缀表达式中的每个字符。
  4. 对于每个字符,执行以下操作:
    • 如果是操作数,直接添加到后缀表达式中。
    • 如果是左括号 (,将其压入栈中。
    • 如果是右括号 ),则弹出栈中的运算符并添加到后缀表达式中,直到遇到对应的左括号 (。左括号 ( 弹出但不添加到后缀表达式中。
    • 如果是运算符(如 +-*/ 等),则将栈中所有优先级高于或等于当前运算符的运算符弹出并添加到后缀表达式中。然后将当前运算符压入栈中。
  5. 扫描完中缀表达式后,将栈中剩余的运算符全部弹出并添加到后缀表达式中。

下面是一个C语言的示例代码,用于将中缀表达式转换为后缀表达式:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_SIZE 100// 栈的结构定义
typedef struct {char items[MAX_SIZE];int top;
} Stack;// 初始化栈
void initStack(Stack* stack) {stack->top = -1;
}// 判断栈是否为空
int isEmpty(Stack* stack) {return stack->top == -1;
}// 判断栈是否满
int isFull(Stack* stack) {return stack->top == MAX_SIZE - 1;
}// 压栈
void push(Stack* stack, char value) {if (isFull(stack)) {printf("Error: Stack is full.\n");return;}stack->items[++stack->top] = value;
}// 出栈
char pop(Stack* stack) {if (isEmpty(stack)) {printf("Error: Stack is empty.\n");return '\0';}return stack->items[stack->top--];
}// 获取栈顶元素
char peek(Stack* stack) {if (isEmpty(stack)) {printf("Error: Stack is empty.\n");return '\0';}return stack->items[stack->top];
}// 操作符优先级
int precedence(char op) {if (op == '+' || op == '-') {return 1;} else if (op == '*' || op == '/') {return 2;} else if (op == '(' || op == ')') {return 0;}return -1;
}// 中缀转后缀
void infixToPostfix(char* infix, char* postfix) {Stack stack;initStack(&stack);int i, j;for (i = 0, j = 0; infix[i] != '\0'; ++i) {if (infix[i] == ' ') continue;else if (isdigit(infix[i]) || isalpha(infix[i])) {postfix[j++] = infix[i];} else if (infix[i] == '(') {push(&stack, infix[i]);} else if (infix[i] == ')') {while (!isEmpty(&stack) && peek(&stack) != '(') {postfix[j++] = pop(&stack);}pop(&stack); // 弹出左括号} else {while (!isEmpty(&stack) && precedence(infix[i]) <= precedence(peek(&stack))) {postfix[j++] = pop(&stack);}push(&stack, infix[i]);}}while (!isEmpty(&stack)) {postfix[j++] = pop(&stack);}postfix[j] = '\0'; // 结束字符串
}int main() {char infix[] = "a+b*(c-d)-e/f";char postfix[MAX_SIZE];infixToPostfix(infix, postfix);printf("Infix: %s\n", infix);printf("Postfix: %s\n", postfix);return 0;
}
 

后缀表达式的计算(手算)

从左往右扫描,每遇到一个运算符,就让运算符前面最近的两个操作数执行对应运算,合体为一个操作数

注意:两个操作数的左右顺序

后缀表达式的计算(机算)

用栈实现后缀表达式的计算:

  1. 从左往右扫描下一个元素,直到处理完所以元素
  2. 若扫描到操作数则压入栈,并回到1;否则执行3
  3. 若扫描到运算符,则弹出两个栈顶元素,执行相应运算,运算结果压回栈顶,回到1

注意:后缀表达式先弹出的元素是‘右操作数’

入栈流程:

 中缀表达式转前缀表达式(手算)

  1. 确定中缀表达式中各个运算符的运算顺序
  2. 确定下一个运算符,按照[运算符 左操作数 右操作数]的方式组合成一个新的操作数
  3. 如果还有运算符没被处理,就继续2

"右优先"原则:只要右边的运算符能先计算,就优先算右边

前缀表达式的计算

  1. 从右往左扫描下一个元素,直到处理完所有元素
  2. 若扫描到操作数则压入栈,并回到1;否则执行3
  3. 若扫描到运算符,则弹出两个栈顶元素,执行相应运算,运算结构压回栈顶,回到1

注意前缀表达式先弹出的元素是‘左操作数’

栈在递归中的应用

递归调用时,函数调用栈可称为“递归工作栈”

每进入一层递归,就将递归调用所需信息压入栈顶

每退出一层递归,就从栈顶弹出相应信息

  • 缺点:太多层递归可能会导致栈溢出

递归算法可能会包含很多重复计算 

总结

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/373830.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

设计模式探索:观察者模式

1. 观察者模式 1.1 什么是观察者模式 观察者模式用于建立一种对象与对象之间的依赖关系&#xff0c;当一个对象发生改变时将自动通知其他对象&#xff0c;其他对象会相应地作出反应。 在观察者模式中有如下角色&#xff1a; Subject&#xff08;抽象主题/被观察者&#xf…

C++第四弹 -- 类与对象(中上) (构造函数 析构函数 拷贝构造函数)

目录 前言构造函数1. 概念2. 特征 析构函数1. 概念2. 特征 拷贝构造函数1. 概念2. 特征 总结 前言 让我们一起揭开 C 对象生命周期管理的神秘面纱&#xff0c;掌握构造函数、析构函数和拷贝构造函数的精髓&#xff01; 博客主页: 酷酷学!!! 期待更多好文, 点击关注~ 构造函…

【Neo4j】实战 (数据库技术丛书)学习笔记

Neo4j实战 (数据库技术丛书) 第1章演示了应用Neo4j作为图形数据库对改进性能和扩展性的可能性, 也讨论了对图形建模的数据如何正好适应于Neo4j数据模型,现在到了该动 手实践的时间了。第一章 概述 Neo4j将数据作为顶点和边存储(或者用Neo4j术语,节点和关系存 储)。用户被定…

外卖商城平台小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;商家管理&#xff0c;骑手管理&#xff0c;商品类型管理&#xff0c;商品信息管理&#xff0c;订单信息管理 微信端账号功能包括&#xff1a;系统首页&#xff0c;商品信息&#…

深入了解java锁升级可以应对各种疑难问题

对于java锁升级&#xff0c;很多人都停留在比较浅层的表面理解&#xff0c;一定程度下也许够用&#xff0c;但如果学习其中的细节&#xff0c;我们更好地理解多线程并发时各种疑难问题的应对方式&#xff01; 因此我将锁升级过程中可能涉及的大部分细节或者疑问都整合成了一篇…

后端之路——文件本地上传

一、基础原理 文件上传是一个很基础的知识点&#xff0c;尤其是本地上传&#xff0c;在现实开发基本都是云上传&#xff0c;但是作为一个基础要简单了解一下 首先前端我就不多讲解了&#xff0c;网页开发里用<form>表单可以上传文件&#xff0c;只需要加上这三属性&…

防火墙基础实验配置

一&#xff0c;实验拓扑 二&#xff0c;实验需求&#xff1a; 1.DMZ区内的服务器&#xff0c;办公区仅能在办公时间内&#xff08;9&#xff1a;00 - 18&#xff1a;00&#xff09;可以访问&#xff0c;生产区的设备全天可以访问 2.生产区不允许访问互联网&#xff0c;办公区…

如何批量更改很多个文件夹里的文件名中包含文件夹名?

&#x1f3c6;本文收录于《CSDN问答解惑-专业版》专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收…

共生与变革:AI在开发者世界的角色深度剖析

在科技日新月异的今天&#xff0c;人工智能&#xff08;AI&#xff09;已不再是遥不可及的概念&#xff0c;而是逐步渗透到我们工作与生活的每一个角落。对于开发者这一群体而言&#xff0c;AI的崛起既带来了前所未有的机遇&#xff0c;也引发了关于其角色定位的深刻讨论——AI…

STM32-Unix时间戳和BKP备份寄存器以及RTC实时时钟

本内容基于江协科技STM32视频学习之后整理而得。 文章目录 1. Unix时间戳1.1 Unix时间戳简介1.2 UTC/GMT1.3 时间戳转换 2. BKP备份寄存器2.1 BKP简介2.2 BKP基本结构2.3 BKP库函数 3. RTC实时时钟3.1 RTC简介3.2 RTC框图3.3 RTC基本结构3.4 硬件电路3.5 RTC操作注意事项3.6 R…

修改服务器挂载目录

由于我们的项目通常需要挂载一个大容量的数据盘来存储文件数据&#xff0c;所以我们每台服务器都需要一个默认的挂载目录来存放这些数据&#xff0c;但是由于我们的误操作&#xff0c;导致挂载目录名字建错了&#xff0c;这时候后端就读不到挂载目录了&#xff0c;那我们我们的…

在mysql中delete和truncated的相同点和区别点

相同点 删除数据&#xff1a;两者都会删除表中的数据。影响数据&#xff1a;两者都不删除表结构&#xff0c;只影响表中的数据。 区别点 操作方式&#xff1a; DELETE&#xff1a;逐行删除数据&#xff0c;可以使用 WHERE 子句来指定删除的条件。如果不加 WHERE 子句&#…

NI 5G大规模MIMO测试台:将理论变为现实

目录 概览引言MIMO原型验证系统MIMO原型验证系统硬件LabVIEW通信系统设计套件&#xff08;简称LabVIEW Communications&#xff09;CPU开发代码FPGA代码开发硬件和软件紧密集成 LabVIEW Communications MIMO应用框架MIMO应用框架特性单用户MIMO和多用户MIMO基站和移动站天线数量…

Hive 高可用分布式部署详细步骤

目录 系统版本说明 hive安装包下载及解压 上传mysql-connector-java的jar包 配置环境变量 进入conf配置文件中&#xff0c;将文件重命名 在hadoop集群上创建文件夹 创建本地目录 修改hive-site.xml文件 同步到其他的节点服务器 修改node02中的配置 hive-site.xml 修改…

如何在多个服务器上安装WordPress分布式部署

许多网络主机现在保证其服务的正常运行时间为 99.9%&#xff0c;但这仍然每年最多有 8.7 小时的停机时间。 许多公司不能够承担这种风险。例如。在超级碗比赛中失败的体育新闻网站可能会失去忠实的追随者。 我们通过设置维护高可用性 WordPress分布式部署配置来帮助 WordPres…

C基础day8

一、思维导图 二、课后习题 #include<myhead.h> #define Max_Stu 100 //函数声明 //学生信息录入函数 void Enter_stu(int *Num_Stu,char Stu_name[][50],int Stu_score[]); //查看学生信息 void Print_stu(int Num_Stu,char Stu_name[][50],int Stu_score[]); //求出成绩…

latex英文转中文word,及一些latex相关工具分享

前言&#xff1a;想要转换latex生成的英文pdf文件为中文word文件 一、主要步骤 1、文字翻译&#xff1a;直接使用谷歌翻译等辅助将英文翻译成中文即可&#xff1b; 支持英文pdf文件全文翻译&#xff0c;再用迅捷PDF转换器之类的转成word&#xff0c;再手动调整。 https://app…

网络编程:各协议头(数据报格式)

一、mac头 二、ip头 protocol——tcp/udp &#xff08;7&#xff09;TTL——生存时间 三、tcp头 四、udp头

第三课网关作用

实验拓扑图&#xff1a; 基础配置&#xff1a; PC1的基础配置 PC2的基础配置&#xff1a; PC4的基础配置 AR1添加PC4网段: 并且添加pc1,pc2的网段。 并且添加pc1,pc2的网段。 原理&#xff1a;PC4先把数据交给100.100.100.1&#xff0c;交给了路由器&#xff0c;路由器再把数…

ARM学习(29)NXP 双coreMCU IMX1160学习----NorFlash 启动引脚选择

ARM学习&#xff08;28&#xff09;NXP 双coreMCU IMX1160学习----NorFlash 启动引脚选择 1、多种启动方式介绍 IMX1166 支持多组flexSPI 引脚启动&#xff0c;FlexSPI1以及FlexSPI2&#xff0c;通过boot cfg可以切换FlexSPI得实例。 每个实例又支持多组引脚&#xff0c;总共…