首页 > 其他分享 >7-20 表达式转换 预习报告

7-20 表达式转换 预习报告

时间:2024-11-28 19:30:28浏览次数:7  
标签:20 中缀 预习 运算符 算法 转换 解析 表达式

1、问题定义

表达式转换

2、问题分析

这道题目显然用到了栈这一数据结构,栈的特点是元素的先进后出,与题目的要求中的将中缀表示法转换为后缀表示法有相似的地方。

任务中要求将输入的中缀表达式转换为后缀表达式,即为给定一个用中缀表示法表示的算术表达式,转换为用后缀表示法表示的算术表达式。根据数据结构课程所学知识,可以使用 Shunting Yard 算法、递归下降解析和逆波兰转换算法等来实现。这些算法的不同点在于算法的灵活性、高效性和支持符号等方面,本题目均可采用。

算法介绍:

一、 Shunting Yard 算法

简介
Shunting Yard 算法是由 Edsger Dijkstra 提出的,主要用于将中缀表达式转换为后缀表达式(逆波兰表示法)。该算法使用两个栈,一个用于存放运算符,另一个用于存放输出结果。

主要特点

  • 简单易懂:算法逻辑清晰,容易理解和实现。
  • 高效:时间复杂度为 O(n),其中 n 是表达式的长度。
  • 支持括号:能够正确处理包含括号的表达式。
  • 动态性:可以在解析过程中动态处理运算符的优先级。

适用场景

  • 适用于大多数中缀表达式转换任务,特别是教育和简单的应用开发。

二. 递归下降解析

简介
递归下降解析是一种自上而下的解析技术,通过递归调用函数来解析表达式。这种方法适用于简单的语法解析,尤其是中缀表达式。

主要特点

  • 灵活性高:可以处理复杂的语法结构,如嵌套表达式和多种运算符。
  • 代码清晰:通过递归函数实现,代码结构清晰,易于维护。
  • 静态性:需要预先定义好每个语法结构的解析函数。

适用场景

  • 适用于需要处理复杂语法结构的场景,如编译器和解释器的前端部分。

3. 逆波兰转换算法

简介
逆波兰转换算法也是一种直接将中缀表达式转换为后缀表达式的算法。它通过使用栈来管理运算符的优先级和括号的匹配。

主要特点

  • 逻辑清晰:算法步骤明确,容易理解和实现。
  • 支持括号:能够正确处理包含括号的表达式。
  • 动态性:可以在解析过程中动态处理运算符的优先级。

适用场景

  • 适用于大多数中缀表达式转换任务,与 Shunting Yard 算法类似,但可能在某些细节上有所不同。

3、概要设计

数据结构设计

(1)、Token 结构体:用于表示表达式中的每个元素(运算数或运算符)。

struct Token {
string value;
bool isOperator; 
};

(2)、Stack 类:用于实现栈操作。

#include <stack> 
#include <string> 
#include <vector> 
class Stack { 
private: 
stack<string> elements; 
//使用 Stack 容器存储元素
public: 
//将元素压入栈顶
void push(const string& element) { 
    elements.push(element); 
} 
//从栈顶弹出元素
string pop() {  
    if (isEmpty()) {  //检查栈是否为空
        throw runtime_error("Stack is empty"); 
    } 
    string topElement = elements.top();  //获取栈顶元素
    elements.pop(); //弹出栈顶元素
    return topElement; //返回栈顶元素
} 
bool isEmpty() const {  //检查栈是否为空
    return elements.empty(); //返回栈是否为空的状态
} 
string peek() const { 
    if (isEmpty()) {  //检查栈是否为空
        throw runtime_error("Stack is empty"); 
    } 
    return elements.top(); //返回栈顶元素
} 
};

标签:20,中缀,预习,运算符,算法,转换,解析,表达式
From: https://blog.csdn.net/2302_79121713/article/details/144118797

相关文章

  • 2024.11.20训练记录
    pack设当前手上的钱数为x。二分一段一段跳的复杂度是对的。因为,如果下一段的代价总和sum<\dfrac{x}{2}。那么这一段的下一个数肯定也小于\dfrac{x}{2}。因为是从大到小排。所以还能继续选下一个数,引出矛盾。所以每段的代价总和只能大于\dfrac{x}{2}。那段数就是log级别的。......
  • 力控组态实现延时5s延时触发,命令间隔200ms
    最近做一个阀门开度随液位变化的程序,液位设定一个目标值,液位高于目标值,阀门开度减小;液位低于目标值,阀门开度增加。很明显,该程序适合用PID控制,在大循环中计算阀门开度值,并下置给阀门,结果,设备经常离线原因:经分析,大循环中运行,数据下置太快,设备反应不过来,导致通讯超时,或者是撞......
  • 「杂题乱刷2」CF2038B
    题目链接CF2038BMakeItEqual题意简述这东西好久没写了啊。阿瓦在一个幻想王国里。他走在草坪上,发现有\(n\)个数字精灵祝他生日快乐。阿瓦非常开心。因为最多可能会有\(2\times10^5\)个精灵为他庆生。但是,对于每个数字精灵都有一个饱食度\(a_i\),如果有任意两个数......
  • [2096]基于JAVA的混凝土供应链智慧管理系统的设计与实现
    毕业设计(论文)开题报告表姓名学院专业班级题目基于JAVA的混凝土供应链智慧管理系统的设计与实现指导老师(一)选题的背景和意义背景部分:在当今信息化高速发展的时代背景下,随着我国基础设施建设规模不断扩大,混凝土作为建筑行业不可或缺的基础材料,其供应链管理面临着巨大的......
  • [2093]基于JAVA的涉诉资产智慧管理系统的设计与实现
    毕业设计(论文)开题报告表姓名学院专业班级题目基于JAVA的涉诉资产智慧管理系统的设计与实现指导老师(一)选题的背景和意义选题背景:随着我国法治建设的不断深入和司法体系的日益完善,涉诉资产作为诉讼活动中的重要组成部分,其管理效率与公正性直接影响着司法工作的质量和效......
  • 20222407 2024-2025-1 《网络与系统攻防技术》实验五实验报告
    1.实验内容1.1本周内容总结使用了Metasploit框架,其是一个功能强大的渗透测试框架。在使用的过程当中,Metasploit提供了种类繁多的攻击模块,涵盖了远程代码执行、服务拒绝、提权等多种攻击方式,支持对多种操作系统和应用程序进行测试。除了漏洞利用,它还具备强大的后渗透功能,如键......
  • noip2024 复习计划
    大致分三步:基本模板、套路复习套题复盘再刷一两道码力题基本模板复习有(参照csp2024套题复盘表):1.数据结构平衡树线段树、树状数组的Trick2.杂算法CDQ分治、整体二分、点分治、点分树KMP(其实不用复习了)3.图论Dijkstra板子,以及最小生成树......
  • 20222404 2024-2025-1 《网络与系统攻防技术》实验五实验报告
    1.实验内容总结一下本周学习内容了解了信息搜集在网络攻防中的重要性,认识不同的信息搜集方法如WHOIS查询、DNS查询(dig、nslookup等)了解一些查询工具:dig工具、nslookup基于网络的信息搜集可以使用nmap,可使用端口、SYN、UDP等不通类型扫描。2.实验过程2.1获取baidu.com如......
  • 2022 年 12 月大学英语四级考试真题(第一套)知识点总结
    1.作文Inthistask,youaretowriteanessaystudentsonthenecessityofdevelopingsocialskillsforcollege.Youwillhave30minutesforthetask.Youshouldwriteatleast120180wordsbutnomorethanwords.【分析】这是一篇议论文,要求论述培养大学......
  • Windows Server 2016如何关闭和打开防火墙 | 详细教程
    WindowsServer2016如何关闭和打开防火墙在WindowsServer2016中,防火墙是保护服务器安全的重要工具。但有时候,我们可能需要临时关闭或重新打开防火墙。本文将为您详细介绍如何在WindowsServer2016中操作防火墙。使用图形界面操作防火墙图形界面操作简单直观,适合不熟悉命令......