nyoj-----前缀式计算

前缀式计算

时间限制:1000 ms  |           内存限制:65535 KB

难度:3

描述

先说明一下什么是中缀式:

如2+(3+4)*5这种我们最常见的式子就是中缀式。

而把中缀式按运算顺序加上括号就是:(2+((3+4)*5))

然后把运算符写到括号前面就是+(2 *( +(3 4) 5) )

把括号去掉就是:+ 2 * + 3 4 5

最后这个式子就是该表达式的前缀表示。

给你一个前缀表达式,请你计算出该前缀式的值。

比如:

+ 2 * + 3 4 5的值就是 37

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是正数,并且都小于10,操作数数目不超过500。 以EOF为输入结束的标志。输出对每组数据,输出该前缀表达式的值。输出结果保留两位小数。样例输入

+ 2 * + 3 4 5
+ 5.1 / 3 7

样例输出

37.00
5.53

来源经典题目上传者张云聪

前缀表达式:

前缀表达式的计算机求值: 又称波兰式

从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。 例如前缀表达式“- × + 3 4 5 6”: (1) 从右至左扫描,将6、5、4、3压入堆栈; (2) 遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素,注意与后缀表达式做比较),计算出3+4的值,得7,再将7入栈; (3) 接下来是×运算符,因此弹出7和5,计算出7×5=35,将35入栈; (4) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。 可以看出,用计算机计算前缀表达式的值是很容易的。

用栈来表示:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<stack>
using namespace std;
char aa[3005];
int main()
{
    stack<double>ans;
    char bb[30],*pre,tt[30];
    double cc,dd;
    int j;
    while(gets(aa)!=NULL)
    {
        j=0;
        for(int i=strlen(aa)-1;i>=0;i--)   /*前缀表达式,从右望左数*/
        {
            if(aa[i]==' ')
            {
               if(bb[0]<='9'&&bb[0]>='0')
               {
                 for(int k=j-1;k>=0;k--)  /*将字符串取反*/
                      tt[j-1-k]=bb[k];
                 j=0;
                 ans.push(strtod(tt,&pre));
                 memset(bb,'\0',sizeof(bb));
                 memset(tt,'\0',sizeof(tt));
               }
            }
            else 
            {
                if(aa[i]<='9'&&aa[i]>='0'||aa[i]=='.')
                     bb[j++]=aa[i];
                else 
                {
                   cc=ans.top();
                   ans.pop();
                   dd=ans.top();
                   ans.pop();
                   switch(aa[i])
                   {
                    case '+': ans.push(cc+dd);break;
                    case '-': ans.push(cc-dd);break;
                    case '/': ans.push(cc/dd);break;
                    case '*': ans.push(cc*dd);break;
                   }
                }
            }
        }
        if(ans.empty())
        {
              if(bb[0]<='9'&&bb[0]>='0')
               {
                 for(int k=j-1;k>=0;k--)  /*将字符串取反*/
                      tt[j-1-k]=bb[k];
                 j=0;
                 ans.push(strtod(tt,&pre));
                 memset(bb,'\0',sizeof(bb));
                 memset(tt,'\0',sizeof(tt));
               }
        }
        cc=ans.top();
        ans.pop();
        printf("%.2lf\n",cc);
    }
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信小驿站

python-运算符与表达式

你所编写的大多数语句(逻辑行)都包含了表达式(Expressions)。一个表达式的简单例子便是 2+3。表达式可以拆分成运算符(Operators)与操作数(...

19920
来自专栏lzj_learn_note

1-python基础

​ 同一个变量a可以反复赋值,且可以是不同类型的变量. 这种变量本身类型不固定的语言称为动态语言, 比如python, javascript....

27520
来自专栏CSDN技术头条

常见的七种排序算法解析

01 选择排序 实现原理 首先从未排序序列中找到最小的元素,放置到排序序列的起始位置,然后从剩余的未排序序列中继续寻找最小元素,放置到已排序序列的末尾。所以称之...

21080
来自专栏深度学习思考者

Python学习(二) 正则表达式

Python正则表达式 正则表达式是一个特殊的字符序列,它能帮助你方便的检查一个字符串是否与某种模式匹配。re 模块使 Python 语言拥有全部的正则表达式功...

20890
来自专栏章鱼的慢慢技术路

多维数组的传递

16440
来自专栏Python小屋

Python内置函数sorted()和列表方法sort()排序规则不得不说的事

Python内置函数sorted()和列表方法sort()可以使用key参数指定排序规则,并且都是稳定排序,也就是说,对于指定规则不能涵盖的元素,本来谁在前面,...

27630
来自专栏编程

Shell 数组

Shell中数据类型不多,比如说字符串,数字类型,数组。数组是其中比较重要的一种,同时Shell中的数组不像JAVA/C,只能是一维数组,没有二维数组;数组元素...

21700
来自专栏PHP在线

PHP函数

请点击上面蓝色PHP关注 你知道这些简单的函数中的方法吗? count() 函数计算数组中的单元数目或对象中的属性个数。 对于数组,返回其元素的个数,对于其他值...

29950
来自专栏kalifaの日々

一个易于理解的C++全排列(permutation)实现

通常我们用这两条语句可以得到一个数组的全排列: sort(nums.begin(),nums.end()); //调用next_permutation求全排列...

35550
来自专栏大前端开发

ES6特性之:解构

解构(destructuring assignment), 也称解构赋值,这种语法可以方便的将数组元素或对象属性赋成新的变量。

7120

扫码关注云+社区

领取腾讯云代金券