Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Matching math expression with regular expression?

Tags:

regex

parsing

For example, these are valid math expressions:

a * b + c
-a * (b / 1.50)
(apple + (-0.5)) * (boy - 1)

And these are invalid math expressions:

--a *+ b @ 1.5.0  // two consecutive signs, two consecutive operators, invalid operator, invalid number
-a * b + 1)  // unmatched parentheses
a) * (b + c) / (d  // unmatched parentheses

I have no problem with matching float numbers, but have difficulty with parentheses matching. Any idea? If there is better solution than regular expression, I'll accept as well. But regex is preferred.

========

Edit:

I want to make some comments on my choice of the “accepted answer”, hoping that people who have the same question and find this thread will not be misled.

There are several answers I consider “accepted”, but I have no idea which one is the best. So I chose the accepted answer (almost) randomly. I recommend reading Guillaume Malartre’s answer as well besides the accepted answer. All of them give practical solutions to my question. For a somewhat rigorous/theoretical answer, please read David Thornley’s comments under the accepted answer. As he mentioned, Perl’s extension to regular expression (originated from regular language) make it “irregular”. (I mentioned no language in my question, so most answerers assumed the Perl implementation of regular expression – probably the most popular implementation. So did I when I posted my question.)

Please correct me if I said something wrong above.

like image 206
Ethan Avatar asked Apr 07 '10 19:04

Ethan


People also ask

How do you match a regular expression?

To match a character having special meaning in regex, you need to use a escape sequence prefix with a backslash ( \ ). E.g., \. matches "." ; regex \+ matches "+" ; and regex \( matches "(" . You also need to use regex \\ to match "\" (back-slash).

Which function is used to match a regular expression?

match() function of re in Python will search the regular expression pattern and return the first occurrence. The Python RegEx Match method checks for a match only at the beginning of the string. So, if a match is found in the first line, it returns the match object.

What is regular expression in maths?

Regular expressions are a generalized way to match patterns with sequences of characters. They define a search pattern, mainly for use in pattern matching with strings, or string matching, i.e. “find and replace” like operations.


1 Answers

Use a pushdown automaton for matching paranthesis http://en.wikipedia.org/wiki/Pushdown_automaton (or just a stack ;-) )

Details for the stack solution:

while (chr available)
    if chr == '(' then
      push '('
    else
      if chr == ')' then
        if stack.elements == 0 then
          print('too many or misplaced )')
          exit
        else
          pop //from stack
end while
if (stack.elements != 0)
  print('too many or misplaced(')

Even simple: just keep a counter instead of stack.

like image 51
Victor Hurdugaci Avatar answered Oct 13 '22 17:10

Victor Hurdugaci