浙江省理工ZSTU 2853 计算表达式的值

浙江理工ZSTU 2853 计算表达式的值

表达式计算

Time Limit:1000MS  Memory Limit:65536K
Total Submit:202 Accepted:55

Description

一个表达式由是由操作数，运算符以及分隔符所构成的,一般我们所写的是中序表达式，也就是运算符在两个操作数之间。由于表达式有优先级，所以计算机用中序表达式并不是很方便，所以计算机中并不使用中序表达式，比较常见的是前序和后序表示法。前序，中序及后序主要区别在于运算符的所在位置不同，前序表达式是将运算符写在两个操作数之前，而后序表达式是将运算符写在两个操作数之后。
例如对与X/(Y-Z)（中序）的
前序表示：/X-YZ
后序表示：XYZ-/
本题的任务很简单：就是要求给一个中序表达式然后计算他的最后结果。

Input

一个字符串表达式，表达式中只有’+’, ‘-’, ‘*’, ‘/’, 数字”0~9”，还有左右括号”()”字符,输入保证表达式合法，而且输入的操作数都是整数。表达式长度不超过150

Output

输出表达式最后的结果,最后结果保留四位小数

Sample Input

1+3*(8+9)/2-100

Sample Output

26.5000-100.0000

Source

Lin Jiudui

/*E：四则运算求值，可用栈转为逆波兰表达式求解，也可递归，处理好运算顺序即可。*///题目：HJN//题解：CSGrandeur//2012.03.07#include<stdio.h>#include<string.h>#include<stdlib.h>#include<ctype.h>const int maxn = 1 << 7;char buf[maxn];void init(){ int i, j; for(i = j = 0; buf[i]; ++ i) {  if(buf[i] != ' ' && buf[i] != '\t')   buf[j ++] = buf[i]; } buf[j] = 0;}//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////bool Isnum(int l, int r){ int i; if(buf[l] == '-' || buf[l] == '+') ++ l; for(i = l; i < r; ++ i)  if(!isdigit(buf[i])) return false;//只要有一个不是数字就返回错误 return true;//全部是数字的时候才能够执行这一步}double Cal(int l, int r){ int i, bckcnt; double x; if(l >= r) return 0; if(Isnum(l, r))//全部是数字或用+ -的时候才会进行转换 {  sscanf(buf + l, "%lf", &x);//把字符 转换为数字 赋给x  return x; } //加法优先 for(i = l, bckcnt = 0; i < r; ++ i) {     bckcnt += buf[i] == '(';     bckcnt -= buf[i] == ')';     if(!bckcnt && buf[i] == '+')//例如（5+5）由于当bckcnt等于0的时候不为加号 下面类似 会执行最后一步的            return Cal(l, i) + Cal(i + 1, r); } //减法不能直接按减法递归，否则影响后面的加减号 for(i = l, bckcnt = 0; i < r; ++ i) {     bckcnt += buf[i] == '(';     bckcnt -= buf[i] == ')';     if(!bckcnt && buf[i] == '-' && i != l)//i != l 防止一开始的负号            return Cal(l, i) + Cal(i, r);//这里不能用减 如果是8-3 这种可以用 但是对于8-3+4就不行了 如果用减得话  // 则变成了8-（3+4）   所以要把-3+4 一起去递归 } //乘法 for(i = l, bckcnt = 0; i < r; ++ i) {     bckcnt += buf[i] == '(';     bckcnt -= buf[i] == ')';     if(!bckcnt && buf[i] == '*')            return Cal(l, i) * Cal(i + 1, r); } //除法不会作为一个数字的符号，所以比减法容易处理 for(i = l, bckcnt = 0; i < r; ++ i) {     bckcnt += buf[i] == '(';     bckcnt -= buf[i] == ')';     if(!bckcnt && buf[i] == '/')            return Cal(l, i) / Cal(i + 1, r); } //处理开头负号 if(buf[l] == '-') return -Cal(l + 1, r);  //表达式在括号里的情况  return Cal(l + 1, r -1);}//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////int main(){ while(gets(buf)) {  init();//初始化  干掉空格  printf("%.4f\n", Cal(0, strlen(buf))); } return 0;}