用正则expression式匹配mathexpression式?

例如,这些是有效的mathexpression式

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

这些是无效的mathexpression式:

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

我没有匹配浮点数的问题,但有括号匹配的困难。 任何想法? 如果比正则expression式有更好的解决scheme,我也会接受。 但是正则expression式是首选。

========

编辑:

我想就“接受答案”的select做一些评论,希望有同样问题的人find这个线索不会被误导。

有几个答案我认为“接受”,但我不知道哪一个是最好的。 所以我随机select了接受的答案(几乎)。 除了被接受的答案之外,我还推荐阅读Guillaume Malartre的答案。 他们都为我的问题提供了实际的解决scheme。 对于有些严谨的理论答案,请阅读David Thornley的评论。 正如他所提到的,Perl对正则expression式的扩展(源自普通语言)使其成为“不规则”的。 (我在我的问题中没有提到任何语言,所以大多数回答者都假设正则expression式的Perl实现 – 可能是最stream行的实现,所以当我发布我的问题时)。

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

8 Solutions collect form web for “用正则expression式匹配mathexpression式?”

用正则expression式匹配parens是很有可能的。

这是一个Perl脚本,将parsing任意深度匹配的parens。 虽然它会抛出外面的不匹配的parens,我没有专门devise它来validationparens。 只要它们是平衡的,它将任意地分解深处的人。 这会让你开始。

在正则expression式和使用它的关键是recursion。 玩它,我相信,你可以得到这个也标志非匹配的假释。 我认为,如果你捕捉到这个正则expression式抛出的东西,并计算出对数(即在不匹配的文本中testing奇数对),那么你就有无效的不平衡对象。

 #!/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) 

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

堆栈解决scheme的详细信息:

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

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

正则expression式只能用于识别常规语言。 mathexpression式的语言是不规则的; 你需要实现一个实际的parsing器(比如LR)才能做到这一点。

我相信你会更好地实施一个真正的parsing器来完成你所追求的。

简单的mathexpression式的parsing器是“parsing101”,并有几个例子可以在网上find。

一些例子包括:

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

请注意,validationexpression式所需的语法比上述示例更简单,因为这些示例还实现了对expression式的评估。

你不能使用正则expression式来做平衡括号这样的事情。

使用一个正则expression式来处理这个问题非常棘手,但是使用混合正则expression式/程序方法很容易。 这个想法是构造一个简单expression式(无括号)的正则expression式,然后用一些primefacesstring(例如标识符)重复replace( simple-expression ) )。 如果最终减less的expression式匹配相同的“简单”模式,则原始expression式被认为是有效的。

插图(在PHP中)。

 function check_syntax($str) { // define the grammar $number = "\d+(\.\d+)?"; $ident = "[az]\w*"; $atom = "[+-]?($number|$ident)"; $op = "[+*/-]"; $sexpr = "$atom($op$atom)*"; // simple expression // step1. remove whitespace $str = preg_replace('~\s+~', '', $str); // step2. repeatedly replace parenthetic expressions with 'x' $par = "~\($sexpr\)~"; while(preg_match($par, $str)) $str = preg_replace($par, 'x', $str); // step3. no more parens, the string must be simple expression return preg_match("~^$sexpr$~", $str); } $tests = array( "a * b + c", "-a * (b / 1.50)", "(apple + (-0.5)) * (boy - 1)", "--a *+ b @ 1.5.0", "-a * b + 1)", "a) * (b + c) / (d", ); foreach($tests as $t) echo $t, "=", check_syntax($t) ? "ok" : "nope", "\n"; 

以上只validation了语法,但同样的技巧也可以用来构造一个真正的parsing器。

对于括号匹配和实现其他expression式validation规则,编写自己的小parsing器可能是最简单的。 正则expression式在这种情况下是不好的。

好的,这里是我在ActionScript3中发现的括号,使用这种方法给分析括号之前的部分,括号内和父类之后的部分,如果有一些括号留在最后,你可以提出警告或拒绝发送到最终的eval函数。

 package { import flash.display.Sprite; import mx.utils.StringUtil; public class Stackoverflow_As3RegexpExample extends Sprite { private var tokenChain:String = "2+(3-4*(4/6))-9(82+-21)" //Constructor public function Stackoverflow_As3RegexpExample() { // remove the "\" that just escape the following "\" if you want to test outside of flash compiler. var getGroup:RegExp = new RegExp("((?:[^\\(\\)]+)?) (?:\\() ( (?:[^\\(\\)]+)? ) (?:\\)) ((?:[^\\(\\)]+)?)", "ix") //removed g flag while (true) { tokenChain = replace(tokenChain,getGroup) if (tokenChain.search(getGroup) == -1) break; } trace("cummulativeEvaluable="+cummulativeEvaluable) } private var cummulativeEvaluable:Array = new Array() protected function analyseGrammar(matchedSubstring:String, capturedMatch1:String, capturedMatch2:String, capturedMatch3:String, index:int, str:String):String { trace("\nanalyseGrammar str:\t\t\t\t'"+str+"'") trace("analyseGrammar matchedSubstring:'"+matchedSubstring+"'") trace("analyseGrammar capturedMatchs:\t'"+capturedMatch1+"' '("+capturedMatch2+")' '"+capturedMatch3+"'") trace("analyseGrammar index:\t\t\t'"+index+"'") var blank:String = buildBlank(matchedSubstring.length) cummulativeEvaluable.push(StringUtil.trim(matchedSubstring)) // I could do soo much rigth here! return str.substr(0,index)+blank+str.substr(index+matchedSubstring.length,str.length-1) } private function replace(str:String,regExp:RegExp):String { var result:Object = regExp.exec(str) if (result) return analyseGrammar.apply(null,objectToArray(result)) return str } private function objectToArray(value:Object):Array { var array:Array = new Array() var i:int = 0 while (true) { if (value.hasOwnProperty(i.toString())) { array.push(value[i]) } else { break; } i++ } array.push(value.index) array.push(value.input) return array } protected function buildBlank(length:uint):String { var blank:String = "" while (blank.length != length) blank = blank+" " return blank } } 

}

它应该跟踪这个:

 analyseGrammar str: '2+(3-4*(4/6))-9(82+-21)' analyseGrammar matchedSubstring:'3-4*(4/6)' analyseGrammar capturedMatchs: '3-4*' '(4/6)' '' analyseGrammar index: '3' analyseGrammar str: '2+( )-9(82+-21)' analyseGrammar matchedSubstring:'2+( )-9' analyseGrammar capturedMatchs: '2+' '( )' '-9' analyseGrammar index: '0' analyseGrammar str: ' (82+-21)' analyseGrammar matchedSubstring:' (82+-21)' analyseGrammar capturedMatchs: ' ' '(82+-21)' '' analyseGrammar index: '0' cummulativeEvaluable=3-4*(4/6),2+( )-9,(82+-21) 
  • 将JSONstringparsing为JavaScript中的特定对象原型
  • :无法识别的select器发送到实例
  • 是否有一个Java XML API可以parsing文档而不parsing字符实体?
  • 如何将查询stringparsing为.NET中的NameValueCollection
  • parsing性能(如果,TryParse,Try-Catch)
  • 如何parsing一个小数点的string为一个双?
  • 你将如何去parsingMarkdown?
  • 在C#中读取和parsingJson文件
  • 如何在窗口上安装python 2.7美丽的汤4
  • 检查一个string是否可以parsing为Long而没有try-catch?
  • 我如何分割和parsingPython中的string?