专栏首页ACM算法日常简单计算器(栈的变种)- HDU 1237

简单计算器(栈的变种)- HDU 1237

Problem Description

读入一个只包含 +, -, *, / 的非负整数计算表达式,计算该表达式的值。

Input

测试输入包含若干测试用例,每个测试用例占一行,每行不超过200个字符,整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束,相应的结果不要输出。

Output

对每个测试用例输出1行,即该表达式的值,精确到小数点后2位。

Sample Input

1 + 2

4 + 2 * 5 - 7 / 11

0

Sample Output

3.00

13.36

堆栈说明:

堆栈是一个在计算机科学中经常使用的抽象数据类型。堆栈中的物体具有一个特性: 最后一个放入堆栈中的物体总是被最先拿出来, 这个特性通常称为后进先出(LIFO)队列。 堆栈中定义了一些操作。 两个最重要的是PUSH和POP。 PUSH操作在堆栈的顶部加入一 个元素。POP操作相反, 在堆栈顶部移去一个元素, 并将堆栈的大小减一。

关于本题的思考:

计算器是一个常用的东西,对于该题而言,其实会很自然的想到使用堆栈或者递归的方式来处理,如果复杂一些的计算器,可能会包含括号,我们甚至可以使用编译原理的语法分析来构造一个状态机,进而可以当作一个数学语言。可是事情往往是我们在正向思维的时候,看起来一切都那么合乎道理,然而实现的效果并不理想,并不是我们的想法是错的,而是在具体实现的过程中,有太多的技巧需要注意,仔细回顾之前的题目,可以发现每一个实际题目都有一些特殊的处理。

对于使用标准栈来实现的同学,只能说是走在正确的道路上,但不是走在性能极限的道路上,我觉得ACM提供的题目就是为了能让这些正确的道路优化成一条既正确有高效的道路,这不是看算法书能够得来的,也因此具有很大的意义。

任何数据结构,包括链表、堆栈、队列、树还有图,一个比较大的性能优化是将算法书上通常意义的节点换成数组,因为数组的性能非常好而且简洁

本题题意简单,解法也简单,但是值得深思。

源代码:请先自己思考解题思路,然后花3分钟时间看源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*读取数字,并且操作字符串*/
double digit(char ** exp_)
{
    char * exp = *exp_;
    double number = 0;
    for (*exp; *exp && *exp != ' '; ++(exp)) {
        //每前进一步,计算数字
        number = number * 10 + *exp - '0';
        ++(*exp_);
    };
    //空格,继续前进一步,注意防止越界
    if(*exp){
        ++(*exp_);
    }
    return number;
}

/*读取操作符,并且操作字符串*/
char function(char ** exp)
{
    //读取字符,前进一步
    char f = *(*exp)++;
    //空格,继续前进一步
    (*exp)++;
    return f;
}

//计算表达式的值
//使用数组作为容器
double calc(char * exp)
{
    double numbers[205];
    //将第一个数字保存在0号位置
    numbers[0] = digit(&exp);
    int i = 0;

    while (*exp) {
        //读取操作符
        char f = function(&exp);
        //读取下一个数字
        double next_value = digit(&exp);
        //如果是乘法和除法,直接将结果存在原位置
        if (f == '*')numbers[i] *= next_value;
        else if (f == '/')numbers[i] /= next_value;
        //如果是加法和减法,则将结果保存在下一位,这是优先级处理的关键点
        else if (f == '+')numbers[++i] = next_value;
        else
        {
            //除法
            numbers[++i] = -next_value;
        }
    }
    //最后只需要进行加法操作,将所有存的数据累加
    for (i; i > 0; i--)
        numbers[0] += numbers[i];
    //返回累加结果
    return numbers[0];
}

int main(int argc, char const *argv[])
{
    char exp[300];
    memset(exp, 0, sizeof(exp));
    //输入表达式
    while (gets(exp) && strcmp(exp, "0"))
    {
        //计算结果
        double value = calc(exp);
        //清空字符串
        memset(exp, 0, sizeof(exp));
        //输出结果
        printf("%.2lf\n", value);
    }

    return 0;
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:dansen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-20

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDOJ 1237题 简单计算器

    简单计算器 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java...

    谙忆
  • 程序员进阶之算法练习(十一)有感而发

    前言 经过这几年的观察,我发现,国内本科高校的ACM集训队,往往汇聚着该校相对靠谱的那一批人。 拿本校举例,队内的众学长学姐毕业之后,有去国内top2的高校...

    落影
  • ACM之坑&amp;套路

    写在前边:这些梗都是敝人自己做题和比赛时曾经坑过自己的地方,特别在这里记录一下,所有的链接都是本博客中的题解链接(有大致题意说明和代码),原题请到OJ上自行寻找...

    ACM算法日常
  • 模拟退火算法从原理到实战【基础篇】

      模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达...

    Angel_Kitty
  • 程序员进阶之算法练习(十二)

    前言 题目地址在HDU,输入对应的题号即可看到题目,在百度搜索hdu+对应的题号可以看到题解。 我简单的对题目难度进行了划分: 简单题:想法题,实现简单...

    落影
  • vb.net简单的计算器实现

    全栈程序员站长
  • PyQt5实现简单的计算器

    下面我们将介绍使用python的PyQt5图形界面来编写一个简易的计算器,实现“加,减,乘,除,平方,开方”等运算。

    砸漏
  • servlet实现简单的计算器

    从今天开始,我会将这学期陆续学习的一些知识,发到网上,也会不断添加新的知识点。 今天,先用servlet编写一个简易的计算器。使用eclipse或myecl...

    曼路
  • java设计之简单的JAVA计算器

           做这个东西主要是为了练习一下以前学习过的java Swing,所以那些复杂的算法就没有加载到里面去........        先展示一下效果....

    Gxjun

扫码关注云+社区

领取腾讯云代金券