【408考点之数据结构】表达式求值和括号匹配

2024-06-23 01:28

本文主要是介绍【408考点之数据结构】表达式求值和括号匹配,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

表达式求值和括号匹配

表达式求值

表达式求值是计算机科学中的一个基本问题,涉及将数学表达式转换为计算机可以理解和处理的形式。通常,我们使用栈来辅助求值过程,特别是在处理中缀表达式转后缀表达式和后缀表达式求值时。

中缀表达式转后缀表达式

中缀表达式(如a + b * c)是我们通常书写数学表达式的形式。为了方便计算机处理,我们将其转换为后缀表达式(逆波兰表达式,RPN)。转换过程如下:

  1. 扫描中缀表达式的每个字符。
  2. 遇到操作数,直接输出。
  3. 遇到左括号,压入栈。
  4. 遇到右括号,不断弹出栈顶元素直到左括号。
  5. 遇到运算符,若其优先级高于栈顶运算符,压入栈,否则不断弹出栈顶运算符直到栈为空或当前运算符的优先级高于栈顶运算符,再将当前运算符压入栈。
后缀表达式求值

后缀表达式(如abc*+)的求值过程如下:

  1. 扫描后缀表达式的每个字符。
  2. 遇到操作数,压入栈。
  3. 遇到运算符,弹出栈顶两个操作数,进行相应运算,并将结果压入栈。
  4. 最终栈顶元素即为表达式的结果。
括号匹配

括号匹配是验证括号在表达式中是否成对出现和正确嵌套的过程。常见的括号有圆括号()、方括号[]和花括号{}。匹配过程通常使用栈实现:

  1. 扫描输入字符串,遇到左括号压入栈。
  2. 遇到右括号,检查栈顶元素是否为对应的左括号,若是则弹出栈顶元素,否则匹配失败。
  3. 最后栈为空则匹配成功,否则匹配失败。

实际题目及解答

题目1:中缀表达式转后缀表达式

将中缀表达式 a + b * (c - d) 转换为后缀表达式。

解答:

  1. a:输出 a
  2. +:压栈 +
  3. b:输出 b
  4. *:压栈 *
  5. (:压栈 (
  6. c:输出 c
  7. -:压栈 -
  8. d:输出 d
  9. ):弹出栈顶元素 - 输出,再弹出栈顶元素 (
  10. 弹出栈顶元素 * 输出
  11. 弹出栈顶元素 + 输出

最终后缀表达式为:ab c d - * +

题目2:后缀表达式求值

求后缀表达式 2 3 1 * + 9 - 的值。

解答:

  1. 2:压栈 2
  2. 3:压栈 3
  3. 1:压栈 1
  4. *:弹出 13,计算 3 * 1 = 3,压栈 3
  5. +:弹出 32,计算 2 + 3 = 5,压栈 5
  6. 9:压栈 9
  7. -:弹出 95,计算 5 - 9 = -4,压栈 -4

最终结果为 -4

题目3:括号匹配

验证字符串 {[()()]} 是否匹配。

解答:

  1. {:压栈 {
  2. [:压栈 [
  3. (:压栈 (
  4. ):栈顶是 (,匹配,弹出 (
  5. (:压栈 (
  6. ):栈顶是 (,匹配,弹出 (
  7. ]:栈顶是 [,匹配,弹出 [
  8. }:栈顶是 {,匹配,弹出 {

最后栈为空,匹配成功。

题目4:括号匹配

验证字符串 [(]) 是否匹配。

解答:

  1. [:压栈 [
  2. (:压栈 (
  3. ]:栈顶是 (,不匹配,匹配失败

结果是匹配失败。

这篇关于【408考点之数据结构】表达式求值和括号匹配的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

二分最大匹配总结

HDU 2444  黑白染色 ,二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible