首页 > 代码库 > 【Zhejiang University PATest】02-3. 求前缀表达式的值

【Zhejiang University PATest】02-3. 求前缀表达式的值

2024-08-07 03:20:38   215人阅读

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3*(7-4)+8/4的前缀表达式是：+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。

输入格式说明：

输入在一行内给出不超过30个字符的前缀表达式，只包含+、-、*、\以及运算数，不同对象（运算数、运算符号）之间以空格分隔。

输出格式说明：

输出前缀表达式的运算结果，精确到小数点后1位，或错误信息“ERROR”。

样例输入与输出：

序号输入输出
1
+ + 2 * 3 - 7 4 / 8 4
13.0
2
/ -25 + * - 2 3 4 / 8 4
12.5
3
/ 5 + * - 2 3 4 / 8 2
ERROR
4
+10.23
10.2

 

【solution】

前缀表达式的求值，算法并不难，我觉得更难的地方是字符串的处理以及一些细节的地方，比较花时间。

算法如下：

“对于一个前缀表达式的求值而言，首先要从右至左扫描表达式，从右边第一个字符开始判断，如果当前字符是数字则一直到数字串的末尾再记录下来，如果是运算符， 则将右边离得最近的两个“数字串”作相应的运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时，最后运算的值也就是表达式的值。例 如，前缀表达式“- 1 + 2 3“的求值，扫描到3时，记录下这个数字串，扫描到2时，记录下这个数字串，当扫描到+时，将+右移做相邻两数字串的运算符，记为2+3，结果为5，记录下这个新数字串，并继续向左扫描，扫描到1时，记录下这个数字串，扫描到-时，将-右移做相邻两数字串的运算符，记为1-5，结果为-4，所以表达式的值为-4。”——来自百度百科词条“前缀表达式”

按照这个算法用栈写出来就可以了，时间复杂度 O(n)。

AC的代码如下：

  1 #include <stdio.h>  2 #include <string.h>  3 #include <stdlib.h>  4 #include <math.h>  5   6 #define exception();  7     printf("ERROR");  8     exit(0);  9  10 int contain(char ch) 11 { 12     if (ch==‘+‘ || ch==‘-‘ || ch==‘*‘ || ch==‘/‘) return 1; 13     return 0; 14 } 15  16 float calc(float a, float b, char ch) 17 { 18     float ans; 19     switch (ch) 20     { 21         case ‘+‘: 22             ans = a+b; 23             break; 24         case ‘-‘: 25             ans = a-b; 26             break; 27         case ‘*‘: 28             ans = a*b; 29             break; 30         case ‘/‘: 31             if (b == 0) { exception(); } 32             ans = a/b; 33             break; 34     } 35     return ans; 36 } 37  38 float addbit(float ans, int boo, char ch, int power) 39 { 40     if (!boo) return (ans*10+ch-‘0‘); 41     else  return (ans+(float)(ch-‘0‘)/pow(10,power)); 42 } 43  44 float str2flo(char *ch) 45 { 46     float ans;  47     int power = 0; 48     int boo = 0, positive = 1; 49      50     if (*ch == ‘-‘)  51     { 52         ch++; 53         positive = 0; 54     } 55     else if (*ch == ‘+‘) ch++; 56      57     ans = *ch-‘0‘; 58     ch++; 59      60     while (*ch != ‘ ‘ && *ch != ‘\0‘ && *ch != ‘\n‘) 61     { 62         if (*ch>=‘0‘ && *ch<=‘9‘) 63         { 64             if (boo) power++; 65             ans = addbit(ans, boo, *ch, power); 66         }  67         else if (*ch==‘.‘) 68         { 69             boo = 1; 70         } 71         ch++; 72     } 73      74     if (positive) return ans; else return -ans; 75 } 76  77 int main() 78 { 79     char str[35]; 80     int n, i, tail = 0; 81     float ans[35]; 82     int boo = 0; 83      84     gets(str); 85      86     n = strlen(str) - 1; 87      88     while (n >= 0) 89     { 90         if ( contain(str[n]) ) 91         { 92             if (tail < 2) { exception(); } 93             else  94             { 95                 ans[tail-2] = calc(ans[tail-1], ans[tail-2], str[n]); 96                 tail--;  97                 n = n - 2; 98             } 99         } 100         else if (str[n] != ‘ ‘)101         {102             while (str[n]!=‘ ‘ && n>=0) n--;103             ans[tail++] = str2flo(str+n+1);104             n--;105         }106         else n--;107     }108     109     if (tail == 1)110     {111         printf("%.1f", ans[0]);112     } 113     else { exception(); }114     115     return 0;116 }

 

【Zhejiang University PATest】02-3. 求前缀表达式的值


联系
我们