专栏首页用户6093955的专栏【表达式转换 (25 分)】

【表达式转换 (25 分)】

题目分析

首先规定优先级,括号为最高优先级,乘号或除号为次优先级,加或减号为最低优先级,至于数字,碰到就直接输出即可。 既然是数字,就有小数,整数,正数,负数之分,还有关于二元运算符的输出,在括号内的二元运算符优先输出,优先级高的优先输出(当然括号不算啊) 根据题意,在输出时可分为以下几种情况。

  • (+1......
  • +1...... 对于正号,是不能输出的
  • -1......
  • 3
  • 34...
  • 3.4... (注意:上面的...指一堆未知长度的数字)
  • 碰到 )符号,将与它对应的括号这之间的符号从栈内导出,也就是输出它们。 上面几种情况只讨论了部分输出问题,下面讨论向栈中插入二元运算符。
  • 当栈为空或者栈顶运算符的优先级小于当前二元运算符的优先级时,将该二元运算符导入。
  • 倘若栈顶运算符的优先级大于或等于当前二元运算符的优先级,又分为以下两种情况,1.若栈顶运算符为( 符号,则直接将该运算符插入即可; 2.若栈顶运算符不是( 符号,则优先输出栈内的元素,直到碰到( 符号或者栈为空,然后将当前二元运算符插入。

正确代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
using namespace std;
stack<char> sign;
char s[22];
map<char, int> mp;
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    mp['+'] = mp['-'] = 1;
    mp['*'] = mp['/'] = 2;
    mp['('] = mp[')'] = 3;
    scanf("%s", s);
    int len = strlen(s);
    bool isfirst = true;
    for(int i = 0; i < len; i++)
    {
        if((!i || (i && s[i-1] == '(')) && (s[i] == '+' || s[i] == '-'))
        {
            if(!isfirst)
                printf(" ");
            if(s[i] != '+')
                printf("%c",s[i]);
            while(i + 1 < len && (s[i+1] == '.' || (s[i+1] >= '0' && s[i+1] <= '9')))
            {
                ++i;
                printf("%c", s[i]);
            }
            if(isfirst)
                isfirst = false;
        }
        else if(s[i] >= '0' && s[i] <= '9')
        {
            if(!isfirst)
                printf(" ");
            printf("%c", s[i]);
            while(i + 1 < len && (s[i+1] == '.' || (s[i+1] >= '0' && s[i+1] <= '9')))
            {
                ++i;
                printf("%c", s[i]);
            }
            if(isfirst)
                isfirst = false;
        }
        else if(s[i] == ')')
        {
            while(!sign.empty() && sign.top() != '(')
            {
                printf(" %c", sign.top());
                sign.pop();   
            }
            if(!sign.empty() && sign.top() == '(')
                sign.pop();
        }
        else if(sign.empty() || (mp[s[i]] > mp[sign.top()]))
            sign.push(s[i]);
        else 
        {
            while(!sign.empty() && sign.top() != '(')
            {
                printf(" %c", sign.top());
                sign.pop();
            }
            sign.push(s[i]);
        }
    }
    while(!sign.empty())
    {
        printf(" %c", sign.top());
        sign.pop();
    }
} 

扩展

关于这道题,如果让你输出这个表达式的值,可以这样做。 安排两个栈,分别存数字和符号,具体要求如下。(该程序还有欠缺,目前对带正号的正数以及小数不支持,只支持正常的整数混合运算)

#include<iostream>
#include<stack>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
stack<int> num;
stack<char> oper;
map<char, int> mp;
char s[22];
void solve(int a, int b, char o)
{
    int c;
    if(o == '+')
        c = a + b;
    else if(o == '-')
        c = a - b;
    else if(o == '*')
        c = a * b;
    else if(o == '/')
        c = a / b;
    if(o != ')')
        num.push(c);
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    scanf("%s", &s);
    int len = strlen(s);
    mp['('] = mp[')'] = 0;
    mp['+'] = mp['-'] = 1;
    mp['*'] = mp['/'] = 2;
    for(int i = 0; i < len; i++)
    {
        if(s[i] >= '0' && s[i] <= '9')
            num.push(s[i] - '0');
        else
        {
            if(oper.empty() || mp[oper.top()] < mp[s[i]] || s[i] == '(')
                oper.push(s[i]);
            else
            {
                if(mp[oper.top()] == mp[s[i]])
                {
                    int b = num.top() ;
                    num.pop();
                    int a = num.top() ;
                    num.pop();
                    solve(a, b, oper.top());
                    oper.pop();
                    oper.push(s[i]);
                }
                else if(mp[oper.top()] > mp[s[i]])
                {
                    if(s[i] == ')')
                    {
                        while(!oper.empty() && mp[oper.top()] > mp[s[i]])
                        {
                            int b = num.top() ;
                            num.pop();
                            int a = num.top() ;
                            num.pop();
                            solve(a, b, oper.top());
                            oper.pop();
                        }
                        if(oper.top() == '(')
                            oper.pop();
                    }
                    else 
                    {
                        while(!oper.empty() && mp[oper.top()] >= mp[s[i]])
                        {
                            int b = num.top() ;
                            num.pop();
                            int a = num.top() ;
                            num.pop();
                            solve(a, b, oper.top());
                            oper.pop();
                        }
                        oper.push(s[i]);
                    }
                }
            }
        }
    }
    while(!oper.empty())
    {
        int b = num.top() ;
        num.pop();
        int a = num.top() ;
        num.pop();
        solve(a, b, oper.top());
        oper.pop();
    }
    cout << num.top() << endl;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Artwork (Gym - 102346A)【DFS、连通块】

    1.这道题就是让你判断从(0,0)到(m,n),避开中途所有的传感器(传感器的检测范围为半径为s的圆)的检测区域,最终能否到达(m,n)。

    _DIY
  • sendRedirect()和forward()方法的区别

    虽然二者都可以实现获取相应的url资源,但首先要注意的是,重定向由sendRedirect来实现,请求转发由forward来实现。

    _DIY
  • JfreeChart 乱码问题处理

    _DIY
  • 起底NuTonomy——凭什么率先发布无人驾驶出租车

    镁客网
  • 直播卖货小程序源码中,商品分类页面是如何实现的

    在直播卖货小程序源码中,一般都包含商品分类页面,如下图,那么这个页面是如何通过代码实现的呢?下面,小编以iOS版本的开发过程为例,来讲述下实现过程。

    万岳教育系统
  • 据说这里可以帮你解决许多关于WebView的问题

    使用WebView开发的坑很多,这是众所周知的。本文分别对WebView的三个基本控件(俗称三剑客WebViewClient,WebChromeClient,W...

    阳仔
  • Android -- 真正的 高仿微信 打开网页的进度条效果

    (本博客为原创,https://cloud.tencent.com/developer/user/1148436/activities) 目录:   一,为什么...

    林冠宏-指尖下的幽灵
  • 邓侃:中国首个全过程智能诊疗系统,全方位披露技术核心和商业模式

    演讲嘉宾:邓侃 【新智元导读】新智元AI WORLD 2017 世界人工智能大会,大数医达CEO、CMU计算机学院暨机器人研究所博士邓侃,发表演讲《智能诊断系统...

    新智元
  • NetScaler 固件升级到11.1版本后管理员界面无法登陆

    最近做了一次Citrix平台的整体升级,由底层XS、应用层XD、XM、PVS访问层NetScaler,在升级Netscaler由10.5到11.1的过程中,出现...

    SuperDream
  • 如何定制一款12306抢票浏览器——用户界面

            我不打算写个Windows界面。因为这个软件的全部就是个浏览器。我准备将”浏览器“进行到底,所以我选择使用html作为我们的用户界面。我也并不打...

    方亮

扫码关注云+社区

领取腾讯云代金券