<small id='j7XLr'></small><noframes id='j7XLr'>

    <bdo id='j7XLr'></bdo><ul id='j7XLr'></ul>
<i id='j7XLr'><tr id='j7XLr'><dt id='j7XLr'><q id='j7XLr'><span id='j7XLr'><b id='j7XLr'><form id='j7XLr'><ins id='j7XLr'></ins><ul id='j7XLr'></ul><sub id='j7XLr'></sub></form><legend id='j7XLr'></legend><bdo id='j7XLr'><pre id='j7XLr'><center id='j7XLr'></center></pre></bdo></b><th id='j7XLr'></th></span></q></dt></tr></i><div id='j7XLr'><tfoot id='j7XLr'></tfoot><dl id='j7XLr'><fieldset id='j7XLr'></fieldset></dl></div>
    1. <legend id='j7XLr'><style id='j7XLr'><dir id='j7XLr'><q id='j7XLr'></q></dir></style></legend>
    2. <tfoot id='j7XLr'></tfoot>

        如何在 JavaScript 中将自下而上的递归算法转换为迭代堆栈

        How to convert bottom-up recursive algorithm to iterative stack in JavaScript(如何在 JavaScript 中将自下而上的递归算法转换为迭代堆栈)
          <tbody id='yzJKh'></tbody>

          <legend id='yzJKh'><style id='yzJKh'><dir id='yzJKh'><q id='yzJKh'></q></dir></style></legend>
          • <bdo id='yzJKh'></bdo><ul id='yzJKh'></ul>
            <i id='yzJKh'><tr id='yzJKh'><dt id='yzJKh'><q id='yzJKh'><span id='yzJKh'><b id='yzJKh'><form id='yzJKh'><ins id='yzJKh'></ins><ul id='yzJKh'></ul><sub id='yzJKh'></sub></form><legend id='yzJKh'></legend><bdo id='yzJKh'><pre id='yzJKh'><center id='yzJKh'></center></pre></bdo></b><th id='yzJKh'></th></span></q></dt></tr></i><div id='yzJKh'><tfoot id='yzJKh'></tfoot><dl id='yzJKh'><fieldset id='yzJKh'></fieldset></dl></div>

                  <tfoot id='yzJKh'></tfoot>

                1. <small id='yzJKh'></small><noframes id='yzJKh'>

                  本文介绍了如何在 JavaScript 中将自下而上的递归算法转换为迭代堆栈的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着跟版网的小编来一起学习吧!

                  问题描述

                  给定以下算法:

                  console.log(JSON.stringify(create(0), null, 2))
                  
                  function create(i) {
                    if (i == 5) return
                    return new Klass(i, create(i + 1), create(i + 1))
                  }
                  
                  function Klass(i, l, r) {
                    this.i = i
                    this.l = l
                    this.r = r
                  }

                  它在create(0) last中创建Klass,递归地创建所有的孩子.所以它首先创建叶节点,然后将其传递给父节点,等等.

                  It creates the Klass in create(0) last, after creating all the children, recursively. So it creates the leaf nodes first, then passes that up to the parent, etc.

                  想知道如何使用没有递归的堆栈来做到这一点.让我头疼:).我了解如何使用堆栈从自上而下创建,而不是自下而上.对于自上而下,本质上是这样的:

                  Wondering how to do this using a stack without recursion. Making my head hurt :). I understand how to use a stack to create from the top-down, but not the bottom up. For top-down, it's essentially this:

                  var stack = [0]
                  while (stack.length) {
                    var i = stack.pop()
                    // do work
                    stack.push(children)
                  }
                  

                  自下而上,我看不出它应该如何工作.这就是我卡住的地方:

                  From the bottom up, I can't see how it should work. This is where I get stuck:

                  function create(i) {  
                    var stack = []
                    stack.push([i, 'open'])
                    stack.push([i, 'close'])
                  
                    while (stack.length) {
                      var node = stack.pop()
                      if (node[1] == 'open') {
                        stack.push([ node[0] + 1, 'open' ])
                        stack.push([ node[0] + 1, 'close' ])
                      } else {
                        // ?? not sure how to get to this point
                        var klass = new Klass(node[0], node[2], node[3])
                        // ??
                      }
                    }
                  }
                  

                  推荐答案

                  将任何递归代码机械地转换为堆栈机器并非易事.自动状态转换会产生非常复杂的代码,想想 C#-s 或 BabelJS-s 生成器.但可以肯定的是,它可以完成,但您将需要可变堆栈帧和/或寄存器.让我们看看我们面临的问题:

                  It's not trivial to mechanically transform any recursive code into a stack machine. Automatic stateful transformations produce very complex code, just think of C#-s or BabelJS-s generators. But sure, it can be done, but you will need mutable stackframes and/or registers. Let's see the problems we are facing:

                  我们必须在堆栈本身上存储一些状态变量/指令指针.这就是您使用 "open""close" 标记模拟的内容.

                  We have to store some state variable/instruction pointer on the stack itself. This is what you are emulating with the "open" and "close" markers.

                  有很多方法:

                  • 将其存储在临时寄存器中
                  • 向函数传递对字段的引用((对象,字段名)对),模拟 out 参数
                  • 像@CtheSky 那样使用第二个堆栈

                  使用可变堆栈帧和结果寄存器,转换后的代码如下所示:

                  Using mutable stack frames and a result register the transformed code would look something like this:

                  console.log(JSON.stringify(create(0), null, 2))
                  
                  function Klass(i, l, r) {
                    this.i = i
                    this.l = l
                    this.r = r
                  }
                  
                  function Frame(i) {
                    this.ip = 0;
                    this.i = i;
                    this.left = null;
                  }
                  
                  function create(i) {
                    var result;
                    var stack = [new Frame(i)];
                    while (stack.length > 0) {
                      var frame = stack[stack.length - 1];
                      switch (frame.ip) {
                        case 0:
                          if (frame.i === 5) {
                            result = undefined;
                            stack.pop();
                            break;
                          }
                          stack.push(new Frame(frame.i + 1));
                          frame.ip = 1;
                          break;
                        case 1:
                          frame.left = result;
                          stack.push(new Frame(frame.i + 1));
                          frame.ip = 2;
                          break;
                        case 2:
                          result = new Klass(frame.i, frame.left, result);
                          stack.pop();
                          break;
                      }
                    }
                    return result;
                  }

                  这篇关于如何在 JavaScript 中将自下而上的递归算法转换为迭代堆栈的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持跟版网!

                  本站部分内容来源互联网,如果有图片或者内容侵犯了您的权益,请联系我们,我们会在确认后第一时间进行删除!

                  相关文档推荐

                  Rails/Javascript: How to inject rails variables into (very) simple javascript(Rails/Javascript:如何将 rails 变量注入(非常)简单的 javascript)
                  CoffeeScript always returns in anonymous function(CoffeeScript 总是以匿名函数返回)
                  Ordinals in words javascript(javascript中的序数)
                  getFullYear returns year before on first day of year(getFullYear 在一年的第一天返回前一年)
                  How do I make a TextGeometry multiline? How do I put it inside a square so it wraps like html text does inside a div?(如何制作 TextGeometry 多线?如何将它放在一个正方形内,以便它像 html 文本一样包裹在 div 内?) - IT屋-程序员软件开发技术分享社
                  How to use coffeescript in developing web-sites?(如何在开发网站时使用coffeescript?)
                    <tbody id='YTnO1'></tbody>

                        <i id='YTnO1'><tr id='YTnO1'><dt id='YTnO1'><q id='YTnO1'><span id='YTnO1'><b id='YTnO1'><form id='YTnO1'><ins id='YTnO1'></ins><ul id='YTnO1'></ul><sub id='YTnO1'></sub></form><legend id='YTnO1'></legend><bdo id='YTnO1'><pre id='YTnO1'><center id='YTnO1'></center></pre></bdo></b><th id='YTnO1'></th></span></q></dt></tr></i><div id='YTnO1'><tfoot id='YTnO1'></tfoot><dl id='YTnO1'><fieldset id='YTnO1'></fieldset></dl></div>
                          <bdo id='YTnO1'></bdo><ul id='YTnO1'></ul>
                            <tfoot id='YTnO1'></tfoot>
                          • <small id='YTnO1'></small><noframes id='YTnO1'>

                          • <legend id='YTnO1'><style id='YTnO1'><dir id='YTnO1'><q id='YTnO1'></q></dir></style></legend>