程序设计能力实训

1237. 链表运算

单点时限: 2.0 sec

内存限制: 256 MB

运算符前置的算术表达式则称为波兰式。例如普通的表达式 2 + 3 的波兰式为:+ 2 3。波兰式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序。

例如:(2.5+3)(-4) 的波兰式为: + 2.5 3 -4,而 5-6*7 的波兰式为:- 5 * 6 7。

现给定一个用单向链表存贮的波兰式,其节点以字符串形式存放运算符和运算数。运算符包括+,-,*,/ 四种,运算数是浮点数,每个运算数的宽度不超过 10。测试数据保证除法运算的除数不等于 0。

要求定义函数 Evaluate 计算一个表达式的值。

例如:波兰式 * + 2.5 3 -4 的存贮为:

Evaluate 的返回值为-22。

结构体类型 NODE 表示一个单向链表的节点定义。

输入格式

第 1 行:整数 $T$ ($1 \le T \le 10$) 为问题数。

第 2∽T+1 行:每一个问题一行数据(数据的意义不在这里描述)。

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等),然后在一行中输出相关数据(数据的意义不在这里描述)。

样例

Input
3
3 2 +
-4 3 2.5 + *
7 6 * 5 -
Output
case #0:
5.00
case #1:
-22.00
case #2:
-37.00

提示

stdlib.h 中的函数 atof 把一个字符串转换成一个浮点数。

// ********** Specification of the structure **********
typedef struct Node { char value[100]; struct Node *next; }NODE;
/*/////////////////////////////////////////////////////*/
double Evaluate(NODE *expr)
/* PreCondition:
expr is the head pointer of a linked-list, which represents a
Poland expression
PostCondition:
return value of the expression
*/
{ //TODO: your definition
}
/*/////////////////////////////////////////////////////*/
/***************************************************************/
/*                                                             */
/*  DON'T MODIFY following code anyway!                        */
/*                                                             */
/***************************************************************/
#include <stdio.h>
#include <stdlib.h>
NODE *input()
{ NODE *h=0,*p;
do { p=(NODE*)malloc(sizeof(NODE)); scanf("%s",p->value); p->next=h; h=p; }
while (getchar()!='\n');
return h;
}
int main()
{  int i,t; scanf("%d\n",&t);
for (i=0;i<t;i++) printf("case #%d:\n%.2f\n",i,Evaluate(input()));
return 0;
}
不限期开放

题目列表