热门标签 | 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;
}

推荐阅读
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 深入解析Spring Cloud Ribbon负载均衡机制
    本文详细介绍了Spring Cloud中的Ribbon组件如何实现服务调用的负载均衡。通过分析其工作原理、源码结构及配置方式,帮助读者理解Ribbon在分布式系统中的重要作用。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 本文详细介绍了Java中org.neo4j.helpers.collection.Iterators.single()方法的功能、使用场景及代码示例,帮助开发者更好地理解和应用该方法。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 本文详细介绍了Akka中的BackoffSupervisor机制,探讨其在处理持久化失败和Actor重启时的应用。通过具体示例,展示了如何配置和使用BackoffSupervisor以实现更细粒度的异常处理。 ... [详细]
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社区 版权所有