将数学表达式与正则表达式匹配？

Question

例如,这些是有效的数学表达式:

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

这些是无效的数学表达式:

--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

我没有匹配浮点数的问题,但是括号匹配有困难.任何的想法？如果有比正则表达更好的解决方案,我也会接受.但正则表达式是首选.

========

编辑:

我想对我对"已接受的答案"的选择做一些评论,希望那些有相同问题并找到这个帖子的人不会被误导.

我认为有几个答案"被接受",但我不知道哪一个是最好的.所以我随机选择了接受的答案(差不多).除了接受的答案,我建议阅读Guillaume Malartre的答案.他们都为我的问题提供了实用的解决方案.有关严谨/理论上的答案,请在接受的答案下阅读David Thornley的评论.正如他所提到的,Perl对正则表达式的扩展(源于常规语言)使其"不规则".(我在我的问题中没有提到任何语言,所以大多数答复者都假设正则表达式的Perl实现 - 可能是最流行的实现.当我发布我的问题时,我也是如此.)

如果我上面说错了,请纠正我.

Answer 1

正则表达式只能用于识别常规语言.数学表达的语言不规律; 你需要实现一个实际的解析器(例如LR)才能做到这一点.

Answer 2

使用下推自动机匹配paranthesis http://en.wikipedia.org/wiki/Pushdown_automaton(或只是一个堆栈;-))

堆栈解决方案的详细信息:

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(')

甚至简单:只需保留一个计数器而不是堆栈.

Answer 3

我相信你会更好地实现一个真正的解析器来完成你所追求的目标.

简单数学表达式的解析器是"Parsing 101",在线可以找到几个例子.

一些例子包括:

• ANTLR:表达式评估器示例(ANTLR语法可以定位多种语言)
• pyparsing:http://pyparsing.wikispaces.com/file/view/fourFn.py(pyparsing是一个Python库)
• Lex&Yacc:http://epaperpress.com/lexandyacc/(包含PDF教程和计算器示例代码)

请注意,验证表达式所需的语法比上面的示例更简单,因为这些示例还实现了对表达式的求值.

Answer 4

用正则表达式匹配括号是很有可能的。

这是一个 Perl 脚本，它将解析任意深度匹配的括号。虽然它会抛出不匹配的括号，但我没有专门设计它来验证括号。只要它们是平衡的，它就会解析任意深的括号。然而，这会让你开始。

关键是正则表达式中的递归及其使用。玩它，我相信你可以用它来标记不匹配的 prens。我认为，如果您捕获此正则表达式丢弃的内容并计算括号（即测试非匹配文本中的奇数括号），则会出现无效的、不平衡的括号。

#!/usr/bin/perl
$re = qr  /
     (                      # start capture buffer 1
        \(                  #   match an opening paren
        (                   # capture buffer 2
        (?:                 #   match one of:
            (?>             #     don't backtrack over the inside of this group
                [^()]+    #       one or more 
            )               #     end non backtracking group
        |                   #     ... or ...
            (?1)            #     recurse to opening 1 and try it again
        )*                  #   0 or more times.
        )                   # end of buffer 2
        \)                  #   match a closing paren
     )                      # end capture buffer one
    /x;


sub strip {
    my ($str) = @_;
    while ($str=~/$re/g) {
        $match=$1; $striped=$2;
        print "$match\n";
        strip($striped) if $striped=~/\(/;
        return $striped;
    }
}

while(<DATA>) {
    print "start pattern: $_";
    while (/$re/g) { 
        strip($1) ;
    }
}   

__DATA__
"(apple + (-0.5)) * (boy - 1)"
"((((one)two)three)four)x(one(two(three(four))))"
"a) * (b + c) / (d"
"-a * (b / 1.50)"

输出：

start pattern: "(apple + (-0.5)) * (boy - 1)"
(apple + (-0.5))
(-0.5)
(boy - 1)
start pattern: "((((one)two)three)four)x(one(two(three(four))))"
((((one)two)three)four)
(((one)two)three)
((one)two)
(one)
(one(two(three(four))))
(two(three(four)))
(three(four))
(four)
start pattern: "a) * (b + c) / (d"
(b + c)
start pattern: "-a * (b / 1.50)"
(b / 1.50)