CodingForums.com - How to go through a table using recursivity?

Page 1 of 2

Show 40 post(s) from this thread on one page

CodingForums.com (http://www.codingforums.com/index.php)

- JavaScript programming (http://www.codingforums.com/forumdisplay.php?f=2)

- - How to go through a table using recursivity? (http://www.codingforums.com/showthread.php?t=284026)

123jo

12-12-2012 01:23 PM

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!

devnull69

12-12-2012 03:53 PM

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?

felgall

12-12-2012 06:35 PM

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.

rnd me

12-12-2012 07:56 PM

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.

123jo

12-12-2012 08:02 PM

Maybe I wasn't clear enough... :confused: 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

devnull69

12-12-2012 08:38 PM

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

123jo

12-12-2012 09:36 PM

Will it fix the problem if I change the parsing for

Code:

var stringNum += parseInt(t, 10);

xelawho

12-12-2012 09:43 PM

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...

123jo

12-12-2012 10:20 PM

I can't use neither eval or dynamic programming... The key of this exercise is to use recursion.

devnull69

12-12-2012 11:04 PM

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

123jo

12-13-2012 01:06 AM

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);

};

felgall

12-13-2012 01:28 AM

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.

123jo

12-13-2012 02:18 AM

Anyone has an idea of how I can get the last integer of a string? Parsing doesn't seem to work...

Philip M

12-13-2012 07:41 AM

Quote:

Originally Posted by 123jo (Post 1299517)

Anyone has an idea of how I can get the last integer of a string? Parsing doesn't seem to work...

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>

devnull69

12-13-2012 07:58 AM