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