Appleby Contest '19 P3 - A Recursion Problem

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type

There are many ways to represent arithmetic expressions.

We commonly use infix notation where operations are put in between values (i.e. 1+2 \times 3=7), but another less well-known method is prefix notation. This is where operations are put before values. For example, if we want to add two numbers we would write + x y instead of x + y. Furthermore, brackets are used to enforce order of evaluation.

The formal definition of prefix notation we will be using is as any one of the following options:

  • x, where x is an integer.
  • (+ x y), where x and y are valid prefix notation expressions. The result of this expression is x+y.

Your objective today is to evaluate prefix notation expressions that only involve addition.

Input Specification

The first and only line of input contains a valid prefix notation expression. You can expect the expression to only consist of the following characters: 0123456789()+- (and the space:  )

Output Specification

The value of that expression.

Constraints

Any integer x in the given expression will satisfy the following inequality: -10^4 \le x \le 10^4.

1 \le |s| \le 10^5, where |s| denotes the length of the prefix notation expression.

Sample Input

(+ 1 (+ (+ (+ 3 4) -2) 5))

Sample Output

11

Sample Explanation

Here is the sample input being simplified:

  • (+ 1 (+ (+ (+ 3 4) -2) 5))
  • (+ 1 (+ (+ 7 -2) 5))
  • (+ 1 (+ 5 5))
  • (+ 1 10)
  • (11)
  • 11

Comments


  • 0
    KevinLyu1006  commented on Aug. 12, 2021, 7:17 p.m.

    I like how the input specification says that the input will only consist of “ 0123456789()+”, yet the sample input has a “-“.


    • 0
      Plasmatic  commented on Aug. 13, 2021, 11:55 p.m.

      fixed


  • 1
    Spitfire720  commented on Feb. 22, 2021, 11:52 a.m.

    I like how the title says its a recursion problem but literally none of the answers use recursion


  • 0
    Lost  commented on Feb. 14, 2021, 12:02 p.m.

    I kept getting a WA on the second test case because the input was simply just an integer. Don't forget to add a test case for this.


  • 0
    nikos  commented on Oct. 17, 2020, 7:00 p.m. edited

    If you got this problem in brain**, I have respect for you.


  • 0
    vishnus  commented on June 19, 2020, 10:23 a.m. edited

    My solution is showing "MemoryError" for almost all of the methods I try. For some other methods, it may show different errors, but the consistent pattern is that the first two inputs show AC and the next one fails for some reason. I am using Python 3.

    Edit: Nevermind, it was probably the eval() I was using...