Smeech

Interview

Time limit1sMemory limit128 MB

Summary
Parse a prefix Smeech expression with probabilistic plus or minus operators and compute its expected value to two decimals.
Level

Easy3 of 10

Topics
Recursion, Math, Probability, Implementation
Solved
No attempts yet

Problem

Professor Octastichs has invented a new programming language called Smeech. A Smeech expression is one of the following:

  • a positive or negative integer, or
  • an expression of the form (p e1 e2), where p is a real number between 0 and 1 (inclusive) and e1, e2 are Smeech expressions.

The value represented by a Smeech expression is defined as follows:

  • An integer represents itself.
  • (p e1 e2) represents x + y with probability p, and x - y with probability 1 - p, where x is the value of e1 and y is the value of e2.

Each add-or-subtract choice is made independently. Given a Smeech expression, compute its expected value.

Input

The input contains several Smeech expressions, one per line, followed by a line containing (), which marks the end of the input.

Output

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

Examples1

  1. Example 1

    Input
    7
(.5 3 9)
()
    Expected output
    7.00
3.00