热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

表达式转换——中缀表达式转换为后缀表达式

表达式转换算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后

表达式转换

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:
输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。

输出格式:
在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。

输入样例:

2+3*(7-4)+8/4

输出样例:

2 3 7 4 - * + 8 4 / +

知识点:将中缀表达式转化为后缀表达式:
两种情况:
(1)没有括号的中缀表达式转化为后缀表达式:

没有括号的中缀表达式转化为后缀表达式
(2)带有括号的中缀表达式转化为后缀表达式:

带有括号的中缀表达式转化为后缀表达式
分析:本题是带有括号的中缀表达式,需要利用第二种方式实现,模拟过程我会在代码上详解
这里说一下这道题的细节问题:
中缀表达式转换为后缀表达式:对于本题而言,细节过多,在完成表达式转换的基础上
1.需要控制空格,首尾不能出现空格
2.需要判断一位以上的数字之间不能有空格
3.需要判断小数的情况,注意之间不能有空格
4.需要判断镶嵌括号的情况,容易出现格式错误
例如:当一开始就输入多个空格会使首位出现空格
5.需要判断正负号
(1)对于正号,当出现在第一位时需直接特判(在第一位无需加括号)
未在第一位出现正号一定会在括号内,而且输出时正号要省略
(2)对于负号,当出现在第一位时需要直接特判(在第一位出现无需加括号)
未在第一位出现负号一定会在括号内,需要输出负号
(3)注意控制好空格,防止格式错误

下面是代码:


#include
#include
#include
#include
#include
using namespace std;
const int M=1010;
char str[M],st[M],c;
stack<char> q;
int main()
{int i,j,k&#61;0,l,m,n,f&#61;0,t&#61;0,ff&#61;0;cin.getline(str,110);l&#61;strlen(str);for(i&#61;0; i<l; i&#43;&#43;){if(str[i]>&#61;&#39;0&#39;&&str[i]<&#61;&#39;9&#39;)///为数字时输出{t&#61;1;///标记已经出现过数字///解决当有镶嵌括号时的格式问题if(ff&#61;&#61;0)///特判当刚开始有镶嵌括号时防止f&#61;1对格式的影响{printf("%c",str[i]);ff&#61;1;f&#61;0;continue;}///解决超过一位数的问题if(f&#61;&#61;0)///遇到数字并且前一个也是数字或&#39;.&#39;输出printf("%c",str[i]);else ///f&#61;1时遇到数字加空格输出&#xff0c;并使f&#61;0{printf(" %c",str[i]);f&#61;0;}}///解决小数问题else if(str[i]&#61;&#61;&#39;.&#39;)///遇到点说明为小数直接输出{printf("%c",str[i]);}///解决第一位为正数带&#39;&#43;&#39;的问题else if(i&#61;&#61;0&&str[i]&#61;&#61;&#39;&#43;&#39;){printf("%c",str[i]);}///解决第一位为正数带&#39;-&#39;的问题else if(i&#61;&#61;0&&str[i]&#61;&#61;&#39;-&#39;){printf("%c",str[i]);}///解决非第一位为正数带&#39;-&#39;的问题else if(str[i]&#61;&#61;&#39;(&#39;&&str[i&#43;1]&#61;&#61;&#39;-&#39;){///输出符号if(t&#61;&#61;1)///若已经出现数字&#xff0c;加符号时需在前面加空格printf(" %c",str[i&#43;1]);elseprintf("%c",str[i&#43;1]);q.push(str[i]);///将括号入栈f&#61;0;///输出数字无需加空格i&#43;&#43;;///跳过这个&#39;-&#39;}///解决非第一位为正数带&#39;&#43;&#39;的问题else if(str[i]&#61;&#61;&#39;(&#39;&&str[i&#43;1]&#61;&#61;&#39;&#43;&#39;){///带正号的数字的正号可以约去q.push(str[i]);///将括号入栈f&#61;1;///输入数字时需要加空格i&#43;&#43;;///跳过&#39;&#43;&#39;}///当遇见左括号else if(str[i]&#61;&#61;&#39;(&#39;){q.push(str[i]);///放入栈中f&#61;1;}///遇见右括号else if(str[i]&#61;&#61;&#39;)&#39;){///输出左括号到右括号之间的符号while(q.top()!&#61;&#39;(&#39;){printf(" %c",q.top());f&#61;1;///当输入数字时需加空格q.pop();///将输出的字符出栈}//printf("%c\n",q.top());q.pop();///将左括号出栈}else{///当栈为空或者栈顶元素为左括号if(q.size()&#61;&#61;0||q.top()&#61;&#61;&#39;(&#39;){f&#61;1;///输入数字时需要加空格q.push(str[i]);///将符号放入栈中}///当需要入栈的符号优先级大于栈顶符号优先级else if((str[i]&#61;&#61;&#39;*&#39;||str[i]&#61;&#61;&#39;/&#39;)&&(q.top()&#61;&#61;&#39;&#43;&#39;||q.top()&#61;&#61;&#39;-&#39;)){f&#61;1;///输入数字时需加括号q.push(str[i]);///将符号入栈}///入栈的符号优先级小于或等于栈顶符号优先级///栈中元素不为空且栈顶元素不是左括号else{///当栈顶元素为&#39;*&#39;或&#39;/&#39;if(q.top()&#61;&#61;&#39;*&#39;||q.top()&#61;&#61;&#39;/&#39;){f&#61;1;///输入数字需加空格printf(" %c",q.top());///加空格输出栈顶元素q.pop();///将栈顶元素出栈///出栈完看栈中元素是否为空///此时四种情况///&#xff08;1&#xff09;栈中元素为0///&#xff08;2&#xff09;栈顶元素为&#39;(&#39;///&#xff08;3&#xff09;栈底元素为&#39;&#43;&#39;或&#39;-&#39;&#xff0c;输入符号为&#39;*&#39;或&#39;/&#39;///&#xff08;4&#xff09;栈底元素为&#39;&#43;&#39;或&#39;-&#39;&#xff0c;输入符号为&#39;&#43;&#39;或&#39;-&#39;///情况一和情况二if(q.size()&#61;&#61;0||q.top()&#61;&#61;&#39;(&#39;){f&#61;1;///输出数字时需加空格q.push(str[i]);///将符号放入栈中}///情况三else if(str[i]&#61;&#61;&#39;*&#39;||str[i]&#61;&#61;&#39;/&#39;){f&#61;1;///输出数字时需加空格q.push(str[i]);///直接将符号入栈}///情况四else if(str[i]&#61;&#61;&#39;&#43;&#39;||str[i]&#61;&#61;&#39;-&#39;){f&#61;1;///输出数字时需加空格printf(" %c",q.top());///将栈顶元素加空格输出q.pop();///栈顶元素出栈q.push(str[i]);///将符号放入栈中}}///当栈顶元素为&#39;&#43;&#39;或&#39;-&#39;else if(q.top()&#61;&#61;&#39;&#43;&#39;||q.top()&#61;&#61;&#39;-&#39;){///两种情况///&#xff08;1&#xff09;入栈符号为&#39;*&#39;或&#39;/&#39;///&#xff08;2&#xff09;入栈符号为&#39;&#43;&#39;或&#39;-&#39;///情况一if(str[i]&#61;&#61;&#39;*&#39;||str[i]&#61;&#61;&#39;/&#39;){f&#61;1;///输出数字时需加空格q.push(str[i]);///将符号放入栈中}else if(str[i]&#61;&#61;&#39;&#43;&#39;||str[i]&#61;&#61;&#39;-&#39;){f&#61;1;///输出数字时需加空格printf(" %c",q.top());///输出栈顶元素q.pop();///栈顶元素出栈q.push(str[i]);///将符号放入栈中}}}}}///当栈中符号未完全出栈while(q.size()!&#61;0){printf(" %c",q.top());///将栈中符号依次输出q.pop();///依次出栈}printf("\n");return 0;
}

推荐阅读
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本文详细介绍了如何构建一个高效的UI管理系统,集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑,实现功能逻辑分散化和代码复用,支持多人协作开发。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本文探讨了 Objective-C 中的一些重要语法特性,包括 goto 语句、块(block)的使用、访问修饰符以及属性管理等。通过实例代码和详细解释,帮助开发者更好地理解和应用这些特性。 ... [详细]
  • 本文详细介绍了 Apache Jena 库中的 Txn.executeWrite 方法,通过多个实际代码示例展示了其在不同场景下的应用,帮助开发者更好地理解和使用该方法。 ... [详细]
  • 本文详细介绍了Java中的访问器(getter)和修改器(setter),探讨了它们在保护数据完整性、增强代码可维护性方面的重要作用。通过具体示例,展示了如何正确使用这些方法来控制类属性的访问和更新。 ... [详细]
  • 主要用了2个类来实现的,话不多说,直接看运行结果,然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 深入解析Spring Cloud Ribbon负载均衡机制
    本文详细介绍了Spring Cloud中的Ribbon组件如何实现服务调用的负载均衡。通过分析其工作原理、源码结构及配置方式,帮助读者理解Ribbon在分布式系统中的重要作用。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • MQTT技术周报:硬件连接与协议解析
    本周开发笔记重点介绍了在新项目中使用MQTT协议进行硬件连接的技术细节,涵盖其特性、原理及实现步骤。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文介绍如何使用 NSTimer 实现倒计时功能,详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器,确保在指定时间间隔内执行特定任务。 ... [详细]
author-avatar
阳光下微醺的我
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有