Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Page 1 of 2 12 LastLast
Results 1 to 15 of 16
  1. #1
    New Coder
    Join Date
    Dec 2012
    Posts
    10
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Question How to go through a table using recursivity?

    Hi guys, I need to convert a table of strings numbers (like 10x4+5x2+...) into one integer using recursivity.
    I need to change that kind of code:

    Code:
    for(var i=0; i<myArray.length; i++) { 
    myArray[i] = parseInt(myArray[i], 10);
    }
    for something using recursivity (no loops) to go through every entries of my table. Can you help me?

    (The code isn't complete, I know I have to use if charAt(i) == "x" or if charAt(i) == "+")

    Thanks!
    Last edited by 123jo; 12-12-2012 at 02:30 PM.

  • #2
    Senior Coder
    Join Date
    Dec 2010
    Posts
    2,396
    Thanks
    12
    Thanked 569 Times in 562 Posts
    So you will have to write a mathematical parser essentially? Should it be able to cope with operator priority? This would really be a big deal ...

    Or maybe I didn't understand your requirement? Do you really have lots of table cells with mathematical expressions that you need to parse/evaluate into a single integer result per cell?

  • #3
    Master Coder felgall's Avatar
    Join Date
    Sep 2005
    Location
    Sydney, Australia
    Posts
    6,632
    Thanks
    0
    Thanked 649 Times in 639 Posts
    That is definitely a task better handled by two nested loops - one for the table rows and one inside it for the cells in the row.

    There is no recursive solution that would map in any meaningful way to the structure of the data so while it would be possible to write a less efficient recursive version of the code it would not only use a lot more memory and run slower - it would also be much harder to maintain.

    You should only use recursion where it maps to the task in a meaningful way.
    Stephen
    Learn Modern JavaScript - http://javascriptexample.net/
    Helping others to solve their computer problem at http://www.felgall.com/

    Don't forget to start your JavaScript code with "use strict"; which makes it easier to find errors in your code.

  • #4
    Senior Coder rnd me's Avatar
    Join Date
    Jun 2007
    Location
    Urbana
    Posts
    4,301
    Thanks
    10
    Thanked 586 Times in 567 Posts
    Code:
    for(var i=0; i<myArray.length; i++) { 
    myArray[i] = parseInt(myArray[i], 10);
    }
    can be written without a loop as:

    Code:
    myArray=myArray.map(Math.floor);
    if your table is shaped like a ladder, it can't be recursively iterated.
    recursion is for deeply nested objects, like a folder structure.
    my site (updated 13/9/26)
    BROWSER STATS [% share] (2014/5/28) IE7:0.1, IE8:5.3, IE11:8.4, IE9:3.2, IE10:3.2, FF:18.2, CH:46, SF:7.9, NON-MOUSE:32%

  • #5
    New Coder
    Join Date
    Dec 2012
    Posts
    10
    Thanks
    2
    Thanked 0 Times in 0 Posts
    Maybe I wasn't clear enough... I learned how to go through my table by using recursivity so I wanted to apply the same method for a string, but I'm still stuck.

    s is the string (for example "14x10+2x1"). The function str is then supposed to return 142.

    Code:
    var str = function(s){
        
        var i = 0;
     
        var helper = function(s) {
            
            if(i < s.length) {
                
                var t = s.substring(i, s.length)
                var stringNum = parseInt(t, 10);
                if( t.charAt(i) == "x" ) stringNum *= t.charAt(i+1);
                if( t.charAt(i) == "+" ) stringNum += t.charAt(i+1);
                
                i++;
            }
            return stringNum;
        }
        return helper(s);
    };
    I don't know where I made a mistake... it only returns 14. How can I do to make the function read "x" and "10" and the rest of the string ? Thanks

  • #6
    Senior Coder
    Join Date
    Dec 2010
    Posts
    2,396
    Thanks
    12
    Thanked 569 Times in 562 Posts
    A good way to debug those kinds of calculations is to write down the values of variables for each step:

    Example: s="14x10+2x1"

    1 - i = 0
    2 - call helper()
    3 - i < s.length, so t = "14x10+2x1"
    4 - stringNum = 14
    5 - t[0] is not "x" and not "+"
    6 - i = 1
    7 - stringNum = 14 will be returned to the function str
    8 - helper(s) = 14 will be returned from str

    So there is no calculation because there is parsing beyond the first numerical value ... an no recursion

  • #7
    New Coder
    Join Date
    Dec 2012
    Posts
    10
    Thanks
    2
    Thanked 0 Times in 0 Posts
    Will it fix the problem if I change the parsing for
    Code:
    var stringNum += parseInt(t, 10);

  • #8
    Senior Coder xelawho's Avatar
    Join Date
    Nov 2010
    Posts
    2,930
    Thanks
    56
    Thanked 552 Times in 549 Posts
    if you wanted to avoid the much-despised eval...

    Code:
    var str=function(s){
    return eval(s.replace(/x/gi,"*"))
    }
    
    alert(str("14X10+2X1"))
    you could make a dynamic script...

    Code:
    var str = function (s){
      var scr = document.createElement("script");
      scr.type = "text/javascript";
      scr.text = "ans = " + s.replace(/x/gi,"*") + ";";
      document.body.appendChild(scr);
      document.body.removeChild(scr);
      return ans;
    }
    
    alert(str("14X10+2X1"))
    although I suspect they amount to much the same thing...

  • #9
    New Coder
    Join Date
    Dec 2012
    Posts
    10
    Thanks
    2
    Thanked 0 Times in 0 Posts
    I can't use neither eval or dynamic programming... The key of this exercise is to use recursion.

  • #10
    Senior Coder
    Join Date
    Dec 2010
    Posts
    2,396
    Thanks
    12
    Thanked 569 Times in 562 Posts
    As this is supposed to be your exercise, I can only give you more hints

    1 - Let's hope that you don't have to take care of operator priority (so you can just go right to left)
    2 - call your function with the current string
    3 - Start from the right of the current string, extract the number and the operator and use it for the expression like "number operator yourfunction(restofstring)". If there is no operator you end the recursion and return the number

    Example: 14x10+2x1
    step 2: alert(yourfunction("14x10+2x1"));
    step 3: inside of yourfunction: extract 1 and x, return 1*yourfunction("14x10+2")
    step 3: inside of yourfunction: extract 2 and +, return 2+yourfunction("14x10")
    step 3: inside of yourfunction: extract 10 and x, return 10*yourfunction("14")
    step 3: inside of yourfunction: just return 14 => end of recursion
    one level up: return 10*14 = 140 => end of recursion
    one level up: return 2+140 = 142 => end of recursion
    one level up: return 1*142 = 142 => end of recursion
    one level up: alert(142) => result

  • Users who have thanked devnull69 for this post:

    123jo (12-13-2012)

  • #11
    New Coder
    Join Date
    Dec 2012
    Posts
    10
    Thanks
    2
    Thanked 0 Times in 0 Posts
    Thanks Devnull69, I almost got it! I have a tiny problem left, how can I extract the 1? When I try with parseInt(s) it automatically takes 14...
    I tried to extract it with s[i] where i = s.length-1 but it won't work if the number has more than 1 number (like 10)...and I don't even know if it's supposed to work with a string... Thanks for your help again!


    Code:
    var str = function(s){
        
        var i = s.length-1;
        
        var helper = function(s) {
    
            if(i >= 0) {
                
                var t = parseInt(s, 10);
                var stringNum = "";
                
                i--;
                
                if( s.charAt(i) == "x" ) stringNum += t*str(s.substring(0,i));
                if( s.charAt(i) == "+" ) stringNum += t+str(s.substring(0,i));
    
            }    
            return stringNum;   
        }
        return helper(s);
    };
    Last edited by 123jo; 12-13-2012 at 01:30 AM. Reason: Thanks felgall I forgot!

  • #12
    Master Coder felgall's Avatar
    Join Date
    Sep 2005
    Location
    Sydney, Australia
    Posts
    6,632
    Thanks
    0
    Thanked 649 Times in 639 Posts
    You should specify the number base you are working with as the second parameter to parseint

    If you don't then it will interpret 0x17 as the number 23 instead of as 0 times 17.
    Stephen
    Learn Modern JavaScript - http://javascriptexample.net/
    Helping others to solve their computer problem at http://www.felgall.com/

    Don't forget to start your JavaScript code with "use strict"; which makes it easier to find errors in your code.

  • #13
    New Coder
    Join Date
    Dec 2012
    Posts
    10
    Thanks
    2
    Thanked 0 Times in 0 Posts
    Anyone has an idea of how I can get the last integer of a string? Parsing doesn't seem to work...

  • #14
    Supreme Master coder! Philip M's Avatar
    Join Date
    Jun 2002
    Location
    London, England
    Posts
    17,924
    Thanks
    203
    Thanked 2,531 Times in 2,509 Posts
    Quote Originally Posted by 123jo View Post
    Anyone has an idea of how I can get the last integer of a string? Parsing doesn't seem to work...

    <script type = "text/javascript">

    Code:
    var str = "1234a56d";
    str = str.replace(/[^\d]/gi,"");
    var len = str.length;
    var x = str.charAt(len-1);
    alert (x);
    
    
    var str = "14x10+2x1123";
    var x = str.match(/\d+\D*/gi);
    var len = x.length;
    var y = Number(x[len-1].replace(/[^\d]/g,""));
    alert (y);
    
    </script>
    Last edited by Philip M; 12-13-2012 at 08:05 AM.

    All the code given in this post has been tested and is intended to address the question asked.
    Unless stated otherwise it is not just a demonstration.

  • #15
    Senior Coder
    Join Date
    Dec 2010
    Posts
    2,396
    Thanks
    12
    Thanked 569 Times in 562 Posts
    More like this
    Code:
    function getLastInteger(current) {
       var i = current.length-1;
       while(!isNaN(parseInt(current.substring(i), 10))) i--;
       return parseInt(current.substring(i+1), 10);
    }
    alert(getLastInteger("14x10+2x1123"));


  •  
    Page 1 of 2 12 LastLast

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •