数据结构-栈和队列的应用(验证括号的正确性,表达式求值,层次遍历)

本文主要是介绍数据结构-栈和队列的应用(验证括号的正确性,表达式求值,层次遍历),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

栈和队列的应用

  栈的应用

  验证括号的正确性

  题目很简单就是输入一串字符,判断字符中的括号是否合法。直接上代码:

#include <iostream>
#include <string.h>
using namespace std;typedef char ElemType;
#define MAXSIZE 100typedef struct Stack
{ElemType data[MAXSIZE];int top;
}Stack;void InitStack(Stack& S) {S.top = -1;
}bool StackEmpty(Stack S) {if (S.top == -1) {return true;}return false;
}bool Push(Stack& S, ElemType x) {if (S.top == MAXSIZE - 1) {return false;}S.top++;S.data[S.top] = x;return true;
}
bool Pop(Stack& S, ElemType& x) {if (S.top == -1) {return false;}x = S.data[S.top];S.top--;return true;
}ElemType GetTop(Stack S) {return S.data[S.top];
}int main() {Stack S;InitStack(S);string str;cin >> str;//flag标志状态 true为括号匹配,false为不匹配bool flag = true;for (int i = 0; i < str.size(); i++) {//元素若为{,(,[则入栈if ((str[i] == '{') || (str[i] == '[') || (str[i] == '(')) {Push(S, str[i]);}//元素若为},),]则出栈 赋值给rightif ((str[i] == '}') || (str[i] == ']') || (str[i] == ')')) {if ((str[i] == '}' && GetTop(S) == '{') || (str[i] == ']' && GetTop(S) == '[') || (str[i] == ')' && GetTop(S) == '(')) {char top = Pop(S, top);continue;}else {Push(S, str[i]);}}}if (S.top != -1) {    //当栈不为空时flag = false;}if (flag == false) {cout << "括号不匹配!" << endl;}else cout << "括号匹配!" << endl;system("pause");return 0;
}

  实验结果:

image-20210122155026920

image-20210122155116917

  表达式求值

  要求一个表达式的结果,例如 9 +(3 - 1) * 3 + 1 ,我们可以直接算出来,但是计算机不会,计算机一般将这种表达式转换成后缀表达式,运算符在操作数后面,并且运算也是根据优先级排列好的,没有括号,利于计算机的计算,如上述表达式转换为后缀表示式为:

9 3 1 - 3 * 10 + ,但是我们现在要实现的是中缀表达式的求值。计算思路:

  • 使用两个栈,stack0用于存储操作数,stack1用于存储操作符
  • 从左往右扫描,遇到操作数入栈stack0
  • 遇到操作符时,如果优先级低于或等于栈顶操作符优先级,则从stack0弹出两个元素进行计算,并压入stack0,继续与栈顶操作符的比较优先级
  • 如果遇到操作符高于栈顶操作符优先级,则直接入栈stack1
  • 遇到左括号,直接入栈stack1,遇到右括号,则直接出栈并计算,直到遇到左括号
//算符优先法
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;  
const int maxn=110; 
char priority[7][7]={ {'>','>','<','<','<','>','>'},  {'>','>','<','<','<','>','>'},  {'>','>','>','>','<','>','>'},  {'>','>','>','>','<','>','>'},  {'<','<','<','<','<','=','0'},   // 此行"("=")"表示左右括号相遇,括号内运算已完成 {'>','>','>','>','0','>','>'},  {'<','<','<','<','<','0','='}    // "=" 表示整个表达式求值完毕 };                               //  "0"表示不可能出现这种情况 ( 语法错误 ) //Precede 用于判断运算符栈栈顶运算符 a1 与读入运算符 a2 之间的优先关系函数 
char Procede(char a,char b){   // 建立 pre[][] 到 运算符间的映射关系 int i,j;  switch(a){  case'+':i=0;break;  case'-':i=1;break;  case'*':i=2;break;  case'/':i=3;break;  case'(':i=4;break;  case')':i=5;break;  case'#':i=6;break;   // # 是表达式的结束符 }  switch(b){  case'+':j=0;break;  case'-':j=1;break;  case'*':j=2;break;  case'/':j=3;break;  case'(':j=4;break;  case')':j=5;break;  case'#':j=6;break;  }  return priority[i][j];  
}int Operate(int m,int n,char x){  if(x=='+')  return m+n;  if(x=='-')  return n-m;  if(x=='*')  return m*n;  if(x=='/')  return n/m;  
}  
// EvaluuateExpression-reduced
int main(){stack <int> OPND;  // Operand stackstack <char> OPTR;  // Operator stackOPTR.push('#');//char ss[2]="#";//尾部有\0 char s[maxn];cin>>s;strcat(s,ss);// 运算式尾部加 "#"--结束运算符 char c=s[0];int k=1;while(c!='#'||OPTR.top()!='#'){  //表达式未读完或者运算未完 int y=0;  if(c>='0'&&c<='9'){    while(c>='0'&&c<='9'){  // 读入连续的数字 y=y*10+(c-'0');  c=s[k++];  }  OPND.push(y);  // 把读进的数字入数字栈 }else{switch(Procede(OPTR.top(),c))  {  case'<':  //栈顶元素优先权低 OPTR.push(c);  c=s[k++];  break;  case'=':  OPTR.pop();  // 脱括号 c=s[k++];  // 读入下一个字符 break;  case'>':  //退栈并将运算结果入栈 char x=OPTR.top();OPTR.pop();  int m=OPND.top();OPND.pop();  int n=OPND.top();OPND.pop();  OPND.push(Operate(m,n,x));  break;    } }}cout<<OPND.top();return 0;
}

  实验结果:

image-20210122155312932

  队列的应用

  层次遍历

  利用队列存储每一层的结点,再存储到数组中,很容易理解。下面是套路:

vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;if (root != nullptr)   q.push(root);vector<vector<int>> res;while (!q.empty()) {int sz = q.size();vector<int> temp;for (int i = 0; i < sz; i++) {TreeNode* cur = q.front();q.pop();temp.push_back(cur->val);if (cur->left != nullptr)q.push(cur->left);if (cur->right != nullptr)q.push(cur->right);}res.push_back(temp);}return res;
}

  队列在计算机系统中的应用

  一、解决主机与外部设备之间速度不匹配的问题。

  二、解决由多用户引起的资源竞争问题。

如果觉得本文对你有帮助的话,不妨关注作者一波,小小的关注其实对我很重要。更多高质量内容与资料请访问:数据结构简单学,个人主页:修心的小屋
如果喜欢的话,不妨关注一波,谢谢啦。
在这里插入图片描述

这篇关于数据结构-栈和队列的应用(验证括号的正确性,表达式求值,层次遍历)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/652908

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

SpringBoot @Scheduled Cron表达式使用方式

《SpringBoot@ScheduledCron表达式使用方式》:本文主要介绍SpringBoot@ScheduledCron表达式使用方式,具有很好的参考价值,希望对大家有所帮助,如有... 目录Cron 表达式详解1. 表达式格式‌2. 特殊字符解析3. 常用示例‌4. 重点规则5. 动态与复杂场景‌

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

SpringBoot整合MybatisPlus的基本应用指南

《SpringBoot整合MybatisPlus的基本应用指南》MyBatis-Plus,简称MP,是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,下面小编就来和大家介绍一下... 目录一、MyBATisPlus简介二、SpringBoot整合MybatisPlus1、创建数据库和

Spring Boot 集成 Quartz 使用Cron 表达式实现定时任务

《SpringBoot集成Quartz使用Cron表达式实现定时任务》本文介绍了如何在SpringBoot项目中集成Quartz并使用Cron表达式进行任务调度,通过添加Quartz依赖、创... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启