描述

先说明一下什么是中缀式：

如2+(3+4)*5这种我们最常见的式子就是中缀式。

而把中缀式按运算顺序加上括号就是：(2+((3+4)*5))

然后把运算符写到括号前面就是+(2 *( +(3 4) 5) )

把括号去掉就是：+ 2 * + 3 4 5

最后这个式子就是该表达式的前缀表示。

给你一个前缀表达式，请你计算出该前缀式的值。

比如：

+ 2 * + 3 4 5的值就是 37

输入

有多组测试数据，每组测试数据占一行，任意两个操作符之间，任意两个操作数之间，操作数与操作符之间都有一个空格。输入的两个操作数可能是小数，数据保证输入的数都是正数，并且都小于10，操作数数目不超过500。
以EOF为输入结束的标志。

输出

对每组数据，输出该前缀表达式的值。输出结果保留两位小数。

样例输入

+ 2 * + 3 4 5+ 5.1 / 3 7

样例输出

37.005.53


前缀式计算：从后往前遍历，遇到数字压入栈，遇到符号，弹出两个数字，计算

（第一个操作数为先出栈的数），然后压入栈。

  1 #include<stdio.h>  2 #include<string.h>  3 #include<stack>  4 using namespace std;  5 double calPerfix(char *input)  6 {  7     stack<double> result;  8     int len = strlen(input) - 1;  9     int n,j,i; 10     while (len >= 0) 11     { 12         j = len; 13         double sum = 0.0,dot = 0.0; 14         if (len == 0){ 15             j = 0; 16             n = j; 17         } 18         else { 19             while (input[j] != ‘ ‘) 20                 j--; 21             n = j+1; 22         } 23         if (input[n] >= ‘0‘ && input[n] <= ‘9‘){ 24         for (i=n; i <= len; i++) 25         { 26             if(input[i] >= ‘0‘ && input[i] <= ‘9‘) 27             { 28                 double num = input[i] - ‘0‘; 29                 sum = sum * 10 + num; 30             } 31             else if (input[i] == ‘.‘) 32             { 33                 int l = 10; 34                 dot = 0.0; 35                 for (int k=i+1; k <= len; k++ ) 36                 { 37                     if(input[k] >= ‘0‘ && input[k] <= ‘9‘) 38                     { 39                         double num = input[k] - ‘0‘; 40                         dot += num / l; 41                         l *= 10; 42                         i++; 43                     } 44                 } 45             } 46         } 47         sum += dot; 48         result.push(sum); 49         } 50         else { 51             double one; 52             switch (input[n]) 53             { 54             case ‘+‘: 55                 sum = result.top(); 56                 result.pop(); 57                 one = result.top(); 58                 result.pop(); 59                 sum += one; 60                 result.push(sum); 61                 break; 62             case ‘-‘: 63                 sum = result.top(); 64                 result.pop(); 65                 one = result.top(); 66                 result.pop(); 67                 sum -= one; 68                 result.push(sum); 69                 break; 70             case ‘*‘: 71                 sum = result.top(); 72                 result.pop(); 73                 one = result.top(); 74                 result.pop(); 75                 sum *= one; 76                 result.push(sum); 77                 break; 78             case ‘/‘: 79                 sum = result.top(); 80                 result.pop(); 81                 one = result.top(); 82                 result.pop(); 83                 sum /= one; 84                 result.push(sum); 85                 break; 86             default: 87                 break; 88             } 89         } 90         len = j - 1; 91     } 92     return result.top(); 93 } 94 int main() 95 { 96     char input[10000]; 97     while(gets(input)){ 98         printf("%.2f\n",calPerfix(input)); 99         fflush(stdin);100     }101     return 0;102 }

 

NYOJ 128 前缀式计算