How do you parse non-standard form function?

Question

A standard form function like A*B+A*B' is easy to parse (spliting by + and then spliting by *). How do you parse a function, if it doesn't take a standard form? Example: a function can take the following forms:

A*B+A(A+B')
A*B+(A+B')A
A*B+A*B(A+B)

Any ideas?

P.S: I would like to parse the function in Java.

just an idea: remove all the symbols which you can't or don't want to parse before parsing your function — Leo, Mar 22 '12 at 03:39
@Bergi: 1- the task I have is to recognize the structure of the non standard form and translate it to standard form like A*B+C*D+A*C... 2- I want to use java — Max_Salah, Mar 22 '12 at 17:07
possible duplicate of [Parse non standard form to standard form in java](http://stackoverflow.com/questions/9844023/parse-non-standard-form-to-standard-form-in-java) — Bart Kiers, Mar 23 '12 at 19:06

score 0 · Answer 1 · edited May 23 '17 at 11:52

0

Rather than trying to parse with ad hoc methods (which always ends badly), you are better off

writing an BNF grammar for your expression forms, in all variants
code a recursive descent parser (See https://stackoverflow.com/a/2336769/120163)

edited May 23 '17 at 11:52

Community

1
1

answered Oct 05 '15 at 04:29

Ira Baxter

93,541
22
172
341

score 0 · Answer 2 · edited Sep 01 '12 at 11:11

A standard form function like A*B+A*B' is easy to parse (splitting by + and then splitting by *).

Good. Now, all that's left is to deal with those pesky parenthesis. First, we will remove them with array.split, and then we will add the necessary logic to carry out the multiplications:

Once you have split the string A(A+B')C, you will end up with an array of three strings A, A+B, and C. And notice that in this method odd-number strings are ALWAYS the ones inside the parenthesis. So all we have to do is check to see if the last and first characters of odd strings are letters (A, B, C) or operators (*,+).

String firstString = "A*B+A*B(A+B)+A*B+A*B(A+B)";
String leftOfParenthesis;
String insideParenthesis;
String rightOfParenthesis
String last;
String first;

String[] masterArray;
masterArray = str.split(firstString);

for(int i=0; i<masterArray.length; i+2){
   leftOfParenthesis = masterArray[i];
   insideParenthesis = masterArray[i+1];
   rightParenthesis = masterArray[i+2];

   last = leftOfParenthesis.substring(leftOfParenthesis.length()-1);
   first = rightParenthesis.substring(0,1);

   if(last.isLetter() && first.isLetter()){
      leftOfParenthesis.append("*" + insideParenthesis + "*" +
          last + "+last*" +  insideParenthesis + "*" + first);
      rightOfParenthesis[0] = last;
   }
   else if(last.isLetter()){
      leftOfParenthesis.append("*" + insideParenthesis + "*" + last);
   }
   else if(first.isLetter()){
      leftOfParenthesis.append("+" + first + "*" +
          insideParenthesis + "*" );
   }
}

That's the basic logic. There will be some issues with the rightParenthesis = masterArray[i+2]; if you run past the end of your input string and there aren't that many terms left. So you will have to add some if statements to check for that. And this isn't totally generally, if you have parenthesis inside parenthesis or more than two terms inside a pair of parenthesis, you will have to add special logic to deal with that.

This is exactly what I meant by "ad hoc" parsing in my answer to the original question: http://stackoverflow.com/a/9867303/120163. I don't think this will get you very far for serious logic analysis and transformation. — Ira Baxter, Mar 26 '12 at 19:50
Well, obviously I didn't see your post. It was after I posted, and on a different thread. But I'm totally willing to admit there may be a more elegant or generally useful way to solve the problem. I guess it all depends how general Ahmed's problem-set will be. If there will only ever be strings of the length he quoted in his post, I would probably go short-and-sweet. BUT, if there could be hundreds of terms in the string, with embedded quotes and craziness, than, yes, a more sophisticated approach would be far superior. I guess I assumed his example was as complex as he needed. — john_science, Mar 26 '12 at 20:06

How do you parse non-standard form function?

2 Answers2