递归算法实例应用(二)

简介: 递归算法实例应用(二):Polish Expression问题

Polish Expression

Description

A Polish expression is an arithmetic expression that prepositions an operator. For example, the Polish representation of the ordinary expression 2 + 3 is + 2 3. The advantage of Polish expressions is that there is no need for precedence between operators, nor for parentheses to change the order of operations. For example, the Polish representation of (2 + 3) * 4 is * + 2 3 4. This problem evaluates the value of the Polish expression, where the operators include ‘+’,‘-’,‘*’,‘/’.

Input

The input is a line with Spaces separating both the operator and the operand, which is a floating-point number.

Output

The output is a line, the value of the expression.

Sample Input

* + 11.0 12.0 + 24.0 35.0

Sample Output

1357.000000

关于前缀表达式,又称波兰表达式,它是一种不需要括号的计算表达式的表示法。它将操作符号写在操作数之前,即二元运算符总是置于与之相关的两个运算对象之前,而每一个对象也可以是一个波兰表达式,因此波兰式是一个明显的以递归形式定义的问题。所以我们可以采用递归的方式进行解决。

同时,在数据结构栈相关章节,也有更为详细的阐述,主要是通过栈的方法将我们所熟知的中缀表达式转为后缀表达式(逆波兰表达式)或前缀表达式(波兰表达式),因为在计算机中通过前缀、后缀表达式相比于中缀表达式有着更广、更深的用途,只需入栈和出栈就可以搞定任何普通中缀表达式的运算。简言之为:如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。具体通过栈来模拟算法转换在此不加阐述,本文属递归篇,所以通过递归形式来解决问题。


算法思想:

当仅通过递归来实现时,相比于栈操作问题会变得更加简单。

所以,我们从波兰式的定义出发:

  1. 一个数是一个波兰表达式,值为数本身。
  2. “运算符” “波兰表达式1” “波兰表达式2” 是一个波兰表达式,值为波兰表达式1 运算符 波兰表达式2的值。

发现该定义本身是一个以递归形式来定义的,如2中,在定义波兰式时又用到了波兰式的概念,所以波兰式是一个以递归形式定义的问题。

而在1中,该条定义是明确的一条定义,并没有递归的定义形式出现。

波兰式的递归形式之所以成立,是因为1中这条非递归形式的定义在约束,作为递归的终止条件。也就是说,因为1中定义的存在使得2中的定义不存在无限循环定义的形式,使得波兰式的递归形式成立。

当对于波兰式的递归定义形式清楚以后问题就迎刃而解。

由于C/C++语言具有输入/输出缓冲区的特性,所以可以在程序等待输入时一次性将待输入字符串输入完整。


代码逻辑:

  1. 依次读入每一个字符串
  2. 判断字符串类型:

    • 若该字符串为‘+’,则后两个字符串应该为波兰式1和波兰式2,并对两波兰式做加法运算,其值作为返回值。
    • 若该字符串为‘-’,则后两个字符串应该为波兰式1和波兰式2,并对两波兰式做减法运算,其值作为返回值。
    • 若该字符串为‘*’,则后两个字符串应该为波兰式1和波兰式2,并对两波兰式做乘法运算,其值作为返回值。
    • 若该字符串为‘/’,则后两个字符串应该为波兰式1和波兰式2,并对两波兰式做除法运算,其值作为返回值。
    • 若该字符串为数字,则根据定义1可知,改波兰式的值为该值本身,所以返回该字符串对应的双浮点数类型即可,可通过stdlib.h头文件中atof()函数进行转换。
  3. 输出波兰式的值

代码整合:

double PolishExp() {
    char str[20];
    scanf("%s", str);
    switch (str[0]) {
        case '+':
            return PolishExp() + PolishExp(); // +ab -> a+b
        case '-':
            return PolishExp() - PolishExp(); // -ab -> a-b
        case '*':
            return PolishExp() * PolishExp(); // *ab -> a*b
        case '/':
            return PolishExp() / PolishExp(); // /ab -> a/b
        default:
            return atof(str); //将字符串转为双浮点数类型
    }
}

By Ss1Two 2023/01/14

目录
相关文章
|
2月前
|
存储 监控 JavaScript
基于布隆过滤器的 Node.js 算法在局域网电脑桌面监控设备快速校验中的应用研究
本文探讨了布隆过滤器在局域网电脑桌面监控中的应用,分析其高效空间利用率、快速查询性能及动态扩容优势,并设计了基于MAC地址的校验模型,提供Node.js实现代码,适用于设备准入控制与重复数据过滤场景。
77 0
|
8天前
|
运维 监控 JavaScript
基于 Node.js 图结构的局域网设备拓扑分析算法在局域网内监控软件中的应用研究
本文探讨图结构在局域网监控系统中的应用,通过Node.js实现设备拓扑建模、路径分析与故障定位,提升网络可视化、可追溯性与运维效率,结合模拟实验验证其高效性与准确性。
65 3
|
19天前
|
机器学习/深度学习 资源调度 算法
遗传算法模型深度解析与实战应用
摘要 遗传算法(GA)作为一种受生物进化启发的优化算法,在复杂问题求解中展现出独特优势。本文系统介绍了GA的核心理论、实现细节和应用经验。算法通过模拟自然选择机制,利用选择、交叉、变异三大操作在解空间中进行全局搜索。与梯度下降等传统方法相比,GA不依赖目标函数的连续性或可微性,特别适合处理离散优化、多目标优化等复杂问题。文中详细阐述了染色体编码、适应度函数设计、遗传操作实现等关键技术,并提供了Python代码实现示例。实践表明,GA的成功应用关键在于平衡探索与开发,通过精心调参维持种群多样性同时确保收敛效率
|
19天前
|
机器学习/深度学习 边缘计算 人工智能
粒子群算法模型深度解析与实战应用
蒋星熠Jaxonic是一位深耕智能优化算法领域多年的技术探索者,专注于粒子群优化(PSO)算法的研究与应用。他深入剖析了PSO的数学模型、核心公式及实现方法,并通过大量实践验证了其在神经网络优化、工程设计等复杂问题上的卓越性能。本文全面展示了PSO的理论基础、改进策略与前沿发展方向,为读者提供了一份详尽的技术指南。
粒子群算法模型深度解析与实战应用
|
19天前
|
机器学习/深度学习 算法 安全
小场景大市场:猫狗识别算法在宠物智能设备中的应用
将猫狗识别算法应用于宠物智能设备,是AIoT领域的重要垂直场景。本文从核心技术、应用场景、挑战与趋势四个方面,全面解析这一融合算法、硬件与用户体验的系统工程。
|
3月前
|
机器学习/深度学习 人工智能 算法
AI-Compass 强化学习模块:理论到实战完整RL技术生态,涵盖10+主流框架、多智能体算法、游戏AI与金融量化应用
AI-Compass 强化学习模块:理论到实战完整RL技术生态,涵盖10+主流框架、多智能体算法、游戏AI与金融量化应用
|
3月前
|
机器学习/深度学习 人工智能 自然语言处理
深度学习模型、算法与应用的全方位解析
深度学习,作为人工智能(AI)的一个重要分支,已经在多个领域产生了革命性的影响。从图像识别到自然语言处理,从语音识别到自动驾驶,深度学习无处不在。本篇博客将深入探讨深度学习的模型、算法及其在各个领域的应用。
484 3
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
76 1
|
2月前
|
算法 数据可视化
matlab版本粒子群算法(PSO)在路径规划中的应用
matlab版本粒子群算法(PSO)在路径规划中的应用
|
3月前
|
存储 监控 算法
公司员工泄密防护体系中跳表数据结构及其 Go 语言算法的应用研究
在数字化办公中,企业面临员工泄密风险。本文探讨使用跳表(Skip List)数据结构优化泄密防护系统,提升敏感数据监测效率。跳表以其高效的动态数据处理能力,为企业信息安全管理提供了可靠技术支持。
59 0

热门文章

最新文章