简单计算器(栈的变种)- 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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

左右用R右手Python系列——字符串格式化输出

学习Python不到一个月,虽然学的很渣,但是还是想通过这种途径分享自己的学习心得,毕竟当初学习R语言也是这么走过来的。 今天是R语言与Python综合系列的第...

4456
来自专栏彭湖湾的编程世界

【算法】哈希表的诞生

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

35510
来自专栏HTML5学堂

原生JS | 数据类型检测,并没你想象的那么简单

HTML5学堂-码匠:看上去,JavaScript中的数据类型检测,并没有什么难度,但是……它包含了不少的知识,如果你只知道一个typeof的话,那很建议你读读...

3425
来自专栏zhisheng

运算优先级、结合性、求值顺序、副作用和顺序点

标题中这几个概念,是很多C/C++程序员在表达式上容易出问题或不清楚的地方,虽然这些概念在很多语言都有体现,但C里面特别明显,所以就以C语言为例子总结下 运算...

4867
来自专栏编程

浅谈如何定义和调用Python的函数

函数是python编程核心内容之一,笔者在本文中主要介绍下函数的概念和基础函数相关知识点。函数是什么?有什么作用、定义函数的方法及如何调用函数。 函数是可以实现...

1845
来自专栏诸葛青云的专栏

想当黑客?浅谈C语言编程:不会这个知识就别想了!

看到标题点进来的朋友,应该对黑客这个名词很敏感吧?我想应该是这样的,但是你们知道作为一名黑客需要学习哪些知识吗?小编不是什么大佬,但小编可以明确的告诉你,学习C...

2680
来自专栏Java开发者杂谈

Thinking in java(1):对象导论

纯粹的面向对象程序设计的几个特性: 1. 万物皆对象 2. 程序是对象的合集,他通过发消息告诉彼此要做什么 3. 每个对象都有自己的由其他对象所构成的存储 4....

37612
来自专栏非著名程序员

鸡蛋问题来了,是先有Class还是先有Object?

周末比较无聊,在浏览论坛的时候,偶然看到一个程序猿提问的问题,他时这样提问的:突然想到一个很菜的问题, 倒底先有Object还是先有Class?所有类都是Obj...

2076
来自专栏深度学习自然语言处理

介绍4个大神常用而你不常用的python函数

1101
来自专栏vue学习

函数声明提升与变量提升

1.当在函数的作用域里定义一个和外部变量一样的名称的变量时,变量声明会提升至第一句,但是赋值则不变

1052

扫码关注云+社区

领取腾讯云代金券