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

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如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的代码如下：

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <math.h>

 #define exception();\

     printf("ERROR");\

     exit();

 int contain(char ch)

 {

     if (ch=='+' || ch=='-' || ch=='*' || ch=='/') return ;

     return ;

 }

 float calc(float a, float b, char ch)

 {

     float ans;

     switch (ch)

     {

         case '+':

             ans = a+b;

             break;

         case '-':

             ans = a-b;

             break;

         case '*':

             ans = a*b;

             break;

         case '/':

             if (b == ) { exception(); }

             ans = a/b;

             break;

     }

     return ans;

 }

 float addbit(float ans, int boo, char ch, int power)

 {

     if (!boo) return (ans*+ch-'');

     else  return (ans+(float)(ch-'')/pow(,power));

 }

 float str2flo(char *ch)

 {

     float ans;

     int power = ;

     int boo = , positive = ;

     if (*ch == '-')

     {

         ch++;

         positive = ;

     }

     else if (*ch == '+') ch++;

     ans = *ch-'';

     ch++;

     while (*ch != ' ' && *ch != '\0' && *ch != '\n')

     {

         if (*ch>='' && *ch<='')

         {

             if (boo) power++;

             ans = addbit(ans, boo, *ch, power);

         }

         else if (*ch=='.')

         {

             boo = ;

         }

         ch++;

     }

     if (positive) return ans; else return -ans;

 }

 int main()

 {

     char str[];

     int n, i, tail = ;

     float ans[];

     int boo = ;

     gets(str);

     n = strlen(str) - ;

     while (n >= )

     {

         if ( contain(str[n]) )

         {

             if (tail < ) { exception(); }

             else

             {

                 ans[tail-] = calc(ans[tail-], ans[tail-], str[n]);

                 tail--;

                 n = n - ;

             }

         }

         else if (str[n] != ' ')

         {

             while (str[n]!=' ' && n>=) n--;

             ans[tail++] = str2flo(str+n+);

             n--;

         }

         else n--;

     }

     if (tail == )

     {

         printf("%.1f", ans[]);

     }

     else { exception(); }

     return ;

 }

巴特西

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

最新文章

热门文章