03-3.3.2_1 栈在表达式求值中的应用(上)

2024-06-09 06:36
文章标签 应用 求值 表达式 03 3.3

本文主要是介绍03-3.3.2_1 栈在表达式求值中的应用(上),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • 👋 Hi, I’m @Beast Cheng
  • 👀 I’m interested in photography, hiking, landscape…
  • 🌱 I’m currently learning python, javascript, kotlin…
  • 📫 How to reach me --> 458290771@qq.com

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏,今后还会不断更新。🧑‍💻
此外,《程序员必备技能》专栏和《程序员必备工具》专栏(该专栏暂未开设)日后会逐步更新,感兴趣的小伙伴可以点一下订阅、收藏、关注!🚀
谢谢大家!🙏

引言

大家熟悉的算数表达式

( ( 15 ÷ ( 7 − ( 1 + 1 ) ) ) × 3 ) − ( 2 + ( 1 + 1 ) ) ((15÷(7-(1+1)))×3)-(2+(1+1)) ((15÷(7(1+1)))×3)(2+(1+1))
在我们熟悉的算数表达式中,由三个部分组成:

  1. 操作数:如1, 2, 3, 4, 5这些
  2. 运算符:如加减乘除这些
  3. 界限符:如括号

波兰数学家的灵感

灵感:可以不用界限符也能无歧义地表达运算顺序
Reverse Polish notation(逆波兰表达式 = 后缀表达式)
Polish notation(波兰表达式 = 前缀表达式)

三种算数表达式

(1)中缀表达式

运算符在两个操作数中间:
a + b a + b a+b
a + b − c a+b-c a+bc
a + b − c ∗ d a+b-c*d a+bcd

(2)后缀表达式

运算符在两个操作数后面:
a b + a b + ab+
a b + c − ab+c- ab+c 或者也可以先算 b − c b-c bc,那么结果就是: a b c − + abc-+ abc+
a b + c d ∗ − ab+cd*- ab+cd
要注意操作数的左右顺序

(3)前缀表达式

运算符在两个操作数的前面:
+ a b + a b +ab
− + a b c -+abc +abc,类似的,也可以写成别的形式
− + a b ∗ c d -+ab*cd +abcd

后缀表达式相关考点

(1)中缀表达式转后缀表达式

中缀转后缀的手算方法

  1. 确定中缀表达式中各个运算符的运算顺序
  2. 选择下一个运算符,按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数
  3. 如果还有运算符没有被处理,就继续执行步骤 2
    根据以上步骤,在引言中的算数表达式: ( ( 15 ÷ ( 7 − ( 1 + 1 ) ) ) × 3 ) − ( 2 + ( 1 + 1 ) ) ((15÷(7-(1+1)))×3)-(2+(1+1)) ((15÷(7(1+1)))×3)(2+(1+1))
    就可以写成: ( 3 ( 15 ( 7 ( 11 + ) − ) ÷ ) × ) ( 2 ( 11 + ) + ) − (3(15(7(11+)-)÷)×)(2(11+)+)- (3(15(7(11+))÷)×)(2(11+)+)

上面算数表达式中的括号应该是去掉的
加在上面是为了便于理解
括号中的 11+,不是 11,而是两个 1

再举一个例子: A + B × ( C − D ) − E ÷ F A+B×(C-D)-E÷F A+B×(CD)E÷F
转换为后缀表达式就应该是: A B C D − × + E F ÷ − ABCD-×+EF÷- ABCD×+EF÷

运算顺序不唯一
因此对应的后缀表达式也不唯一

练习:写出 A + B × ( C − D ) − E ÷ F A+B×(C-D)-E÷F A+B×(CD)E÷F 的另一种后缀表达式形式
答案: A B C D − × E F ÷ − + ABCD-×EF÷-+ ABCD×EF÷+

客观来说,两种形式都是正确的
只是“机算”的结果是前者

那么如何才能写出更精确的后缀表达式呢?
使用 “左优先原则”:只要左边的运算符能够先运算,就先计算左边的
这样可以保证运算顺序唯一
举例: A + B − C × D ÷ E + F A+B-C×D÷E+F A+BC×D÷E+F
转换后结果: A B + C D × E ÷ − F + AB+CD×E÷-F+ AB+CD×E÷F+

(2)后缀表达式求值

后缀表达式的手算方法
从左往右扫描,每遇到一个运算符,就让运算符前面最近的两个操作数执行对应运算,合体为一个操作数
注意:两个操作数的运算顺序

用计算机机算后缀表达式

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

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

需要注意的是:先出栈的是右操作数
若表达式合法,则最后栈中只会留下一个元素,也就是最终结果

具体代码实现

#include <stdio.h> 
#include <stdlib.h> 
#include <ctype.h> 
#include <string.h> #define MAX 100 // 定义栈的最大长度 typedef struct {int data[MAX]; int top; 
} IntStack; // 初始化整数栈 
void InitIntStack(IntStack *S) {S->top = -1; 
} // 判断整数栈是否为空 
int IntStackEmpty(IntStack S) {return S.top == -1; 
} // 整数元素入栈 
void IntPush(IntStack *S, int x) {S->data[++S->top] = x; 
} // 整数元素出栈 
int IntPop(IntStack *S) {if (IntStackEmpty(*S)) {return 0; // 栈空返回0 } return S->data[S->top--]; 
} // 计算后缀表达式的值 
int evaluatePostfix(const char* postfix) {IntStack S;InitIntStack(&S); int i = 0, num1, num2, result; char ch; while ((ch = postfix[i++]) != '\0') {if (isdigit(ch)) { int num = 0; while (isdigit(ch)) { num = num * 10 + (ch - '0'); ch = postfix[i++]; } IntPush(&S, num); } else if (ch == ' ') { continue; // 忽略空格 } else { num2 = IntPop(&S); num1 = IntPop(&S); switch (ch) { case '+': result = num1 + num2; break; case '-': result = num1 - num2; break; case '*': result = num1 * num2; break; case '/': result = num1 / num2; break; } IntPush(&S, result); } } return IntPop(&S); 
} int main() { // 给定的后缀表达式 const char postfix[] = "15 7 1 1 + - / 3 * 2 1 1 + + -";int result = evaluatePostfix(postfix); printf("计算结果: %d\n", result); return 0; 
}

代码解释

  • const char* postfix 的意思?
    • const 表示这个字符串指针指向的数据(字符串)是不可变的,即你不能通过这个指针修改字符串的内容。
    • char* 表示这个指针指向的是一个字符(char)数组(或者说是一个 C 风格的字符串)。
    • postfix 是这个指针的变量名。
  • 哪里来的 isdigit 函数?
    • isdigit 是 C 标准库函数,定义在 <ctype.h> 头文件中。
      • 这个函数接受一个字符作为参数,判断是否是数字字符(‘0’-‘9’)
      • 如果是数字字符,返回非零值(通常为1),否则返回0
  • num = num * 10 + (ch - '0'); 是什么意思?
    • 这行代码用于将连续的字符数字转换成一个整数。考虑例子,同一个位置的ch是一个数字字符:
      • ch - '0' 将字符数字转换为对应的整数值。例如,‘4’ - ‘0’ 将得到整数 4。
      • num * 10 表示将之前的数向左移动一个十进制位,以便新的数字字符可以追加到末位。
      • 然后加上新的数字,这样可以将多位字符数字连接成一个完整的整数
      • 例如,处理字符串 “123”:
        • '1' - '0' = 1num = 0 * 10 + 1 => num = 1
        • '2' - '0' = 2num = 1 * 10 + 2 => num = 12
        • '3' - '0' = 3num = 12 * 10 + 3 => num = 123
  • ch = postfix[i++]; 是什么意思?
    • ch = postfix[i++]; 用来从字符串 postfix 中依次取得字符,并存储到 ch 变量中
      • postfix[i] 是字符串 postfix 的第 i 个字符
      • ch = postfix[i] 表示将这个字符赋值给变量 ch
      • i++ 是一个后缀自增操作,表示先使用 i 的当前值,然后再将 i 增加 1,以备下次使用

前缀表达式相关考点

(1)中缀表达式转前缀表达式

与中缀转后缀类似,不再过多赘述

(2)前缀表达式求值

手算

中缀转前缀手算方法

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

在这里使用的是右优先原则
只要右边的运算符能先计算,就先算右边

机算

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

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

注意:先出栈的是左操作数

知识回顾与重要考点

表达式求值问题

  • 概念:运算符、操作符、界限符(DIY概念:左操作数、右操作数)
  • 三种表达式
    • 中缀表达式:运算符在操作数中间
    • 后缀表达式(逆波兰式):运算符在操作数后面
    • 前缀表达式(波兰式):运算符在操作数前面
  • 后缀表达式考点
    • 中缀转后缀
      • 按左优先原则确定运算符的运算顺序
      • 根据确定的顺序,依次将各个运算符和与之相邻的两个操作数按规则合体
    • 后缀转中缀
      • 从左往右扫描,每遇到一个运算符,就按规则解体
    • 计算
      • 从左往右扫描,遇到操作数就入栈,遇到运算符则弹出两个栈顶元素运算后入栈(先弹出的是右操作数)
  • 前缀表达式
    • 中缀转前缀
      • 按右优先原则确定运算次序
      • 根据确定的次序,依次按规则合体
    • 计算
      • 从右往左扫描,遇到操作数入栈,遇到运算符就弹出两个栈顶元素运算后入栈(先弹出的是左操作数)

这篇关于03-3.3.2_1 栈在表达式求值中的应用(上)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

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

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

zoj3820(树的直径的应用)

题意:在一颗树上找两个点,使得所有点到选择与其更近的一个点的距离的最大值最小。 思路:如果是选择一个点的话,那么点就是直径的中点。现在考虑两个点的情况,先求树的直径,再把直径最中间的边去掉,再求剩下的两个子树中直径的中点。 代码如下: #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#

06 C++Lambda表达式

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

【区块链 + 人才服务】可信教育区块链治理系统 | FISCO BCOS应用案例

伴随着区块链技术的不断完善,其在教育信息化中的应用也在持续发展。利用区块链数据共识、不可篡改的特性, 将与教育相关的数据要素在区块链上进行存证确权,在确保数据可信的前提下,促进教育的公平、透明、开放,为教育教学质量提升赋能,实现教育数据的安全共享、高等教育体系的智慧治理。 可信教育区块链治理系统的顶层治理架构由教育部、高校、企业、学生等多方角色共同参与建设、维护,支撑教育资源共享、教学质量评估、

AI行业应用(不定期更新)

ChatPDF 可以让你上传一个 PDF 文件,然后针对这个 PDF 进行小结和提问。你可以把各种各样你要研究的分析报告交给它,快速获取到想要知道的信息。https://www.chatpdf.com/