Search Nodes in a Binary Tree

Assignment

Let T be an unempty general rooted binary tree in which each node contains one integer key. We say that a node N in T is a so called search node if one of the following conditions holds:

N is a leaf.
N has only left child L and the key of L is less than the key of N.
N has only right child R and the key of N is less than the key of R.
N has left child L and right child R and the key of L is less than the key of N which is less than the key of R.

Binary tree coding

Any binary tree which nodes contain a single key can be coded by a string composed only of parentheses and key values. We define the code of the tree recursively as follows (the quotation marks are not part of the defined string):

An empty tree is coded by empty string "".
A tree with a single node is coded by the string “(A)”, where A is the string representation of the root’s key.
A tree with more than one node is coded by the string “(ABC)” where A is the code of the left subtree of the root, B is the string representation of the root’s key and C is the code of the right subtree of the root.

For example, a balanced binary search tree containing keys 1, 2, 3, 4, 5, 6, 7 is coded as “(1)2(345)6(7)”.
Note that the order in which the keys appear in the code is identical with the order produced by the Inorder traversal of the tree.

Image 1. A binary tree with its search nodes depicted in dark blue. The tree code is “5070(80(40)60))”. The tree is an illustration of Example 1 bellow.

The task

You are given a binary tree in its coded form. Find the number of search nodes in this tree.

Technical hint
To analyse small examples you may utilise a suitable programmer’s editor which highlights matching brackets in the code. When you paste the tree code into the editor then the highlighted matching brackets indicate the extent of a particular subtree in the tree code.

Input

There is a single input line. It contains the code of a binary tree. The keys in the tree are all positive and less than 10000. The line contains only left and right round parentheses and digits 0, 1, …, 9 and no other symbols.
The number of the nodes in the tree does not exceed 10⁶.

Output

The output contains one text line with one integer representing the total number of search nodes in the given tree.

Examples

Example 1

Input

(((10)40((25)30(35)))50((70(80(40)))60))

Output

     ________50________
   __40____    ______60
   10  __30__  70__
       25  35    80__
                   40

Scheme 1. The tree in Example 1. The search nodes are also depicted in Image 1.

Example 2

Input

(((70)60(50))40((30)20(10)))

Output

     ____40____
   __60__  __20__
   70  50  30  10

Scheme 2. The tree in Example 2.

Example 3

Input

(((((20)12(14((((12)15)19)10(14))))16(17(((11)18)20(14(10)))))10(((10(16))19)18(19(20(17(17))))))16((11)13))

Output

                                 __________________16____
                   ______________10________          __13
     ______________16__                __18__        11
   __12__            17______      ____19  19__
   20  14________        __20__    10__      20__
             __10__    __18  14__    16        17__
           __19  14    11      10                17
         __15
         12

Scheme 3. The tree in Example 3.

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

Public data