Using Java Regex in order to find a subtring withing another substring

Question

I have got a program that takes user input in a form of logical expression (for example: (p=>(r||q)) ) and it divides the string in to substrings which are defined by brackets. I am using pattern and matcher.
So, for example user inputs:
((p||q)=>r).
I want to get 2 substrings which are:
p||q
and (p||q)=>r.
However I am only getting this:
(p||q

Here is the code that I am using

 Scanner scanner = new Scanner(System.in);
 System.out.println("Enter formula: ");
 String formula = scanner.next();
 Pattern pattern = Pattern.compile("\\((.*?)\\)");
 Matcher matcher = pattern.matcher(formula);
         while(matcher.find())
         {
          String s = matcher.group(1);

          System.out.println(s);
          }

So I need a way that the program finds all the substrings in that string.

Regular expressions are poorly suited to this task. I suggest you do the parsing manually or make use of a parsing library. — Mark Peters
– Mark Peters, Commented Dec 21, 2011 at 18:15

belgther · Accepted Answer · 2011-12-21 18:28:56Z

2

You can't do this with regular expressions.

Because the usage of brackets is a sign that what you want to do goes beyond the capabilities of regular expressions. Regular expressions describe a Chomsky-3 grammar which can't have bracket structures. Bracket structures are available in Chomsky-2 grammars. So you have to define a corresponding grammar with parsing rules. A good library that might help you achieving what you want is ANTLR.

answered Dec 21, 2011 at 18:28

belgther

2,53417 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Mark Peters · Accepted Answer · 2011-12-21 18:34:05Z

As I said in my comment, regular expressions do not handle nested brackets well at all. However, parsing them manually is extraordinarily simple if you have a stack. Here is some sample code:

public static void main(String[] args) throws InterruptedException {
    findSubExpressions("((p||q)=>r)");
}

private static void findSubExpressions(String input) {
    Deque<Integer> startingBrackets = new LinkedList<Integer>();

    for (int i = 0; i < input.length(); i++) {
        char c = input.charAt(i);
        if (c == '(') {
            startingBrackets.push(i);
        } else if (c == ')') {
            int correspondingStart = startingBrackets.pop();
            logSubExpression(input.substring(correspondingStart+1, i));
        }
    }
}

private static void logSubExpression(String subExpression) {
    System.out.println(subExpression);
}

Collectives™ on Stack Overflow

Using Java Regex in order to find a subtring withing another substring

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related