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;
}