首页 > 代码库 > 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前缀式计算
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。