表达式计算六月飞雪

　表达式计算

表达式计算

Time Limit: 1000 MS

Memory Limit: 10240 K

Total Submit: 9(5 users)

Total Accepted: 6(5 users)

Rating:

Special Judge: No

Description

输入一个中缀表达式，要求输出计算的结果，保留到小数点后4为位。

表达式中的数均为非负数，可能为小数，不会出现-2，+2的情况，就是说不会有 1 + - 2、1 * -2、2*+2这样的情况。

数字为整数或者带小数的形式，如12、12.345.

符号定义如下：

加法 + ，减法 - ，乘法 * ，除法 / 。

括号 ( ) 。

优先级定义：

加法和减法优先级相同，乘法和除法的优先级相同，加法和减法的优先级比乘法和除法的优先级低。

遇到括号，则括号内的运算优先级高，以此类推。

Input

有多组测试数据，测试数据组数不超过2000个。

每组占一行，不超过2000个字符。所含字符为空格，数字，"+"， "-"， "*"， "/" ，"("，")"，还有小数点"."。

保证每组测试数据均有解和数据的精度。

Output

对于每组测试数据，输出一行，为表达式计算的结果，结果保留到小数点后2位。

Sample Input

1 + 1 + 2
1 - 2.0
(1.0)+2-1*2
37- 89+ 80.295* (86.473)-67*42- (75.077)-5.144- 81.987+ 64.204* (11+ 22- (51-74.867)* (4.737)- (16.017)- 17)/ 23

Sample Output

4.00
-1.00
1.00
4230.69

问题来自： http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1572

这题是栈的经典题，但是之前总是想不出，后来重新整理了思路，才终于AC了。

主要考察了思考的周密性！

①遇到空格的处理

②字符串的最后一个字符是数字的处理

③同级运算的处理、高级遇低级的处理

④低级遇高级的处理

⑤字符串转换为double

⑥符号栈的当前运算符的上一个元素是'('

⑦各种运算、处理的先后顺序......

View Code

  1 # include <stdio.h>
  2 # include <string.h>
  3 
  4 char str[2510], sym_stack[2510], s[2510];
  5 double num_stack[2510];
  6 int num_top, sym_top;
  7 
  8 int main () {
  9     void culcalate();
 10 
 11     while (gets(str)) {
 12         num_top = sym_top = -1;
 13         culcalate();
 14 
 15         printf("%.2lf\n", num_stack[0]);
 16     }
 17 
 18     return 0;
 19 }
 20 
 21 void culcalate() {
 22     void cul(char);
 23     void convert(int st, int en);
 24 
 25     int i, st, en;
 26     st = en = -1;
 27     for (i = 0; str[i] != '\0'; ++i) {
 28         if ('0' <= str[i]  &&  str[i] <= '9'  ||  str[i] == '.') {
 29             if (st == -1) {
 30                 st = i;
 31             }
 32             if (str[i+1] == '\0') { //②
 33                 en = i+1;
 34             }
 35         }
 36         else if (st != -1) {
 37             en = i;
 38         }
 39         if (st != -1  &&  en != -1) {
 40             convert(st, en);//⑤
 41             st = en = -1;
 42         }
 43         if (str[i] == ' ') continue;//①
 44 
 45         if (sym_top == -1) {
 46             if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '(' ) {
 47                 sym_stack[++sym_top] = str[i];
 48                 continue;
 49             }
 50         }
 51         else if (str[i] == '(') {//④
 52             sym_stack[++sym_top] = str[i];
 53             continue;
 54         }
 55         else if ((sym_stack[sym_top] == '+' || sym_stack[sym_top] == '-') && (str[i] == '*' || str[i] == '/')) {//④
 56             sym_stack[++sym_top] = str[i];
 57             continue;
 58         }
 59         else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/') {//③
 60             if (sym_stack[sym_top] == '(' ) {//⑥
 61                 sym_stack[++sym_top] = str[i];
 62                 continue;
 63             }
 64             int flag = 0;
 65             if (sym_stack[sym_top] == '*' || sym_stack[sym_top] == '/') flag = 1;//符号栈栈顶元素是乘除号，做一个flag开关
 66             cul(sym_stack[sym_top]);
 67             if (flag && (str[i] == '*' || str[i] == '/')) {/**乘除遇乘除的处理，很难想到！**/
 68                 sym_stack[++sym_top] = str[i];
 69                 continue;
 70             }
 71             while (sym_top > -1 && sym_stack[sym_top] != '('  //循环解决栈中剩下的同级运算，注意判断条件
 72                     &&  (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')) {
 73                 cul(sym_stack[sym_top]);

 74             }
 75             sym_stack[++sym_top] = str[i];
 76         }
 77         else if (str[i] == ')') {//遇到反括号要把括号里的算完然后去掉括号
 78             while (sym_stack[sym_top] != '(') {
 79                 cul(sym_stack[sym_top]);
 80             }
 81             sym_top--;
 82         }
 83     }
 84     while (sym_top > -1) {
 85         cul(sym_stack[sym_top]);//如果str字符串已遍历完了符号栈不为空，
 86                                 //那么剩下的运算符使用完，而且这些运算符肯定是同级的
 87                                 //因为在上面的循环中已经把低级遇高级的情况解决完了
 88     }
 89 }
 90 
 91 void cul(char c) {
 92     if (c == '+') {
 93         num_stack[num_top-1] += num_stack[num_top];
 94     }
 95     if (c == '-') {
 96         num_stack[num_top-1] -= num_stack[num_top];
 97     }
 98     if (c == '*') {
 99         num_stack[num_top-1] *= num_stack[num_top];
100     }
101     if (c == '/') {
102         num_stack[num_top-1] /= num_stack[num_top];
103     }
104     num_top--;
105     sym_top--;
106 }
107 
108 
109 void convert(int st, int en) {
110     int i, k = 0;
111     for (i = st; i < en; ++i) {
112         s[k++] = str[i];
113     }
114     s[k] = '\0';
115     sscanf(s, "%lf", &num_stack[++num_top]);
116 }

本文结束。

表达式计算 六月飞雪

表达式计算六月飞雪