[已解决]算术表达式求值(10以内整数)

柠檬Ccc

【问题描述】假设一算术表达式的所有操作数均为10以内的整数，请编写代码实现表达式求值。

假设算术表达式满足:

(1) 小括号已匹配；

(2) 表达式无除0错误;

(3) 表达式中间没有多余的空格。

要求： 表达式计算的中间值可以是负数或者实数

【输入形式】第一行输入表达式字符串
【输出形式】第二行输出计算结果（保留两位小数）
【样例输入】(4+1*(5-2))-6/3
【样例输出】5.00

最佳答案

月排行榜 / 总排行榜

人造人

2022-4-30 13:45:11

先贴代码

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. #include <ctype.h>
   
4. 
   
5. enum {EMPTY = 256, ERROR, OK, NUM};
   
6. 
   
7. int symbol;
   
8. double value;
   
9. 
   
10. int symbol_;
    
11. double value_;
    
12. 
    
13. void back(void) {
    
14.     symbol_ = symbol;
    
15.     value_ = value;
    
16. }
    
17. 
    
18. void next(void) {
    
19.     if(symbol_ != 0) {
    
20.         symbol = symbol_;
    
21.         value = value_;
    
22.         symbol_ = 0;
    
23.         return;
    
24.     }
    
25.     symbol = getchar();
    
26.     switch(symbol) {
    
27.         case ' ':
    
28.         case '\t':
    
29.         case '\v':
    
30.         case '\f':
    
31.             return next();
    
32.     }
    
33.     if(!isdigit(symbol)) return;
    
34.     ungetc(symbol, stdin);
    
35.     int temp;
    
36.     scanf("%d", &temp);
    
37.     value = temp;
    
38.     symbol = NUM;
    
39.     return;
    
40. }
    
41. 
    
42. void factor(void) {
    
43.     next();
    
44.     if(symbol == NUM) return;
    
45.     if(symbol != '(') goto err;
    
46.     void expression(void);
    
47.     expression();
    
48.     if(symbol != NUM) goto err;
    
49.     double temp = value;
    
50.     next();
    
51.     if(symbol != ')') goto err;
    
52.     symbol = NUM;
    
53.     value = temp;
    
54.     return;
    
55. err:
    
56.     symbol = ERROR;
    
57.     return;
    
58. }
    
59. 
    
60. void term(void) {
    
61.     factor();
    
62.     if(symbol != NUM) goto err;
    
63.     double a = value;
    
64.     next();
    
65.     if(!(symbol == '*' || symbol == '/')) {
    
66.         back();
    
67.         symbol = NUM;
    
68.         value = a;
    
69.         return;
    
70.     }
    
71.     int op = symbol;
    
72.     term();
    
73.     if(symbol != NUM) goto err;
    
74.     value = op == '*' ? a * value : a / value;
    
75.     return;
    
76. err:
    
77.     symbol = ERROR;
    
78.     return;
    
79. }
    
80. 
    
81. void expression(void) {
    
82.     term();
    
83.     if(symbol != NUM) goto err;
    
84.     double a = value;
    
85.     next();
    
86.     if(!(symbol == '+' || symbol == '-')) {
    
87.         back();
    
88.         symbol = NUM;
    
89.         value = a;
    
90.         return;
    
91.     }
    
92.     int op = symbol;
    
93.     expression();
    
94.     if(symbol != NUM) goto err;
    
95.     value = op == '+' ? a + value : a - value;
    
96.     return;
    
97. err:
    
98.     symbol = ERROR;
    
99.     return;
    
100. }
     
101. 
     
102. void line(void) {
     
103.     next();
     
104.     if(symbol == '\n') return;
     
105.     back();
     
106.     expression();
     
107.     if(symbol == '\n') return;
     
108.     if(symbol != NUM) goto err;
     
109.     double a = value;
     
110.     next();
     
111.     if(symbol != '\n') goto err;
     
112.     printf(">>> %lf\n", a);
     
113.     return;
     
114. err:
     
115.     printf("错误的表达式!\n");
     
116.     symbol = ERROR;
     
117.     return;
     
118. }
     
119. 
     
120. void lines(void) {
     
121.     next();
     
122.     if(symbol == EOF) {
     
123.         symbol = OK;
     
124.         return;
     
125.     }
     
126.     back();
     
127.     line();
     
128.     //if(symbol == ERROR) return;
     
129.     return lines();
     
130. }
     
131. 
     
132. bool start(void) {
     
133.     lines();
     
134.     if(symbol != OK) return false;
     
135.     next();
     
136.     if(symbol != EOF) return false;
     
137.     return true;
     
138. }
     
139. 
     
140. int main(void) {
     
141.     start();
     
142.     return 0;
     
143. }
     

复制代码

假设1. 小括号已匹配
我不做这个假设，如果括号不匹配，我写的这个程序会打印一个错误信息

假设3. 表达式中间没有多余的空格
要在程序中忽略这些多余的空格也不复杂呀，所以我写的这个程序依然不做这个假设

假设 所有操作数均为10以内的整数
这个假设没意思吧，就支持一位数字？你用scanf读取不就可以了

假设太多了，没意思

下面说一说这个代码的思路
1. 首先写出这个语言（表达式）的文法

1. start: lines (EOF);
   
2. 
   
3. lines: (EMPTY)
   
4.      | line lines
   
5.      ;
   
6. 
   
7. line: expression '\n' {print(expression);}
   
8.     | '\n'
   
9.     | (ERROR) {printf("错误的表达式!\n");}
   
10.     ;
    
11. 
    
12. expression: term
    
13.           | expression '+' term {$$ = $1 + $3;}
    
14.           | expression '-' term {$$ = $1 - $3;}
    
15.           ;
    
16. 
    
17. term: factor
    
18.     | term '*' factor {$$ = $1 * $3;}
    
19.     | term '/' factor {$$ = $1 / $3;}
    
20.     ;
    
21. 
    
22. factor: NUM
    
23.       | '(' expression ')' {$$ = $2;}
    
24.       ;

复制代码

2. 消除左递归， 因为要使用递归下降分析

1. expression: term expression_;
   
2. expression_: (EMPTY)
   
3.            | '+' term expression_
   
4.            | '-' term expression_
   
5.            ;
   
6. 
   
7. term: factor term_;
   
8. term_: (EMPTY)
   
9.      | '*' factor term_
   
10.      | '/' factor term_
    
11.      ;

复制代码

编译原理教材中用的是这种方法
但是，为什么不能改成这样？

1. expression: term
   
2.           | term '+' expression {$$ = $1 + $3;}
   
3.           | term '-' expression {$$ = $1 - $3;}
   
4.           ;
   
5. 
   
6. term: factor
   
7.     | factor '*' term {$$ = $1 * $3;}
   
8.     | factor '/' term {$$ = $1 / $3;}
   
9.     ;

复制代码

这样也没有左递归呀，上面的那个代码用的就是这种方法，到目前为止还没有发现 有什么问题

3. 照着这个文法，用递归下降分析，写代码
4. 调试，^_^

跳转到最佳答案楼层

人造人

先贴代码

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. #include <ctype.h>
   
4. 
   
5. enum {EMPTY = 256, ERROR, OK, NUM};
   
6. 
   
7. int symbol;
   
8. double value;
   
9. 
   
10. int symbol_;
    
11. double value_;
    
12. 
    
13. void back(void) {
    
14.     symbol_ = symbol;
    
15.     value_ = value;
    
16. }
    
17. 
    
18. void next(void) {
    
19.     if(symbol_ != 0) {
    
20.         symbol = symbol_;
    
21.         value = value_;
    
22.         symbol_ = 0;
    
23.         return;
    
24.     }
    
25.     symbol = getchar();
    
26.     switch(symbol) {
    
27.         case ' ':
    
28.         case '\t':
    
29.         case '\v':
    
30.         case '\f':
    
31.             return next();
    
32.     }
    
33.     if(!isdigit(symbol)) return;
    
34.     ungetc(symbol, stdin);
    
35.     int temp;
    
36.     scanf("%d", &temp);
    
37.     value = temp;
    
38.     symbol = NUM;
    
39.     return;
    
40. }
    
41. 
    
42. void factor(void) {
    
43.     next();
    
44.     if(symbol == NUM) return;
    
45.     if(symbol != '(') goto err;
    
46.     void expression(void);
    
47.     expression();
    
48.     if(symbol != NUM) goto err;
    
49.     double temp = value;
    
50.     next();
    
51.     if(symbol != ')') goto err;
    
52.     symbol = NUM;
    
53.     value = temp;
    
54.     return;
    
55. err:
    
56.     symbol = ERROR;
    
57.     return;
    
58. }
    
59. 
    
60. void term(void) {
    
61.     factor();
    
62.     if(symbol != NUM) goto err;
    
63.     double a = value;
    
64.     next();
    
65.     if(!(symbol == '*' || symbol == '/')) {
    
66.         back();
    
67.         symbol = NUM;
    
68.         value = a;
    
69.         return;
    
70.     }
    
71.     int op = symbol;
    
72.     term();
    
73.     if(symbol != NUM) goto err;
    
74.     value = op == '*' ? a * value : a / value;
    
75.     return;
    
76. err:
    
77.     symbol = ERROR;
    
78.     return;
    
79. }
    
80. 
    
81. void expression(void) {
    
82.     term();
    
83.     if(symbol != NUM) goto err;
    
84.     double a = value;
    
85.     next();
    
86.     if(!(symbol == '+' || symbol == '-')) {
    
87.         back();
    
88.         symbol = NUM;
    
89.         value = a;
    
90.         return;
    
91.     }
    
92.     int op = symbol;
    
93.     expression();
    
94.     if(symbol != NUM) goto err;
    
95.     value = op == '+' ? a + value : a - value;
    
96.     return;
    
97. err:
    
98.     symbol = ERROR;
    
99.     return;
    
100. }
     
101. 
     
102. void line(void) {
     
103.     next();
     
104.     if(symbol == '\n') return;
     
105.     back();
     
106.     expression();
     
107.     if(symbol == '\n') return;
     
108.     if(symbol != NUM) goto err;
     
109.     double a = value;
     
110.     next();
     
111.     if(symbol != '\n') goto err;
     
112.     printf(">>> %lf\n", a);
     
113.     return;
     
114. err:
     
115.     printf("错误的表达式!\n");
     
116.     symbol = ERROR;
     
117.     return;
     
118. }
     
119. 
     
120. void lines(void) {
     
121.     next();
     
122.     if(symbol == EOF) {
     
123.         symbol = OK;
     
124.         return;
     
125.     }
     
126.     back();
     
127.     line();
     
128.     //if(symbol == ERROR) return;
     
129.     return lines();
     
130. }
     
131. 
     
132. bool start(void) {
     
133.     lines();
     
134.     if(symbol != OK) return false;
     
135.     next();
     
136.     if(symbol != EOF) return false;
     
137.     return true;
     
138. }
     
139. 
     
140. int main(void) {
     
141.     start();
     
142.     return 0;
     
143. }
     

复制代码

假设1. 小括号已匹配
我不做这个假设，如果括号不匹配，我写的这个程序会打印一个错误信息

假设3. 表达式中间没有多余的空格
要在程序中忽略这些多余的空格也不复杂呀，所以我写的这个程序依然不做这个假设

假设 所有操作数均为10以内的整数
这个假设没意思吧，就支持一位数字？你用scanf读取不就可以了

假设太多了，没意思

下面说一说这个代码的思路
1. 首先写出这个语言（表达式）的文法

1. start: lines (EOF);
   
2. 
   
3. lines: (EMPTY)
   
4.      | line lines
   
5.      ;
   
6. 
   
7. line: expression '\n' {print(expression);}
   
8.     | '\n'
   
9.     | (ERROR) {printf("错误的表达式!\n");}
   
10.     ;
    
11. 
    
12. expression: term
    
13.           | expression '+' term {$$ = $1 + $3;}
    
14.           | expression '-' term {$$ = $1 - $3;}
    
15.           ;
    
16. 
    
17. term: factor
    
18.     | term '*' factor {$$ = $1 * $3;}
    
19.     | term '/' factor {$$ = $1 / $3;}
    
20.     ;
    
21. 
    
22. factor: NUM
    
23.       | '(' expression ')' {$$ = $2;}
    
24.       ;

复制代码

2. 消除左递归， 因为要使用递归下降分析

1. expression: term expression_;
   
2. expression_: (EMPTY)
   
3.            | '+' term expression_
   
4.            | '-' term expression_
   
5.            ;
   
6. 
   
7. term: factor term_;
   
8. term_: (EMPTY)
   
9.      | '*' factor term_
   
10.      | '/' factor term_
    
11.      ;

复制代码

编译原理教材中用的是这种方法
但是，为什么不能改成这样？

1. expression: term
   
2.           | term '+' expression {$$ = $1 + $3;}
   
3.           | term '-' expression {$$ = $1 - $3;}
   
4.           ;
   
5. 
   
6. term: factor
   
7.     | factor '*' term {$$ = $1 * $3;}
   
8.     | factor '/' term {$$ = $1 / $3;}
   
9.     ;

复制代码

这样也没有左递归呀，上面的那个代码用的就是这种方法，到目前为止还没有发现 有什么问题

3. 照着这个文法，用递归下降分析，写代码
4. 调试，^_^