英文:
Repeat String in braces n times
问题
我有一个输入字符串，形式为"(x5(y8)2)4"。
假设x和y是不同的函数，我要么调用它们'n'次，要么展开括号以创建一个新的字符串，我可以用它来调用这些函数。
示例1：
输入：(x5(y8)2)4
输出：x5y8y8x5y8y8x5y8y8x5y8y8
示例2（更复杂）：
输入：(((x1)3x2)4y5)2z5
输出：x1x1x1x2x1x1x1x2x1x1x1x2x1x1x1x2y5x1x1x1x2x1x1x1x2x1x1x1x2x1x1x1x2y5z5
英文:
I have an input String in the form "(x5(y8)2)4"
Let's say x and y are separate functions, I either want to call them 'n' times, or expand the brackets to create a new String that I can use to call the functions.
Example 1:
Input: (x5(y8)2)4
Output: x5y8y8x5y8y8x5y8y8x5y8y8
Example 2 (more complex):
Input: (((x1)3x2)4y5)2z5
Output: x1x1x1x2x1x1x1x2x1x1x1x2x1x1x1x2y5x1x1x1x2x1x1x1x2x1x1x1x2x1x1x1x2y5z5
Thanks
答案1
得分: 0
你可以将树解析成树型数据结构。树中的每个节点都有多个子节点。一个节点可以是叶子节点（没有子节点的节点），例如变量 x5，或者可以是带有子节点的节点，表示一个“数学”函数。
你的第一个示例中的树可能是这样的：
根节点 [NODE]：
root的子节点 * 4
Root的子节点 [NODE]：
child_of_root的第一个子节点 + child_of_root的第二个子节点
Child_of_Root的第一个子节点 [LEAF]：
x5
Child_of_Root的第二个子节点 [NODE]：
child_of_2_child_of_child_of_root的子节点 * 2
Child_of_2_Child_of_Child_of_Root的子节点 [LEAF]：
y8
要将输入字符串解析成树结构，你需要分析 ( 和 ) 的设置，以及是否通过因子来“乘法”和添加其他内容，例如 (x5 "＋" (y8) "×" 2)。这可能会变得相当复杂。（也许你可以使用堆栈？但是，我确信有相关的教程可供参考）。
在创建了输入的树表示后，计算输出字符串相对来说是相对简单的。创建一个类似于下面这样的递归算法：
String getResult() {
if (this == NODE) {
return calculate(MY_NODE_CHILDREN.getResult());
} else if (this == LEAF) {
return VARIABLE;
}
}
这是伪代码！
calculate 函数应该根据上下文，将子节点的字符串结果相加，乘以一个因子，或者不执行任何操作。
如果你从根节点调用这个递归函数，正确的结果应该会得出。
英文:
You could parse the tree to a tree-data-structure. Each node in the tree in the has a number of children nodes. A node could either be a leaf (which is a node without children) - so for example a variable x5 - or it could be a node (with children nodes) which represents a "mathematical" function.
The tree from your first example could look like this.
Root [NODE]:
child_of_root * 4
Child_of_Root [NODE]:
1_child_of_child_of_root + 2_child_of_child_of_root
1_Child_of_Child_of_Root [LEAF]:
x5
2_Child_of_Child_of_Root [NODE]:
child_of_2_child_of_child_of_root * 2
Child_of_2_Child_of_Child_of_Root [LEAF]:
y8
To parse your input-string to the tree-structure you have to analyse how the ( and ) are set and if you "multiply" those by a factor and if you add other stuff - (x5 "+" (y8) "*" 2). This could get quite complicated. (Maybe you could use stacks? However, I'm sure there are tutorials out there).
After you created your tree-representation of your input, it is relatively simple to calculate your output string. Create a recursive algorithm similar to this:
String getReult() {
if(this == NODE) {
return calculate(MY_NODE_CHILDREN.getResult());
}else if(this == LEAF) {
return VARIABLE;
}
}
This is pseudo-code!
The calculate function should add the children string results, multiply them by a factor or do nothing, depending on a context.
If you call your recursive function at the root, the correct result should pop out.
专注分享java语言的经验与见解，让所有开发者获益！
评论