




'''simple docstring'''





import functools
from math import sqrt
from time import time


def 				UpperCamelCase	(  snake_case	,     *snake_case	,     **snake_case   ):




   '''simple docstring'''

   SCREAMING_SNAKE_CASE__			:				Optional[int]       						= time()
   SCREAMING_SNAKE_CASE__			:				str       						= func(*snake_case	,     **snake_case   )
   SCREAMING_SNAKE_CASE__			:				Optional[int]       						= time()
   if int(end - start   ) > 0:
      print(f"""{func.__name__} runtime: {(end - start):0.4f} s"""   )
   else:
      print(f"""{func.__name__} runtime: {(end - start) * 10_00:0.4f} ms"""   )
   return output


def 				UpperCamelCase	(  snake_case   ):




   '''simple docstring'''

   if n < 0:
      raise Exception('''n is negative'''   )
   if n == 0:
      return [0]
   SCREAMING_SNAKE_CASE__			:				Tuple       						= [0, 1]
   for _ in range(n - 1   ):
      fib.append(fib[-1] + fib[-2]   )
   return fib


def 				UpperCamelCase	(  snake_case   ):




   '''simple docstring'''

   def fib_recursive_term(snake_case   ) -> int:
      if i < 0:
         raise Exception('''n is negative'''   )
      if i < 2:
         return i
      return fib_recursive_term(i - 1   ) + fib_recursive_term(i - 2   )

   if n < 0:
      raise Exception('''n is negative'''   )
   return [fib_recursive_term(snake_case   ) for i in range(n + 1   )]


def 				UpperCamelCase	(  snake_case   ):




   '''simple docstring'''

   @functools.cache
   def fib_recursive_term(snake_case   ) -> int:
      if i < 0:
         raise Exception('''n is negative'''   )
      if i < 2:
         return i
      return fib_recursive_term(i - 1   ) + fib_recursive_term(i - 2   )

   if n < 0:
      raise Exception('''n is negative'''   )
   return [fib_recursive_term(snake_case   ) for i in range(n + 1   )]


def 				UpperCamelCase	(  snake_case   ):




   '''simple docstring'''

   if n < 0:
      raise Exception('''n is negative'''   )
   # Cache must be outside recursuive function
   # other it will reset every time it calls itself.
   SCREAMING_SNAKE_CASE__			:				dict[int, int]       						= {0: 0, 1: 1, 2: 1}  # Prefilled cache

   def rec_fn_memoized(snake_case   ) -> int:
      if num in cache:
         return cache[num]

      SCREAMING_SNAKE_CASE__			:				Tuple       						= rec_fn_memoized(num - 1   ) + rec_fn_memoized(num - 2   )
      SCREAMING_SNAKE_CASE__			:				int       						= value
      return value

   return [rec_fn_memoized(snake_case   ) for i in range(n + 1   )]


def 				UpperCamelCase	(  snake_case   ):




   '''simple docstring'''

   if n < 0:
      raise Exception('''n is negative'''   )
   if n >= 14_75:
      raise Exception('''n is too large'''   )
   SCREAMING_SNAKE_CASE__			:				int       						= sqrt(5   )
   SCREAMING_SNAKE_CASE__			:				List[Any]       						= (1 + sqrt_a) / 2
   return [round(phi**i / sqrt_a   ) for i in range(n + 1   )]


if __name__ == "__main__":
       lowercase__			=	3_0
       time_func(fib_iterative, num)
       time_func(fib_recursive, num)  # Around 3s runtime
       time_func(fib_recursive_cached, num)  # Around 0ms runtime
       time_func(fib_memoization, num)
       time_func(fib_binet, num)







'''simple docstring'''





lowercase__			=	{
    '''+''': lambda x, y: x + y,
    '''-''': lambda x, y: x - y,
    '''*''': lambda x, y: x * y,
    '''/''': lambda x, y: x / y,
}


def 				UpperCamelCase	(  snake_case   ):




   '''simple docstring'''

   return c.isdigit()


def 				UpperCamelCase	(  snake_case   ):




   '''simple docstring'''

   SCREAMING_SNAKE_CASE__			:				Union[str, Any]       						= []

   # iterate over the string in reverse order
   for c in expression.split()[::-1]:
      # push operand to stack
      if is_operand(snake_case   ):
         stack.append(int(snake_case   )   )

      else:
         # pop values from stack can calculate the result
         # push the result onto the stack again
         SCREAMING_SNAKE_CASE__			:				Dict       						= stack.pop()
         SCREAMING_SNAKE_CASE__			:				Any       						= stack.pop()
         stack.append(calc[c](snake_case	,     snake_case   )   )

   return stack.pop()


# Driver code
if __name__ == "__main__":
       lowercase__			=	'''+ 9 * 2 6'''
       print(evaluate(test_expression))

       lowercase__			=	'''/ * 10 2 + 4 1 '''
       print(evaluate(test_expression))

