思路：递归

因为子树必定是(...)num(...)或者空子树,所以可以记录左括号个数，中途让右括号消去左括号，遇到数字时左括号数量+1就是深度。

计算权值可以使用双指针计算 右指针一直往右遍历 直到遇到非数字字符 循环结束

将每一位累加即可

我们可以使用迭代的方式替代递归，下面是迭代的代码。

题目内容

二叉树按以下规则进行字符串编码序列化存储：

1. 如果当前树为空，则表示为X;
2. 如果当前树不为空，则表示为(left_sub_tree)current_value(right_sub_tree);
   1. left_sub_tree:左子树按此规则序列化后得到的字符串
   2. right sub_tree:右子树按此规则序列化后得到的字符串

请编写代码实现从输入的字符串反序列化出对应的二叉树结构，并输出 所有结点的 深度*权值 之和. 根的深度定义为1

输入描述

输入字符串编码的二叉树

输出描述

深度*权值之和

示例1

输入

((X)2(X))1(((X)4(X))3((X)2(X)))

输出

29

说明

字符串长度不超过$100000$.保证给定的字符串形成一个合法的二叉树。

$1 \leq current\_value \leq 10000$