【数据结构】栈的应用

目录

0  引言

1  栈在括号匹配中的应用

2  栈在表达式求值中的应用

        2.1 算数表达式

        2.2 中缀表达式转后缀表达式

2.3 后缀表达式求值

3  栈在递归中的应用

3.1 栈在函数调用中的作用

3.2 栈在函数调用中的工作原理

4  总结


0  引言

        栈(Stack)是一种非常基本且重要的数据结构,它们在许多计算机科学和软件工程的应用中都有广泛的用途。

        栈:

                ①括号匹配;

                ②表达式求值;

                ③递归函数调用。

1  栈在括号匹配中的应用

        表达式中有两种括号:圆括号 ( ) 和 方括号 [ ],嵌套的顺序任意,但应为正确的格式。

        例如:( ( [ ] [ ] ) ) 为正确格式。

        但如何用算法实现括号匹配问题?

        思路如下:

        (1)初始一个空栈;

        (2)顺序读入括号;

        (3)当读入的为左括号,将继续读入括号,直到读入第一个右括号。那将检测与之最近的左括号是否与之相匹配,若匹配,则出栈;若不匹配,则退出程序。当程序结束时,栈为空。反之,则表明括号序列的格式不正确。

        代码如下:

#include <stdio.h>  
#include <stdlib.h>  
#include <stdbool.h>  #define MAX_SIZE 100 // 假设栈的最大大小  typedef struct {  char data[MAX_SIZE];  int top;  
} Stack;  // 初始化栈  
void initStack(Stack *s) {  s->top = -1;  
}  // 判断栈是否为空  
bool isEmpty(Stack *s) {  return s->top == -1;  
}  // 入栈  
void push(Stack *s, char c) {  if (s->top >= MAX_SIZE - 1) {  printf("Stack overflow\n");  return;  }  s->data[++s->top] = c;  
}  // 出栈  
char pop(Stack *s) {  if (isEmpty(s)) {  printf("Stack underflow\n");  return '#'; // 返回一个无效字符,或可以选择抛出一个错误  }  return s->data[s->top--];  
}  // 检查两个括号是否匹配  
bool isMatch(char c1, char c2) {  if (c1 == '(' && c2 == ')') return true;  if (c1 == '[' && c2 == ']') return true;  if (c1 == '{' && c2 == '}') return true;  return false;  
}  // 括号匹配函数  
bool isBalanced(char *str) {  Stack s;  initStack(&s);  for (int i = 0; str[i] != '\0'; i++) {  if (str[i] == '(' || str[i] == '[' || str[i] == '{') {  push(&s, str[i]);  } else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {  if (isEmpty(&s)) {  // 栈为空,但遇到了右括号,不匹配  return false;  }  char topChar = pop(&s);  if (!isMatch(topChar, str[i])) {  // 栈顶元素与当前右括号不匹配  return false;  }  }  }  // 如果栈为空,则所有括号都匹配  return isEmpty(&s);  
}  int main() {  char str[MAX_SIZE];  printf("Enter a string with brackets: ");  scanf("%s", str); if (isBalanced(str)) {  printf("The brackets are balanced.\n");  } else {  printf("The brackets are not balanced.\n");  }  return 0;  
}

2  栈在表达式求值中的应用

        2.1 算数表达式

        中缀表达式是人们常用的算术表达式,即操作符以中缀形式处于操作数之间。但在计算机中,中缀表达式相较于前缀和后缀表达式来说,更不易被计算机识别。前缀表达式成为波兰式,后缀表达式又称逆波兰式。

        2.2 中缀表达式转后缀表达式

        (1)手算方法:

        ①根据运算顺序对表达式运算符排号;

        ②根据运算符排号顺序,将运算符及两端的操作数以(左操作数 右操作数 运算符)的顺序重新组合。

        例如:( A + B ) * C + ( D - E ) / F 转后缀表达式的过程如下:

        (2)算法实现:

        ①初始一个栈;

        ②遇到操作数,直接加入后缀表达式;

        ③遇到界限符,若为左括号直接入栈,若为右括号,则依次弹出栈中的运算符,加入后缀表达式,知道弹出左括号为止。需要注意的是,左括号和右括号直接删除,不加入后缀表达式。

        ④遇到运算符,则看运算符的优先级,若高于除左括号外的栈顶元素,则直接入栈。反之,则依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,直到遇到低于他的优先级的运算符,才入栈。

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <stdbool.h>  #define MAX_SIZE 100  typedef struct {  char data[MAX_SIZE];  int top;  
} Stack;  // 初始化栈  
void initStack(Stack *s) {  s->top = -1;  
}  // 判断栈是否为空  
bool isEmpty(Stack *s) {  return s->top == -1;  
}  // 入栈  
bool push(Stack *s, char c) {  if (s->top >= MAX_SIZE - 1) {  return false; // 栈溢出  }  s->data[++s->top] = c;  return true;  
}  // 出栈  
char pop(Stack *s) {  if (isEmpty(s)) {  return '\0'; // 栈空,返回空字符  }  return s->data[s->top--];  
}  // 获取栈顶元素,但不弹出  
char peek(Stack *s) {  if (isEmpty(s)) {  return '\0'; // 栈空,返回空字符  }  return s->data[s->top];  
}  // 运算符的优先级比较(这里只处理了基本的四则运算)  
int precedence(char op) {  if (op == '+' || op == '-') {  return 1;  }  if (op == '*' || op == '/') {  return 2;  }  return 0; // 如果不是运算符,返回0  
}  // 将中缀表达式转换为后缀表达式  
void infixToPostfix(char *infix, char *postfix) {  Stack s;  initStack(&s);  int i = 0, j = 0;  while (infix[i] != '\0') {  if (infix[i] >= '0' && infix[i] <= '9') {  // 如果是操作数,直接添加到后缀表达式中  postfix[j++] = infix[i++];  postfix[j++] = ' '; // 假设操作数都是个位数,用空格分隔  } else if (infix[i] == '(') {  // 如果是左括号,直接入栈  push(&s, infix[i++]);  } else if (infix[i] == ')') {  // 如果是右括号,则弹出栈中元素直到遇到左括号  while (!isEmpty(&s) && peek(&s) != '(') {  postfix[j++] = pop(&s);  postfix[j++] = ' ';  }  // 弹出左括号,但不加入后缀表达式  pop(&s);  i++;  } else {  // 如果是运算符  while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(infix[i])) {  // 如果栈不为空且栈顶元素优先级高于或等于当前运算符,弹出栈顶元素  postfix[j++] = pop(&s);  postfix[j++] = ' ';  }  // 当前运算符入栈  push(&s, infix[i++]);  }  }  // 弹出栈中剩余的所有运算符  while (!isEmpty(&s)) {  postfix[j++] = pop(&s);  postfix[j++] = ' ';  }  // 添加字符串结束符  postfix[j] = '\0';  
}  int main() {  char infix[MAX_SIZE], postfix[MAX_SIZE * 2]; // 后缀表达式可能更长,因此分配更多空间  printf("Enter an infix expression: ");  scanf("%s", infix); // 注意:这里不会处理空格和复杂输入  infixToPostfix(infix, postfix);  printf("Postfix expression: %s\n", postfix);  return 0;  
}

2.3 后缀表达式求值

        后缀表达式(也称为逆波兰表示法或逆波兰记法)是一种不需要括号来标明运算符的优先级的数学表达式。在这种表示法中,所有的运算符都放在操作数的后面。

        求值后缀表达式的基本步骤如下:

  • 初始化一个栈,用于存储操作数。
  • 从左到右扫描后缀表达式。
  • 如果扫描到操作数,则将其压入栈中。
  • 如果扫描到运算符,则从栈中弹出两个操作数(先弹出的为右操作数,后弹出的为左操作数),将这两个操作数作为运算符的输入进行运算,然后将结果压回栈中。
  • 重复步骤2-4,直到后缀表达式扫描完毕。
  • 栈中剩下的元素就是表达式的值。

        示例

        后缀表达式:3 4 + 5 *

        求值过程:

  1. 扫描到 3,压入栈:[3]
  2. 扫描到 4,压入栈:[3, 4]
  3. 扫描到 +,弹出 4 和 3,计算 3 + 4 得到 7,压入栈:[7]
  4. 扫描到 5,压入栈:[7, 5]
  5. 扫描到 *,弹出 5 和 7,计算 7 * 5 得到 35,压入栈:[35]
  6. 扫描完毕,栈中元素 35 即为表达式的值。

        下面是实现代码(以上述示例为例):

#include <stdio.h>  
#include <stdlib.h>  
#include <ctype.h>  
#include <string.h>  #define MAX_STACK_SIZE 100  typedef struct {  double data[MAX_STACK_SIZE];  int top;  
} Stack;  // 初始化栈  
void initStack(Stack *s) {  s->top = -1;  
}  // 判断栈是否为空  
int isEmpty(Stack *s) {  return s->top == -1;  
}  // 压栈操作  
void push(Stack *s, double value) {  if (s->top >= MAX_STACK_SIZE - 1) {  printf("Stack overflow\n");  exit(1);  }  s->data[++s->top] = value;  
}  // 弹栈操作  
double pop(Stack *s) {  if (isEmpty(s)) {  printf("Stack underflow\n");  exit(1);  }  return s->data[s->top--];  
}  // 求值后缀表达式  
double evaluatePostfix(const char *postfix) {  Stack s;  initStack(&s);  const char *token = strtok((char *)postfix, " "); // 假设操作符和操作数之间用空格分隔  while (token != NULL) {  if (isdigit(token[0])) { // 如果是操作数  double value = atof(token);  push(&s, value);  } else { // 如果是运算符  double rightOperand = pop(&s); // 弹出右操作数  double leftOperand = pop(&s); // 弹出左操作数  switch (token[0]) {  case '+':  push(&s, leftOperand + rightOperand);  break;  case '-':  push(&s, leftOperand - rightOperand);  break;  case '*':  push(&s, leftOperand * rightOperand);  break;  case '/':  if (rightOperand != 0.0) {  push(&s, leftOperand / rightOperand);  } else {  printf("Error: Division by zero\n");  exit(1);  }  break;  default:  printf("Error: Unknown operator\n");  exit(1);  }  }  token = strtok(NULL, " "); // 继续获取下一个token  }  if (!isEmpty(&s)) {  return pop(&s); // 栈中剩下的元素就是表达式的值  } else {  printf("Error: Invalid postfix expression\n");  exit(1);  }  
}  int main() {  const char *postfix = "3 4 + 5 *";  double result = evaluatePostfix(postfix);  printf("Result: %lf\n", result);  return 0;  
}

3  栈在递归中的应用

3.1 栈在函数调用中的作用

  • 参数传递:当调用一个函数时,需要传递参数给该函数。这些参数会被压入栈中,以便函数内部能够访问和使用它们。
  • 局部变量分配:函数内部定义的局部变量会在栈上分配空间。这些变量的生命周期与函数的执行周期相同,当函数执行完毕后,这些局部变量所占用的栈空间会被自动释放。
  • 保存调用的返回地址:在函数调用时,CPU需要知道函数执行完毕后应该返回到哪个位置继续执行。这个返回地址会被保存在栈中,以便函数执行完毕后能够正确地返回到调用它的位置。
  • 保存寄存器以供恢复:在函数调用和返回的过程中,CPU的寄存器状态会发生变化。为了能够在函数返回后恢复原来的寄存器状态,栈会保存这些寄存器的值。

3.2 栈在函数调用中的工作原理

  • 函数调用:当调用一个函数时,系统首先会创建一个新的栈帧(stack frame)来保存该函数的执行环境。这个栈帧包含了函数的返回地址、参数、局部变量等信息。然后,系统会将当前程序的执行状态(如返回地址、寄存器状态等)压入栈中,以便在函数执行完毕后能够恢复。
  • 函数执行:在函数执行过程中,函数会访问栈帧中的参数和局部变量,并根据需要进行计算和操作。同时,如果函数内部调用了其他函数,系统也会为这些被调用的函数创建新的栈帧,并将当前函数的执行状态压入栈中保存。
  • 函数返回:当函数执行完毕或者遇到return语句时,系统会弹出当前函数的栈帧,并根据栈帧中的返回地址返回到调用它的位置继续执行。在返回之前,系统还会恢复调用该函数时的寄存器状态。

        下面将给出一个例子:

        例如:阶乘,大家可以自行调试;

#include <stdio.h>int step(int n){if(n==1)return 1;elsereturn n*step(n-1);
}int main(){int n,s;scanf("%d",&n);s=step(n);printf("%d",s);
}

4  总结

        在本文中,我们深入探讨了栈这一数据结构及其在各种应用场景中的重要作用。栈作为一种后进先出(LIFO)的数据结构,其独特的操作方式——压栈(push)和弹栈(pop),使得它在计算机科学和软件开发中占据了不可或缺的地位。

        详细讨论了栈在多个领域中的应用。其中,后缀表达式的求值是一个经典的栈应用示例。在这个问题中,我们利用栈来存储操作数,并通过操作数的弹出和结果的压入,实现了表达式的正确计算。这种方法不仅简化了表达式的处理流程,而且提高了计算效率。

        此外,栈还在函数调用、递归等方面发挥着重要作用。在函数调用中,栈用于存储局部变量和返回地址,确保函数能够正确地返回并继续执行。在递归算法中,栈用于保存递归调用的中间结果,从而避免重复计算。

        综上所述,栈作为一种基本而强大的数据结构,在各个领域都有着广泛的应用。通过学习和掌握栈的使用方法和应用场景,我们能够更好地解决实际问题,提高编程效率。

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

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

相关文章

WPF视频学习-基础知识篇

1.简介WPF&#xff1a; C# 一套关于windows界面应用开发框架 2.WPF和winform的差别 &#xff0c;(WPF比较新) 创建新项目使用模板&#xff1a; WPF使用.xaml后缀&#xff0c;双击可查看操作界面和设置代码&#xff0c;其文件展开之后中有MainWindow.xaml.cs为程序交互逻辑。…

linux笔记8--安装软件

文章目录 1. PMS和软件安装的介绍2. 安装、更新、卸载安装更新ubuntu20.04更新镜像源&#xff1a; 卸载 3. 其他发行版4. 安装第三方软件5. 推荐 1. PMS和软件安装的介绍 PMS(package management system的简称)&#xff1a;包管理系统 作用&#xff1a;方便用户进行软件安装(也…

nginx mirror流量镜像详细介绍以及实战示例

nginx mirror流量镜像详细介绍以及实战示例 1.nginx mirror作用2.nginx安装3.修改配置3.1.nginx.conf3.2.conf.d目录下添加default.conf配置文件3.3.nginx配置注意事项3.3.nginx重启 4.测试 1.nginx mirror作用 为了便于排查问题&#xff0c;可能希望线上的请求能够同步到测试…

PyCharm QThread 设置断点不起作用

背景&#xff1a; 端午节回来上班第一天&#xff0c;不想干活&#xff0c;领导又再后面看着&#xff0c;突然想起一个有意思的问题&#xff0c;为啥我的程序在子进程QThread的子类里打的断点不好用呢&#xff1f;那就解决一下这个问题吧。 原因&#xff1a; 如果您的解释器上…

开发框架表单设计器办公效率高吗?

对于很多职场人来说&#xff0c;拥有一款可以提质、增效、降本的办公利器是大有裨益的。随着科技的进步和发展&#xff0c;低代码技术平台凭借可视化界面、易操作、好维护、高效率等多个优势特点&#xff0c;成为大众喜爱的办公利器。开发框架表单设计器是减少信息孤岛&#xf…

macbook本地部署 pyhive环境连接 hive用例

前言 公司的测试和生产环境中尚未提供基于Hive的客户端。若希望尝试操作Hive表&#xff0c;目前一个可行的方案是使用Python语言&#xff0c;通过借助pyhive库&#xff0c;您可以对Hive表进行各种操作。以下是一些示例记录供您参考。 一、pyhive是什么&#xff1f; PyHive是一…

从零到一建设数据中台(番外篇)- 数据中台UI欣赏

番外篇 - 数据中台 UI 欣赏 话不多说&#xff0c;直接上图。 数据目录的重要性&#xff1a; 数据目录是一种关键的信息管理工具&#xff0c;它为组织提供了一个全面的、集中化的数据资产视图。 它不仅记录了数据的存储位置&#xff0c;还详细描述了数据的结构、内容、来源、使…

细说ARM MCU的串口接收数据的实现过程

目录 一、硬件及工程 1、硬件 2、软件目的 3、创建.ioc工程 二、 代码修改 1、串口初始化函数MX_USART2_UART_Init() &#xff08;1&#xff09;MX_USART2_UART_Init()串口参数初始化函数 &#xff08;2&#xff09;HAL_UART_MspInit()串口功能模块初始化函数 2、串口…

批量申请SSL证书如何做到既方便成本又最低

假如您手头拥有1千个域名&#xff0c;并且打算为每一个域名搭建网站&#xff0c;那么在当前的网络环境下&#xff0c;您必须确保这些网站通过https的方式提供服务。这意味着&#xff0c;您将为每一个域名申请SSL证书&#xff0c;以确保网站数据传输的安全性和可信度。那么&…

面试-NLP八股文

机器学习 交叉熵损失&#xff1a; L − ( y l o g ( y ^ ) ( 1 − y ) l o g ( 1 − ( y ^ ) ) L-(ylog(\hat{y}) (1-y)log(1-(\hat{y})) L−(ylog(y^​)(1−y)log(1−(y^​))均方误差&#xff1a; L 1 n ∑ i 1 n ( y i − y ^ i ) 2 L \frac{1}{n}\sum\limits_{i1}^{n}…

【ai】openai-quickstart 配置pycharm工程

之前都是本地执行脚本【AI】指定python3.10安装Jupyter Lab环境为:C:\Users\zhangbin\AppData\Local\Programs\Python\Python310 参考之前创建的python工程 使用的是局部的私有的虚拟环境 pycharm给出的解释器 直接使用现有的,不new了 可以选择3.10 :可以选虚拟的:

Rust-02-变量与可变性

在Rust中&#xff0c;变量和可变性是两个重要的概念。 变量&#xff1a;变量是用于存储数据的标识符。在Rust中&#xff0c;变量需要声明其类型&#xff0c;例如&#xff1a; let x: i32 5; // 声明一个名为x的变量&#xff0c;类型为i32&#xff08;整数&#xff09;&#…

SpringCloud 前端-网关-微服务-微服务间实现信息共享传递

目录 1 网关获取用户校验信息并保存至请求头&#xff08;前端-网关&#xff09; 2 微服务获取网关中的用户校验信息&#xff08;网关-微服务&#xff09; 2.1 一般的做法是在公共的module中添加&#xff0c;此处示例为common 公共配置module中添加 2.2 定义拦截器 2.3 定义…

简单通用的系统安装、备份、还原方法,支持 ARM 系统【Ventory+FirePE+DiskGenius】

文章目录 0. 简介1. 制作 Ventory 启动盘1.1. 下载 Ventory1.2. 制作 Ventory 启动盘 2. 添加 FirePE 等系统镜像到启动盘2.1. 下载 FirePE2.2. 导出 .iso 系统镜像文件2.3. .iso 系统镜像文件添加至启动盘 3. 启动 FirePE 等系统镜像3.1. 在 bios 中选择启动盘启动3.2. 启动系…

# RocketMQ 实战:模拟电商网站场景综合案例(八)

RocketMQ 实战&#xff1a;模拟电商网站场景综合案例&#xff08;八&#xff09; 一、RocketMQ 实战&#xff1a;模拟电商网站场景综合案例–下单异常问题演示 1.png 1、如果订单在扣减库存、扣减优惠券、扣减余额后&#xff0c;在 未 确认订单 前&#xff0c;出现了异常&am…

vue+element el-select动态加减框数量及验证下拉框选项动态置灰(选中行的下拉框换个值后,原值没办法监控这个问题也解决了)

1效果: 2部分主要(HTML): 1:这个位置主要就是看看方法什么的吧,还有大概的结构 2:change"sort_Change(item,tablelists.orderbyList)这两个参数(都有大用): (1)item:代表每次你操作的这个数据 (2)tablelists.orderbyList:代表你这一共有几行数据(上边这个例子就会得到一个…

LCD电子广告牌课程设计

概述 1.1课程设计简介 亮丽实用的广告牌可以给我们的生活添加光彩、可以给店铺招揽生意。传统的广告牌都是固定的汉字&#xff0c;并且时间长了会掉色&#xff0c;使汉字模糊难认&#xff0c;这就给我的生活带来很多的不便。尤其到了晚上传统广告牌就会失去其该有的作用。所以在…

2024年安全现状报告

2024 年安全现状报告有些矛盾。尽管安全专业人员的道路困难重重&#xff0c;比如说严格的合规要求、不断升级的地缘政治紧张局势和更复杂的威胁环境&#xff0c;但整个行业还是在取得进展。 许多组织表示&#xff0c;与前几年相比&#xff0c;网络安全变得更容易管理。组织之间…

AI赋能银行国际结算审单:合合信息抽取技术的实践与应用

官.网地址&#xff1a;合合TextIn - 合合信息旗下OCR云服务产品 时下&#xff0c;银行国际业务是金融体系的重要组成部分&#xff0c;涵盖了外汇交易、国际结算、贸易融资、跨境投资等领域&#xff0c;这些业务对于国际贸易和全球经济发展具有重要作用。国际业务部门单据、凭证…

OpenGL系列(五)纹理贴图

概述 OpenGL纹理是一种在三维图形中应用纹理映射的技术。纹理是一张图像&#xff0c;可以应用到三维模型的表面上&#xff0c;从而使得模型看起来更加真实和具有细节。通过纹理映射&#xff0c;可以将图像的像素值与三维模型的顶点进行匹配&#xff0c;从而为模型的表面增加细节…