how do you build a number?

Basically I want to build a number using linked lists. Each node contans a data value of type int or Integer which represents a single digit ie. 345 = a 3 node linked list with one node that contains a 5, another a 4, and the last one a 3. I just want to implement the addition of something like this. Example input

345
111
+

would output 345 + 111 = 456

I have a limited understanding of linked lists so any help in getting me started would be greatly appreciated :)

Comments

  • In your LinkedLists, store each digit as a char value. To get the integer value (or float for that matter if you include the decimal point) of that list: Collection.toArray() gets a char array --> new String(char[]) creates a String --> and Integer.parseInt(String) yields an int. The string can also include the minus sign. Simple:

    int x = Integer(new String((char[]) yourLinkedList.toArray()));

    Then, once you have the int value for each LinkedList; I'm afraid I can't help you in doing the addition of the int's.

    But this is a friendly place! I'm sure someone else could!

    Peace.
  • [b][red]This message was edited by Vilanye at 2004-8-23 2:36:14[/red][/b][hr]
    Are you needing to handle huge integers and perform arithmetic operations on them?

    If so your best bet is to build a linked list of single digits using the Integer class inside another class called HugeInt or whatever. You need a LL Class, an boolean for sign and an int for the length of the HugeInt at the minimum. You have to decide whether you are going to insert from the front or back of the list and stay consistant.
    The logic of artimetic operations on the HugeInt's is pretty straight forward. Create another HugeInt to store the answer and make sure you are adding the correct digits up and take the fact that numbers may be different lengths into account( ie 5000+50), otherwise you will be getting null pointer excpetions all over the place. Here is some code I did about a year ago, this creates a LL, and adds any 2 numbers of any size. I have this for the other arithmetic operations, but the code is quite long, this should get you started if I am understanding what you need. Subtraction and division is the hardest to work out an algorithm, just use simple elementary school arithmetic to work it out.

    public class InfInt implements Comparable
    {
    private int num;

    private LinkedList l;
    private boolean sign;//true = positive number false = negative number
    private boolean swapped;//true = the 2 InfInt were swapped
    private int length;


    public InfInt()
    {
    l = new LinkedList();
    sign = true;
    }


    public InfInt(String str)
    {
    l = new LinkedList();
    sign = true;
    swapped = false;
    length = str.length();

    //parses string, exception thrown sets the sign
    for( int i = 0; i < str.length(); i++)
    {

    try
    {
    num = Integer.parseInt( "" + str.charAt(i));
    l.addFirst(new Integer(num));
    }
    catch(NumberFormatException E)
    {

    i++; //skip over sign
    num = Integer.parseInt( "" + str.charAt(i));
    sign = false;
    length = str.length() - 1;

    l.addFirst(new Integer(num));
    }
    }


    }//end of constructor


    //compares absolute values of equal length numbers
    public int compareTo(Object o)
    {
    int i = 0;
    Integer one, two;

    InfInt rhs = (InfInt)o;

    while( i < length)
    {
    one = this.l.getValue(i);
    two = rhs.l.getValue(i);

    if( one.intValue() < two.intValue())
    return -1;

    else if( one.intValue() > two.intValue())
    return 1;

    i++;
    }
    return 0;

    }

    public InfInt plus(InfInt rhs)
    {
    InfInt result = new InfInt();
    Integer a, b, sum;
    int carry = 0, lenOne, lenTwo;


    lenOne = getLength();
    lenTwo = rhs.getLength();

    //sets the sign of the result
    resultSign( rhs, result);

    for( int i = 0; i < lenOne || i < lenTwo; i++)
    {
    //exception adds a zero to the InfInt as the most significant digit
    try
    {
    a = this.l.getItem(i);
    }
    catch( NullPointerException e)
    {
    a = new Integer(0);
    }
    try
    {
    b = rhs.l.getItem(i);
    }
    catch( NullPointerException e)
    {
    b = new Integer(0);//this avoids null pointer exceptions when one HugeInt has less places
    }

    sum = new Integer( a.intValue() + b.intValue() + carry);

    if( sum.intValue() > 9)
    carry = sum.intValue()/10;

    else
    carry = 0;

    sum = new Integer( sum.intValue() % 10);
    result.l.addLast(sum);
    result.setLength(1);
    }//end of for


    //adds the final carry to the MSD if it is > 0
    if( carry != 0)
    {
    result.l.addLast( new Integer(carry));
    result.setLength(1);
    }

    return result;
    }// end of plus

    //returns whether or not the result from plus() is a positive or negative
    public void resultSign(InfInt rhs, InfInt result)
    {
    if( this.sign == false && rhs.getSign() == false)
    result.setSign(false);

    else
    result.setSign(true);
    }

    If you want, I have a far better implementation of this in C++


Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories