2013-06-13 07:28:53Morris
[UVA][遞迴] 11291 - Smeech
Problem B: Smeech
Professor Octastichs has invented a new programming language, Smeech. An expression in Smeech may be a positive or negative integer, or may be of the form (p e1 e2) where p is a real number between 0 and 1 (inclusive) and e1 and e2 are Smeech expressions. The value represented by a Smeech expression is as follows:- An integer represents itself
- With probability p, (p e1 e2) represents x+y where x is the value of e1 and y is the value of e2; otherwise it represents x-y.
Input consists of several Smeech expressions, one per line, followed by a line containing (). For each expression, output its expected value to two decimal places.
Sample Input
7 (.5 3 9) ()
Output for Sample Input
7.00 3.00
Gordon V. Cormack
題目描述：
類似於 BNF 表示法。
<E[x]> -> <Integer> | (p <E[x]> <E[x]>)
<Integer> -> #number
然後他說有 p 的機率表示 x+y, 1-p 的機率表示 x-y
即 E[X] = p*(e1+e2) + (1-p)*(e1-e2)
題目解法：
使用遞迴去剖析字串會比較方便好寫。
#include <stdio.h>
#include <string.h>
char s[10000];
int i;
double sol() {
if(s[i] != '(') {
double e;
sscanf(s+i, "%lf", &e);
while((s[i] <= '9' && s[i] >= '0') || s[i] == '-')
i++;
while(s[i] == ' ') i++;
return e;
}
double p, e1, e2;
sscanf(s+i, "(%lf", &p);
while(s[i] != ' ') i++;
i++;
e1 = sol();
e2 = sol();
while(s[i] != ')') i++;
i++;
while(s[i] == ' ') i++;
return p*(e1+e2) + (1-p)*(e1-e2);
}
int main() {
double p, e1, e2;
while(gets(s)) {
if(!strcmp(s, "()"))
break;
i = 0;
printf("%.2lf\n", sol());
}
return 0;
}