首页 > 代码库 > NYOJ128前缀式计算

NYOJ128前缀式计算

前缀式计算

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
 
描述

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

如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.00
    5.53  

这个题目也是用栈来做的,只不过顺序与后缀式有点不同,他与中缀的区别是可以不用比较优先级,
因为前缀和后缀式中都没有括号,直接按照顺序计算就行了,下面是具体的实现代码,代码中有注释,
如有不懂的,可以留言…

  1 #include <stdio.h>  2 #include <string.h>  3 #include <stdlib.h>  4 #include <math.h>  5 typedef struct stack{  6     double data;  7     struct stack *next;  8 }stack;  9 stack *init(); 10 int isOperand(char ch); 11 stack *push_stack(stack *top, double data); 12 stack *pop_stack(stack *top); 13 void calc(stack **top, char ch); 14 int main() 15 { 16     char ch[5001], temp[1000]; 17     stack *top; 18     top = init(); 19     double num; int i, count, flag, j; 20     while(gets(ch) != NULL) 21     { 22         i = strlen(ch) - 1; 23         while(i >= 0) 24         { 25             if(ch[i] ==  )//判断如果是空格,继续下一个 26             { 27                 i --; 28                 continue; 29             } 30             if(isOperand(ch[i]))//如果是运算符,这是调用计算函数 31             { 32                 calc(&top, ch[i]); 33                 i --; 34                 continue; 35             } 36             count = 0; flag = 1; j = 0; 37             while(!isOperand(ch[i]) && ch[i] !=   && i >= 0)//判断是数字的话就保存到一个新的数组中 38             { 39                 temp[j++] = ch[i]; 40                 i --; 41             } 42             j = j -1; 43             num = 0; 44             while(j >= 0)//将字符串解析成double类型数字 45             { 46  47                 if(temp[j] == .) 48                 { 49                     flag = 0; 50                     j --; 51                     continue; 52                 } 53                 if(flag) 54                     num = num * 10 + (temp[j] - 0);//如果没出现小数点之前,都是*10 + 本身的 55                 else 56                 { 57                     count ++; 58                     num += pow(0.1, count) * (temp[j] - 0);//出现小数点之后就得加上0.1的count此方了 59                 } 60                 j --; 61             } 62             top = push_stack(top, num); 63         } 64         printf("%.2f\n", top -> data); 65     } 66     return 0; 67 } 68 stack *init()//初始化栈 69 { 70     stack * node; 71     node = (stack *)malloc(sizeof(stack)); 72     node -> next = NULL; 73     return node; 74 } 75 int isOperand(char ch)//判断是不是运算符 76 { 77     if(ch == + || ch == - || ch == * || ch == /) 78         return 1; 79     return 0; 80 } 81 stack *push_stack(stack *top, double data)//入栈 82 { 83     stack *node; 84     node = init(); 85     node -> data =http://www.mamicode.com/ data; 86     node -> next = top; 87     top = node; 88     return top; 89 } 90 stack *pop_stack(stack *top)//出栈 91 { 92     stack *node; 93     node = top; 94     top = top -> next; 95     free(node); 96     return top; 97 } 98 void calc(stack **top, char ch)//计算函数,当然也可以不用二级指针,把void改成stack返回类型  就行了 99 {100     double num1, num2;101     num1 = (*top) -> data;102     (*top) = pop_stack(*top);103     num2 = (*top) -> data;104     (*top) = pop_stack(*top);105     switch(ch)106     {107     case +:108         num1 = num1 + num2;109         break;110     case -:111         num1 = num1 - num2;112         break;113     case *:114         num1 = num1 * num2;115         break;116     case /:117         num1 = num1 / num2;118         break;119     }120     (*top) = push_stack(*top, num1);//计算完之后将结果继续入栈121 }

 

 

NYOJ128前缀式计算