题目大意： 给一棵递归树，看链接图片，从根节点开始对于每个节点往它的子节点移动，直到叶子节点停止。每个节点选哪一个孩子节点继续往下走是随机的(等概率)。然后叶子节点都会标记一个数值，记为走到该节点的得分。
输入条件：先输入整数n(n=0时结束),接下来有n行(n <= 26)，每一行会为前n个小写字母(每个字母作为一个变量)的描述。如a = (1 b)表示 f(a) = 1/2 * (1 + f(b))其中f(x)为x节点的得分期望。
现在对n个小写字母表示的变量节点，求出那个节点的得分期望即f(x) (x=a,b,c ...)。
这个题相当有意思，有意思在于它的输入——基于某个字符集的语义分析。递归向下分析的策略，而且是非常典型LL(1)文法！
S -> XWEWT
X -> (X)|a|b|c|...|z
E -> '='
W -> {Blank}|空
T -> (U)
U -> T|X|I
U -> UwU
w -> {Blank}
I -> [+|-]{Digit}+[.{Digit}]
这道题另外一个关键点是将T转化成方程式，然后综合这n个方程式，使用gauss消元求解。
gauss消元其实就是线性代数中，化简行列式然后进行求解。不会的亲们回去好好看看线性代数的书，不要看网上某些人写的不清不楚的报告。
只是有一点需要注意：计算机中的数字是有界的，要时刻注意数字边界问题！
还有，很多事情需要自己亲身实践，我贡献了很多次WA，一个大原因是听人家要排除输出"-0.000"的问题。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
int alpha[]={},n;
int getint(char *mes){
int i=;
while(mes[i]!='\0' && (mes[i]<'' || mes[i]>'')) i++;
return atoi(mes+i);
}
struct equation{
double ec[];
equation(){ for(int i=;i<;i++) ec[i]=; }
equation operator+(const equation & S){ equation E; for(int i=;i<;i++) E.ec[i]= ec[i]+S.ec[i]; return E; }
equation operator+=(const equation & S){ for(int i=;i<;i++) ec[i]+=S.ec[i]; return *this; }
equation operator*(double rat){ equation E; for(int i=;i<;i++) E.ec[i]= ec[i]*rat; return E; }
void print(){ for(int i=;i<n-;i++) printf("%f*%c + ",ec[i],i+'a'); printf("%f*%c = %f\n",ec[n-],n-+'a',ec[]); }
};
char mes[]; int idx;
equation getEquation(){
equation E;
if(mes[idx] == '('){
queue<equation> que; idx++;
while(){
while(!alpha[mes[idx]]) idx++; //跳到下一个合法字母
if(mes[idx]==')') break;
que.push(getEquation());
} idx++;
double quesize=1.0/que.size();
while(!que.empty()) E += que.front()*quesize, que.pop();
}else if(mes[idx]>=''&&mes[idx]<='' || mes[idx]=='-' || mes[idx]=='+'){
double t=,sign=;
if(mes[idx]=='-' || mes[idx]=='+'){
if(mes[idx]=='-') sign=-;
idx++;
}
while(mes[idx]>=''&&mes[idx]<=''){
t = t* + mes[idx]-'';
idx++;
}
if(mes[idx]=='.'){
double tt=0.1; idx++;
while(mes[idx]>=''&&mes[idx]<=''){
t += tt*(mes[idx]-'');
tt *= 0.1; idx++;
}
}
//printf("t = %f, sign = %f\n",t,sign);
E.ec[]=t*sign;
}else { // 'a' ---- 'z'
E.ec[mes[idx]-'a']=;
idx++;
}
while(!alpha[mes[idx]]) idx++; //跳到下一个合法字母
return E;
}
equation parse(){
while(mes[idx]<'a' || mes[idx]>'z') idx++;
int c=mes[idx]-'a';
while(mes[idx]!='=') idx++; idx++;
while(!alpha[mes[idx]]) idx++; //跳到下一个合法字母
equation E = getEquation();
E.ec[]=-E.ec[];
E.ec[c]-=;
return E;
}
double mat[][];
int setted[],rid[];
const double zero=1e-;
void unset(int x){
if(!setted[x]) return;
setted[x]=;
for(int i=x-;i>=;i--)
if(fabs(mat[i][x]) > zero)
unset(i);
}
void gauss(){
memset(setted,-,sizeof(setted));
for(int r=;r<n;r++){
int c=r;
int nonzero=-; double minv=1e99;
for(int i=c;i<n;i++)
if(fabs(mat[i][c]) > zero && fabs(mat[i][c]-) < minv)
nonzero=i, minv=mat[i][c];
if(nonzero < ) unset(r);
else {
double rat=/mat[nonzero][c];
for(int i=c;i<=n;i++) mat[nonzero][i] *= rat, swap(mat[nonzero][i],mat[r][i]);
for(int i=;i<n;i++)
if(i!=r && fabs(mat[i][c]) > zero){
rat = mat[i][c];
for(int j=c;j<=n;j++)
mat[i][j] -= rat*mat[r][j];
}
}
}
}
int main()
{
// init the legal alpha
for(int i='';i<='';i++) alpha[i]=;
for(int i='a';i<='z';i++) alpha[i]=;
alpha['.']=; alpha['(']=; alpha[')']=;
alpha['+']=; alpha['-']=;
// main logic
int game=;
do {
gets(mes); n=getint(mes);
if(n <= ) break;
for(int i=;i<n;i++){
gets(mes); idx=;
equation E = parse();
//E.print();
for(int j=;j<;j++)
mat[i][j]=E.ec[j];
}
for(int j=;j<n;j++)
mat[j][n]=mat[j][];
printf("Game %d\n",game++);
gauss();
for(int j=;j<n;j++)
if(setted[j]) {
/* 排除输出 -0.000 的问题， 这里多余了
int tt=0;
for(int i=0;i<n;i++){
sprintf(mes,"%.3f",mat[j][n]);
tt=0;
if(memcmp("-0.000",mes,5)==0) tt=1;
printf("Expected score for %c = %s\n",j+'a',mes+tt);
}
*/
printf("Expected score for %c = %.3f\n",j+'a',mat[j][n]);
}
else printf("Expected score for %c undefined\n",j+'a');
puts("");
}while();
return ;
}