
Splitting text into several components
Hi everyone!
I've been lurking here for a few months but this is my first time posting. Im also pretty new in Java so forgive me if this question is too basic :)
Anyway, i'm writing a program which utilizes a linked list implementation of polynomials, and its working fine; except now im having trouble parsing the user's input. Basically, the users input should be something like; "2x^3 + 3x^5" with as many terms as he wants. My program then needs to split that string into Coefficients and Exponents to feed into the linked list.
so, in the case of 2x^3 + 3x^5, the coefficient would be 2 and associated exponent would be 3; these are then converted into int before being passed. This my problem, as i cant get it working properly. I tried using split and substring but its not working properly.
Any tips, suggestions, examples? Just pushing me along the right path would be appreciated.
Thanks in advance :)

Re: Splitting text into several components
I'd work through the order of operations backwards. First, get rid of any spaces. Then, separate the String by its '+' and '', so that all additive parts of the polynomial are separated. After that it should be easier to get at the coefficients (before the variable!) and exponents (after the caret!).

Re: Splitting text into several components
Use java.util.regex.Pattern  it takes a while to learn how to use regular expressions properly, but they should be in every programmers' toolbox.
Test your regexes here:
RegEx: online regular expression testing
I would guess at something like "([09]{0,})x\\^([09]{0,})" and use Matcher.find() and Matcher.group() to extract the bits you want. 1 is the integer coefficient group, 2 the exponent group.

Re: Splitting text into several components
thank you both!
snowguy13 that seems to be the simplest way, thank you for that.
Sean4u, wow that is really interesting; I had no idea something like that even existed! I might try using that method just so i can learn it, as it seems extremely useful.
Thanks again. I'll post back with any more questions

Re: Splitting text into several components
@Sean4u
That seems utterly and incredibly fascinating. I now go to read.
Thank you very much; I hadn't even heard of regular expressions until now!

Re: Splitting text into several components
well i'm back.
I tried to use the simple way, but honestly its not working out too well, fact is i dont even really have much to post on that i am trying to get the regex to work however, but i need some help. would it be something like:
Code :
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class test
{
public static void splitter(String s)
{
String str = "([09]{1,})x\\^([09]{1,})";
Pattern p = Pattern.compile(str);
Matcher matcher = p.matcher(s);
boolean matchFound = matcher.find();
if (matchFound)
{
for (int i=0; i<=matcher.groupCount(); i++) {
String groupStr = matcher.group(i);
System.out.println(groupStr);
}
}
}
public static void main(String[] args)
{
String s = "12x^5+6x^33x+5";
splitter(s);
}
}
is that correct?
I'm trying to run it but nothing is happening. no error or output. I am so confused... :/
Can anyone give me a hand please?
EDIT: Oh i figured it out how to get it to work with 1 term (12x^5), however it doesnt work with multiple terms (12x^5+3x^2)
One other thing, how can i get it to return negative values, such as 12x^5? It just returns 12,5 instead of 12,5

Re: Splitting text into several components
Quote:
One other thing, how can i get it to return negative values, such as 12x^5? It just returns 12,5 instead of 12,5
I've been reading, and now I can help you with that! *cheesy superhero fanfare plays*
In a regex String, you can use the character ? to check if a certain character or character class occurs ONCE OR NOT AT ALL, such as in your  sign.
Quote:
"([09]{1,})x\\^([09]{1,})"
This is what you currently have (I get it now, heehee!).
I think that you should amend it to be like this:
"(?[09]{1,})x\\^(?[09]{1,})"
Note that I'm not sure that this will work (I'm still reading the tutorial page as I post this xD). But it should, because it tells the matcher to check for a  before the numbers once, or not at all. Also note that instead of [09] you can just use \d, like this:
"(?\\d{1,})x\\^(?\\d{1,})"
It helps to read out what this regex is doing:
"Check for a negative sign occurring once or not at all, followed by any number of numbers, followed by "x^", followed by a negative sign occurring once or not at all, followed by any number of numbers."
This. Is. So. Cool.

Re: Splitting text into several components
lol you certainly are a superhero that works perfectly!
The only issue i have left is to be able to pass it a polynomial with any number of terms. So far it only works with one term. I'm guessing the simplest way to do that would be to some sort of recursive function or for loop, where it evaluates one term at a time. what do you think? I've been reading this regex stuff and i cant figure out how to apply the pattern multiple times.
Also when i finally do extract these coefficients and exponents, i need to pass them into the constructor to assemble a polynomial. I'm thinking about writting all these pairs into some sort of List or map and then passing it through. Am i on the right track?

Re: Splitting text into several components
Hmm... Well, if your polynomial terms are always going to be surrounded by spaces, you could use another regex, and the <String>.split(String regex) method:
Use this regex: "\s[+]\s"
And the <String>.split(/*stick the regex here!*/) method, which will split the String at all the spots where that pattern occurs.
What it literally means is "split the String at a spot where there is a space, followed by a + or , followed by a space".
Hopefully that will work...
And yes, I could see a Map working. You could also create your own Polynomial class, if you had other functions in mind, but if all you want is the coefficients and degrees, then a Map should be just fine. :)
EDIT: This is very interesting. I copied your test program, and with the parentheses, got this:
12x^5
12
5
But without them, got this:
12x^5
I think it has to do with the groups created by the ( ). This is so interesting...

Re: Splitting text into several components
well this is strange...
I was starting to get desperate and frustrated since i've been working on this for about 8hours now, and i just kind of slammed by head against the keyboard then suddenly my code started working. lol but in all seriousness i found out how to get the regex thing to keep repeating.
Basically I changed:
to
then i appended this just outside the for loop BUT within the while loop:
Code :
matchFound = matcher.find(matcher.end());
I'm not sure if this is the proper way it's supposed to be done, but it works lol. I *think* what the code does is that it continues checking for a pattern right where it left off; not too sure to be honest as like i said i was just mashing away at the keyboard
i figured you might want to know. :)
I'm thinking about just passing all this stuff into a linkedhashmap with the exponents being teh key (the degrees are supposed to be unique), and then in turn passing the key/values into a bunch of nodes strung together to make polynomial. i think the linkedhashmap sorts stuff based on the key values. hopefully i'm able to retrieve key values...
this is my polynomial class:
Code :
class Polynomial
{
Node head;
Polynomial()
{
head = new Node(null,null);
}
public void add(int coef, int power)
{
if(coef == 0)
{
}
else
{
Node temp = new Node(coef, power);
Node current = head;
// starting at the head node, crawl to the end of the list
while(current.getNext() != null)
{
current = current.getNext();
}
// the last node's "next" reference set to our new node
current.setNext(temp);
}
}
class Node<E>
{
E Element1, Element2;
Node<E> next;
public Node(E Element1,E Element2)
{
this.Element1 = Element1;
this.Element2 = Element2;
next = null;
}
public Node getNext()
{
return next;
}
public void setNext(Node next)
{
this.next = next;
}
}
}
What do you think?
Thank you so much for the help :D

Re: Splitting text into several components
Quote:
i think the linkedhashmap sorts stuff based on the key values. hopefully i'm able to retrieve key values...
I found this (link for more detail):
get(Object key)
Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
Hopefully that helps?
Also, I edited our regex again so that inputs like "3x" or "6x" (that have no ^ and exponent) will still be accepted by the regex:
"?\\d{1,}(x(\\^?\\d{1,})?)?"
What I changed is red and bold. Basically it takes the "^[someNumber]" and puts the ONCE OR NOT AT ALL condition on it, stating that it can be there once, or not. Then, I did the same thing around the "x" part so that polynomials like "5" and "3" work too! I tried it and it worked!
Quote:
Thank you so much for the help
Thank you for posting! I think this is the most fun I've had learning Java... maybe ever! :P

1 Attachment(s)
Re: Splitting text into several components
Quote:
Originally Posted by
snowguy13
I found this (link for more detail):
get(Object key)
Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
Hopefully that helps?
Yes! Thank you, i'll be sure to read that.
Quote:
Originally Posted by
snowguy13
"?\\d{1,}(x(\\^?\\d{1,})?)?"
this does not appear to be working for me actually. 12x^5 returns x^5,^5 instead of 15,5. and 5x returns x,null. 5 returns null,null. strange...
here is my code, essentially the same i believe (ignore the comments, i was just testing stuff out):
Code :
public class test
{
public static void prep(String s)
{
String str = "?\\d{1,}(x(\\^?\\d{1,})?)?";
Pattern p = Pattern.compile(str);
int[] groupInt = new int[2];
Matcher matcher = p.matcher(s);
boolean matchFound = matcher.find();
while (matchFound)
{
for (int i=1; i<=matcher.groupCount(); i++)
{
String gstr = matcher.group(i);
System.out.println(gstr);
// int n = Integer.parseInt(gstr);
// groupInt[i1] = n;
}
/* int coef = groupInt[0];
int power = groupInt[1];
System.out.println(coef);
System.out.println(power);*/
matchFound = matcher.find(matcher.end());
}
}
public static void main(String[] args)
{
String s = "5";
prep(s);
}
}
Quote:
Originally Posted by
snowguy13
Thank you for posting! I think this is the most fun I've had learning Java... maybe ever! :P
Haha, i'm glad your having fun. so am i, but im more like this most of the time:
Attachment 1053

Re: Splitting text into several components
Hahaha :D I'm gonna go to sleep for tonight, but I'll check out that code tomorrow! Good night! :)

Re: Splitting text into several components
good night :)
thanks for the help. im gonna keep working on this

Re: Splitting text into several components
Quote:
Originally Posted by
clydefrog
good night :)
thanks for the help. im gonna keep working on this
Seems like you're doing just fine. You're right  a reasonable pattern for something like you're doing could be (not tested by compiling)
Code java:
Matcher matcher = PATTERN_POLY.matcher(inputString);
if (matcher.find())
{
newPoly = new Poly();
do
newPoly.add(new Term(matcher.group(1), matcher.group(2)));
while (matcher.find());
}
else
{ /* not a poly */ }
I like the idea of storing the terms by exponent in your class, that's neat. LinkedHashMap might not be quite right because it preserves the insertion order of its elements, and your input could be "4x^3+7xx^2", right? TreeMap stores its entries sorted on natural order, but you can also provide your own Comparator.
Good luck with tuning your regular expression  that can be a labour of love! Would treating a term as (optionalsign)(optionalcoefficient)x(optionalexponent) work? Don't forget to code for (or canonicalise) whitespace and case, and constant (x^0) terms!
I guess one übersimple option would be to implement your polynomial class as a Map of integer exponents onto signed integer coefficients, as opposed to having a separate class for the terms. The sorted map also makes reporting the 'degree' of your polynomial trivial.

Re: Splitting text into several components
Thank you :)
Sorry i didnt reply sooner, i was away from the computer.
Quote:
Originally Posted by
Sean4u
Code java:
Matcher matcher = PATTERN_POLY.matcher(inputString);
if (matcher.find())
{
newPoly = new Poly();
do
newPoly.add(new Term(matcher.group(1), matcher.group(2)));
while (matcher.find());
}
else
{ /* not a poly */ }
Wow this is extremely helpful. I was scratching my head all day for an efficient way to add the the results into the polynomial, and think this may very well be it!
this is the regex im using: "(?[09]{1,})x?\\^?(?[09]{1,})?"
when applying this polynomial to it, 12x^5+6x^33x+5 i get the following pairings (coef,exp): (12,5), (6,3) , (3, null), (5, null).
Now everything is correct except the last 2 pairs, as it cant seem to deferential between x and x^0. Is it possible to add multiple patterns, and then have it run through an if function to see which pattern matches? for example, here is some psuedocode:
Pattern 1 = ax^b
Pattern 2 = ax
Pattern 3 = a
if my poly matches pattern1, return (a,b)
if my poly matches pattern2, return (a,1)
if my poly matches pattern3, return (a,0)
so basically it would break up my polynomial of 12x^5+6x^33x+5 into 3 parts: 12x^5+6x^3 , 3x, and 5
would this be possible?
You're right, linkedhashmap does not sort, and i'd rather not fiddle around with a comparator lol. i'll just use a treemap thank you for the heads up.
Thank you for the help ;)

Re: Splitting text into several components
A couple of minutes' fiddling at the test site got me this pattern:
Code :
\+{0,1}(\{0,1}[09]{0,})x{0,1}(\^[09]{0,}){0,1}
which produces one extra match with both groups empty. Remember to doubleup the backslashes for Java. I feel sure there is a better way of writing that regex with the '' (or) operator. That looks messy to me.
You wouldn't have to 'fiddle' even that long with a Comparator for two ints: if you got it wrong the first time, you'd only have to negate the return value and it would be right.

Re: Splitting text into several components
Could you briefly explain to me what that regex does? When i plug it in, i just get an infinite loop of "null" as my coef and exp. i'll try to tweak it

Re: Splitting text into several components
Oh really? I only tested it on the regex test site, so it could be that it works slightly differently for you  although perhaps the test site detects the first zerolength find and stops at that point? It's an attempt to cope with the range of possibilities in a term, but actually every component (the leading sign, the numeric part of the coefficient, the 'x', the caret, the exponent) is not guaranteed to be present in every term. If there is at least one zero length matches in a string, then there are infinitely many zerolength matches in it.
An expression with '' that matches expressions 2 or greater, expressions in x (no exponent) or constants would probably be ideal. It would provide what you suggested a couple of posts ago, but in a nicer way.

Re: Splitting text into several components
oh okay.
there might be something wrong with my loop, idk. ill try to mess around with it and see.
thank you :)
man this project is tough! I'm still working on the user input part of this. I still have to make get to polynomials to add/sub/mult/div not to mention the gui :(

Re: Splitting text into several components
Using this regex: "?\d{1,}(x(\^?\d{1,})?)?" (remember to add another \ before special characters)
And the input String: "12x^5+6x^3+3x5", and only accepting group zero (the entire regex), I got this result:
12x^5
6x^3
3x
5
So, the regex I'm using gets the right output and matches, but you'd have to do some extra fiddling with code outside of the regex to get the Polynomial values (which should be too hard). I'd just check to see if that match contains "x^" (in which case you could split the String at that point), and if not, check to see if the String has "x" (in which case the exponent is 1 and the coefficient is everything before x), and otherwise the exponent is 0 and the coefficient is the match. Hopefully that makes sense?

Re: Splitting text into several components
sweet! i did a quick test and it seems to work as you said. i'll be sure to implement that into my actual program.
However, i have another question. I know i'm beginning to leave the scope of this thread but i feel it would be better if i posted here since all the relevant info is already included in this thread.
Anyway, basically i've split my polynomials up into (coef,exp) and i've added it all into a treemap with the exponents being the key. Now the treemap has already sorted it out but i have a 2 part question:
1. it automatically sorts it in ascending order, (1, 2, 3...) but i need it in descending order (5, 4, 3, ...). How do i specify?
2. how can i actually get the key and values out of the treemap and stick into my constructor add(int coef, int exp)? I tried using an iterator, but iterator.keySet() and iterator.values() return objects, yet my constructor needs integers.
any ideas?
I remember you mentioned something about using a comparator to avoid the map, how would i go about doing that? Is there a way i can just go and reorder my nodes based on the exponent? My nodes contain 2 elements (coef, exp) and multiple nodes strung together forms a polynomial.
If you need to get a better idea here is my basic code:
Code :
class Polynomial
{
Node head;
Polynomial()
{
head = new Node(null,null);
}
public void add(int coef, int power)
{
Node temp = new Node(coef, power);
Node current = head;
// starting at the head node, crawl to the end of the list
while(current.getNext() != null)
{
current = current.getNext();
}
// the last node's "next" reference set to our new node
current.setNext(temp);
class Node<E>
{
E Element1, Element2;
Node<E> next;
public Node(E Element1,E Element2)
{
this.Element1 = Element1;
this.Element2 = Element2;
next = null;
}
public Node getNext()
{
return next;
}
public void setNext(Node next)
{
this.next = next;
}
}
}
}

Re: Splitting text into several components
Quote:
it automatically sorts it in ascending order, (1, 2, 3...) but i need it in descending order (5, 4, 3, ...). How do i specify?
I've never worked with TreeMap before, but would it be possible for you to move through the keys backwards?
Quote:
how can i actually get the key and values out of the treemap and stick into my constructor add(int coef, int exp)? I tried using an iterator, but iterator.keySet() and iterator.values() return objects, yet my constructor needs integers.
You can class cast objects to other objects; so, as long as the inputs to your TreeMap are of the class Integer, you can class cast the objects returned by the iterator to Integers, and the use the intValue() method.
Class casting works like this:
Code Java:
Object cake = new Integer(); //Integer is a subclass of Object (like everything)
Integer cakeInteger = (Integer)cake; //cake can be cast to an Integer (that's what we initialized it as)

Re: Splitting text into several components
Perfect! Thank you VERY much!

Re: Splitting text into several components
You're welcome! So, I'm curious, what is the extent of this program's functionality? How much and what will it do when it's done?