UVA 11291 Smeech

Description:

Professor Octastichs has invented a new pro-gramming language, Smeech. An expression in Smeech may be a positive or negative integer, or may be of the form (p e 1 e 2 ) where p is a real number between 0 and 1 (inclusive) and e 1 and e 2 are Smeech expressions.

The value represented by a Smeech expression is as follows:

• An integer represents itself
• With probability p, (p e 1 e 2 ) represents x+ y where x is the value of e 1 and y is the value of e 2 ; otherwise it represents x − y.

Given a Smeech expression, what is its expected value?

Input:

Input consists of several Smeech expressions, one per line, followed by a line containing ‘()’.

Output:

For each expression, output its expected value to two decimal places.

Sample Input:

7
(.5 3 9)
()

Sample Output:

7.00
3.00

题目链接

有一种编程语言可以是一个数，或者是(p e1 e2)形式，若一个数其结果即为自身，若(p e1 e2)结果有p可能性为e1+e2，其余为e1-e2，求期望。

2018ICPC徐州现场热身赛是UVA 11290-11293的原题，其中B是这道题，在现场题意理解错了，刚开始没有get到e1、e2也可能是(p e1 e2)形式，最后想到之后也没有上机实现。

期望很好求，(e1+e2)*p+(e1-e2)*(1-p)即为期望，因为e1、e2也可能是(p e1 e2)形式所以使用递归处理数据，由于数据按行输入，所以使用字符串读入，sscanf可以很方便的用来将字符串转换为数值。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

char Str[maxn], Convert[maxn];
int Cur;

double Read() {
	int Pos = 0;
	double Ans;
	while (isalnum(Str[Cur]) || Str[Cur] == '.' || Str[Cur] == '-') {
		Convert[Pos++] = Str[Cur++];
	}
	Convert[Pos] = '\0';
	sscanf(Convert, "%lf", &Ans);
	return Ans;
}

double Cal() {
	double P = 0.0, A = 0.0, B = 0.0;
	while (Str[Cur] == ' ') {
		Cur++;
	}
	if (Str[Cur] == '(') {
		Cur++;
		P = Read();
		A = Cal();
		B = Cal();
		if (Str[Cur] == ')') {
			Cur++;
			return (A + B) * P + (A - B) * (1.0 - P);
		}
	}
	else {
		return Read();
	}
}

int main(int argc, char *argv[]) {
	while (fgets(Str, maxn, stdin)) {
		if (Str[strlen(Str) - 1] == '\n') {
			Str[strlen(Str) - 1] = '\0';
		}
		if (!strcmp(Str, "()")) {
			break;
		}
		Cur = 0;
		printf("%.2lf\n", Cal());
	}
    return 0;
}