单点时限: 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:
等),然后在一行中输出相关数据(数据的意义不在这里描述)。
3 3 2 + -4 3 2.5 + * 7 6 * 5 -
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;
}