0

I am creating a programming language in Python and one main component that I'm missing for the basic language is the ability to parse mathematical equations. I have the function to parse the math but I need to be able to check if the input is a math equation. I'm looking for a regex to match something like 3*x^(4*y)+1-(7*y*z/x).

Noah Singer
  • 526
  • 2
  • 6
  • 17
  • 2
    Although a regular expression may *check* such input, I'm skeptic how much you can rely on it to *validate* the equation. – Jason McCreary Sep 01 '11 at 20:16
  • 4
    No, a regular expression can't even *check* if it is syntactically correct. – aioobe Sep 01 '11 at 20:19
  • @aioobe: Just because Python’s patterns aren’t up to the task doesn’t mean nobody’s is. [Many are](http://stackoverflow.com/questions/4840988/the-recognizing-power-of-modern-regexes/4843579#4843579). You know this. Please stop parroting. – tchrist Sep 01 '11 at 20:21
  • 2
    Right... I'm commenting on this from the perspective of "pure" regular expressions, i.e., those that check for containment in a regular language. I agree, some engines have extensions which makes them as powerful as any CFG parser. – aioobe Sep 01 '11 at 20:23

5 Answers5

10

You can't do what you want with regular expressions, it isn't a regular language. Python has extensions that you could abuse to do what you want but it would be un-maintainable and would not gain you anything over using a parser.

What you want is a Parser, a great easy to use library for Python is called pyparsing.

Here is a related answer with a pyparsing example.

Community
  • 1
  • 1
  • 2
    pyparsing is absolutely the right tool for the job here. Parsing simple irregular grammars is precisely the task that pyparsing excels at. – Chinmay Kanchi Sep 01 '11 at 21:34
2

I'm looking for a regex to match something like 3*x^(4*y)+1-(7*y*z/x).

You can't have a regular expression that matches strings such as "3*x^(4*y)...". The languages of well-balanced parenthesis is simply not regular.

(Actually, when talking about Python specific regular expressions, the above is a lie. Still though, I would claim that regular expressions would be the wrong tool for this task.)

I have the function to parse the math...

If you have a parser, I suggest you simply attempt to parse it, and say true if it succeeds, and false otherwise.

aioobe
  • 413,195
  • 112
  • 811
  • 826
  • 1
    ʀᴇɢᴜʟᴀʀ sᴍᴇɢᴍᴜʟᴀʀ. So use a better pattern matching library then. Hint: Python can match `(.*)\1` too, and that isn’t regular either. . – tchrist Sep 01 '11 at 20:22
  • 2
    Hm.. right. Still though, I don't believe regular expressions is the right tool for this... do you? – aioobe Sep 01 '11 at 20:24
  • Updated answer anyway... – aioobe Sep 01 '11 at 20:52
2

You need to use an actual expression parser. Here is a question about expression parsing in Python:

Math Expression Evaluation

And here is the link from the best answer:

http://effbot.org/zone/simple-top-down-parsing.htm

Community
  • 1
  • 1
steveha
  • 74,789
  • 21
  • 92
  • 117
  • *I have the function to parse the math* -- Seems like he already has a parser... – aioobe Sep 01 '11 at 20:22
  • I'm not sure. What parser function is there that can parse the expression but doesn't tell you whether it succeeded or not? I'm not sure what he actually has. – steveha Sep 02 '11 at 01:44
  • I think he means that he has a function that can evaluate a parsed expression. – Karl Knechtel Sep 02 '11 at 01:49
0

For parsing math text, reverse polish notation is often used. If you get your input in this syntax, then you can use a RPN python function to read it.

For a RPN parser in python, either this or this looks promising.

If your are writing your own programming language, you can simply force the user to use this notation, and check if it is not in RPN :)

tylerthemiler
  • 5,496
  • 6
  • 32
  • 40
0

It turns out I can use a recursive function that recognizes letters and numbers and then when parsing expressions, say for example "x+y", it checks whether "x" and "y" are valid math. So whenever you are validating an expression, if it is a letter or a number it is valid or if it is an operator with valid stuff on either side.

Noah Singer
  • 526
  • 2
  • 6
  • 17