中缀转后缀表达式

思路分析

  • 遇到数字,直接输出
  • 遇到符号
    • 栈为空,符号直接入栈
    • 若为 ( ,则直接入栈
    • 用当前符号和栈顶符号比较优先级
      • 当前符号 > 栈顶符号,当前符号直接入栈,结束
      • 当前符号 <= 栈顶符号,栈顶符号出栈并输出,继续比较
        • 把栈中符号弹空
        • 遇到 ) ,要一直出栈,直到遇见 ) 为止
例子1:

中缀表达式:(1 + 2) * (3 + 4)

后缀表达式:12 + 34 + *

符号入栈情况图(从上到下,从左往右看):

在这里插入图片描述

例子2:

中缀表达式:2 + (4 + 6)/2 + 6 / 3

后缀表达式:2 4 6 + 2 / + 6 3

代码

// 中缀转后缀表达式
// 2024年03月31日10:57:06
#include <iostream>
#include <string>
#include <stack>
using namespace std;

bool Priority(char ch, char topch)
{
    // ch优先级大的情况:
    if((ch == '*' || ch == '/') && (topch == '+' || topch == '-')) return true;

    // 栈顶的 ( 优先级小于任何其他符号(除了 ))
    if(topch == '(' && ch != ')')  return true;

    return false;
}

string MiddleToPostExpr(string expr)
{
    string res;
    stack<char> s;

    for(char ch : expr)
    {
        if(ch >= '0' && ch <= '9')
        {
            res.push_back(ch);
        }
        else 
        {
            for(;;) // 用于处理可能得多次出栈(遇到 ), 或优先级不同)
            {
                // 栈空 或 遇到 ( ,直接入栈
                if(s.empty() || ch == '(')
                {
                    s.push(ch);
                    break;
                }
                // 比较当前符号ch和栈顶符号top
                char topch = s.top();
                // true if ch > topch
                if(Priority(ch, topch)) // 当面符号优先级大于栈顶符号,入栈
                {
                    s.push(ch);
                    break;
                }
                else /// 不断出栈的情况
                {
                    s.pop();
                    if(topch == '(') // 遇见 ),一直出栈直到 (
                        break;
                    res.push_back(topch);
                }
            }
        }
    }
    while(!s.empty()) // 栈还留存符号,直接输出到后缀表达式中
    {
        res.push_back(s.top());
        s.pop();
    }
    return res;
}

int main()
{
    cout << MiddleToPostExpr("(1+2)*(3+4)") << endl;
    // cout << MiddleToPostExpr("2+(4+6)/2+6/3") << endl;
    return 0;
}
执行结果
[root@centos01 stack]# g++ mid_to_post.cpp 
[root@centos01 stack]# ./a.out 
12+34+*

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/505581.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

verilog中的testbench语句——display,fopen,fread,fwrite——更新中

一、fopen bmp_file_read $fopen("../pic/picture.bmp","rb"); 要注意这类操作文件的函数&#xff0c;在vivado2018自带的仿真软件里&#xff0c;不综合直接仿真&#xff0c;它的当前文件夹如图所示。 一、fwrite $fwrite(bmp_file_write,"%c"…

【Effective Web】页面优化

页面优化 页面渲染流程 JavaScript 》 Style 》 Layout 》 Paint 》 Composite 首先js做了一些逻辑&#xff0c;触发了样式变化&#xff0c;style计算好这些变化后&#xff0c;把影响的dom元素进行重新布局&#xff08;layout&#xff09;,再画到画布中&#xff08;Paint&am…

【数据结构与算法】二叉树遍历、判断和 diff 算法

遍历 深度优先遍历 function Node(value) {this.value valuethis.left nullthis.right null }let a new Node(a) let b new Node(b) let c new Node(c) let d new Node(d) let e new Node(e) let f new Node(f) let g new Node(g) a.left c a.right b c.l…

如何提升公众号搜索量?分享内部运营的5步优化技术!

最近一直有自媒体同行朋友在写关于公众号的内容&#xff0c;很多都说公众号现在没得玩了。其实&#xff0c;在运营自媒体上面&#xff0c;思维不通&#xff0c;技术不到位&#xff0c;哪个平台都不适合你玩。 想要在自媒体上面运营变现&#xff0c;一定不要先点击广告变现&…

【二分查找】查找数列中数第一次出现的编号

一道巩固二分查找知识的题&#xff0c;非常简单&#xff0c;一起做一下吧 题目&#xff1a; 答案&#xff1a; #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N1000010;int n,m; int q[N];bool isBlue(int num…

7种2024年算法优化BP,实现回归,单/多变量输入,单/多步预测功能,机器学习预测全家桶再更新!...

截止到本期MATLAB机器学习预测全家桶&#xff0c;一共发了19篇关于机器学习预测代码的文章。算上这一篇&#xff0c;一共20篇&#xff01;参考文章如下&#xff1a; 1.五花八门的机器学习预测&#xff1f;一篇搞定不行吗&#xff1f; 2.机器学习预测全家桶&#xff0c;多步预测…

中文乱码 一文讲解 字符集和字符编码 不再困惑(有源码)

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 这可能是应用级程序员最困惑的…

SSTI 服务器端模板注入(Server-Side Template Injection)

1.Web_python_template_injection {{}}是变量包裹标识符&#xff0c;里面存放的是一个变量&#xff0c;当你输入 http://61.147.171.105:55121/{{8*8}} 执行成功&#xff0c;说明存在模版注入。接下来&#xff0c;开始想办法编代码拿到服务器的控制台权限 。 首先&#xff0c…

Redis 命令行客户端

目 录 redis 客户端介绍 redis 客户端介绍 redis 是一个 客户端-服务器 结构的程序&#xff01;&#xff01;&#xff08;类似于 MySQL&#xff09; 因此 redis 客户端和服务器 可以在同一个主机上&#xff0c;也可以在不同主机上. Redis 的客户端也有很多种形态&#xff1a;…

2024 批量下载吾爱破解公众号文章内容/话题/图片/封面/视频/音频,导出文章pdf合集,excel数据包含阅读数留言数粉丝数

前几天看到吾爱破解论坛公众号文章吾爱破解精华集2023&#xff0c;于是把吾爱破解论坛公众号2022-2023年所有公众号文章也下载做成合集分享给大家&#xff0c;网盘地址https://pan.quark.cn/s/9c1b60b822a7 下载的excel文章数据包含文章日期&#xff0c;文章标题&#xff0c;文…

基于springboot实现图书个性化推荐系统项目【项目源码+论文说明】

基于springboot实现图书个性化推荐系统演示 摘要 本论文主要论述了如何使用JAVA语言开发一个图书个性化推荐系统&#xff0c;本系统将严格按照软件开发流程进行各个阶段的工作&#xff0c;采用B/S架构&#xff0c;面向对象编程思想进行项目开发。在引言中&#xff0c;作者将论…

risc-v向量扩展strlen方法学习

riscv向量文档中给出了strlen的实现&#xff0c; 大概是这么一个思路&#xff0c; 加载向量: 使用向量加载指令&#xff08;如 vload&#xff09;从内存中加载一个向量长度的字符。比较向量与零: 使用向量比较指令&#xff08;如 vmask 或 vcmpeq&#xff09;来检查向量中的每…

Js之运算符与表达式

运算符&#xff1a;也叫操作符&#xff0c;是一种符号。通过运算符可以对一个或多个值进行运算&#xff0c;并获取运算结果。 表达式&#xff1a;由数字、运算符、变量的组合&#xff08;组成的式子&#xff09;。 表达式最终都会有一个运算结果&#xff0c;我们将这个结果称…

【电路笔记】-快速了解数字逻辑门

快速了解数字逻辑门 文章目录 快速了解数字逻辑门1、概述2、集成电路的分类3、摩尔定律4、数字逻辑状态5、数字逻辑噪声6、简单的基本数字逻辑门7、基本 TTL 逻辑门8、发射极耦合数字逻辑门9、集成电路的“74”子族10、基本 CMOS 数字逻辑门数字逻辑门是一种电子电路,它根据其…

C++从入门到精通——引用()

C的引用 前言一、C引用概念二、引用特性交换指针引用 三、常引用保证值不变权限的方法权限的放大权限的缩小权限的平移类型转换临时变量 四、引用的使用场景1. 做参数2. 做返回值 五、传值、传引用效率比较值和引用的作为返回值类型的性能比较 六、引用和指针的区别引用和指针的…

动态规划-最长回文子串

动态规划-最长回文子串 原题描述解答中心移动思想代码实现复杂度分析时间复杂度空间复杂度 动态规划思想代码实现复杂度分析时间复杂度空间复杂度 突然觉得很有必要将学过的内容记录下来&#xff0c;这样后续在需要用到的时候就可以避免从头进行学习&#xff0c;而去看自己之前…

调试技巧安全预编译头文件(C++基础)

调试 调试可以选择条件调试和操作调试&#xff1a; 条件调试来选择条件进入断点设置&#xff0c;操作调试来使达到断点条件后完成某些操作&#xff08;一般是output窗口输出&#xff09;。 在这里就只输出了小于6的条件。 安全 降低崩溃、内存泄露、非法访问等问题。 应该转…

GetSystemTimes:获取CPU占用率(WIN API)

原文链接&#xff1a;https://blog.csdn.net/qq_28742901/article/details/104960653 GetSystemTimes函数&#xff1a; BOOL WINAPI GetSystemTimes(__out_opt LPFILETIME lpIdleTime, // 空闲时间__out_opt LPFILETIME lpKernelTime, // 内核进程占用时间__out_opt LPFILETI…

【JavaWeb】Day29.SpringBootWeb请求响应——请求(二)

请求响应 4.数组集合参数 数组集合参数的使用场景&#xff1a;在HTML的表单中&#xff0c;有一个表单项是支持多选的(复选框)&#xff0c;可以提交选择的多个值。 4.1 数组 数组参数&#xff1a;请求参数名与形参数组名称相同且请求参数为多个&#xff0c;定义数组类型形参即…

C++取经之路(其一)——namespace(命名空间),cout,cin(输入输出流),缺省参数。

目录 目录&#xff1a; 前言&#xff1a; namespace(命名空间): 命名空间可以嵌套使用如&#xff1a; 相同的命名空间 cout cin输入输出 std命名空间的使用惯例&#xff1a; 缺省参数&#xff1a; 缺省类型&#xff1a; 前言&#xff1a; 最近开始学习C了&#xff0c;…