不好意思请问如何验证四则运算数学表达式的合法性?

Question

不好意思又来提问了... 编译原理什么的学得太差了, 可现在又要用... 想求一个能验证四则运算数学表达式 (比如: (A + B)/C^2 - D*E) 合法性的程序... 在论坛搜索了一下, 大部分都是只给了一个提示比如 "这个要用栈啊... ", "编译原理书上有啊... " 什么的. 当然了我想这些大家都指导, 但关键是如何实现. 规则很普通: 比如 "(A +", (A + B", "A^" 这样缺失左/右括号或者运算符前/后缺失运算数的必然都是非法表达式. 希望大家可以给一个可以用的Java程序或者稍加修改即可使用的Java程序 (比如之前求的一个计算数学表达式的程序就是修改了一下填加了计算乘方的功能就达到要求了), 谢谢大家!!

Answer 1

正则表达式（转）Regex regex = new Regex(@"
^           (?#匹配开头)
\s*[-+]?         (?#开头可以出现正负号)
(((([0-9]\,?[0-9]*)+\.?[0-9]*))+(\s*$|\s*([-+*/]+?|[<>!=]+)\s*))*  (?#可选数-符号-数-符号-……-数-符号或结尾)
(
 (
  (?<o>\()\s*       (?#左括号，保存到o名字下)
  [-+]?        (?#可选正负号)
  (((([0-9]\,?[0-9]*)+\.?[0-9]*))+\s*([-+*/]+?|[<>!=]+)\s*)* (?#可选数-符-数-符……)
 )+          (?#可以重复出现左括号)
 ((([0-9]\,?[0-9]*)+\.?[0-9]*))+      (?#左右括号之间最起码需要一个操作数)
 (
  \s*(?<-o>\))      (?#右括号，匹配的同时去掉一个左括号)
  (\s*([-+*/]+?|[<>!=]+)\s*((([0-9]\,?[0-9]*)+\.?[0-9]*))+)* (?#可选符-数-符-数……)
 )+          (?#可以重复出现右括号，仅当还有左括号剩余)
 (\s*$|\s*([-+*/]+?|[<>!=]+)\s*)      (?#要么结尾，要么在下一个左括号出现之前出现一个运算符)
)*           (?#重复出现左括号)
(?(o)(?!))         (?#如果还有左括号剩余就不匹配任何东西)
(?<=[0-9)]\s*)         (?#检查结尾前是否数字或右括号)
\s*$           (?#匹配结尾)
", RegexOptions.IgnorePatternWhitespace);

Answer 2

采用自顶向下分析法，运算符优先匹配，即使用ansi-C编写，代码也很容易。
计算过程也就是验证过程，而且可以抛出适当的异常属性（比如，错在哪儿）。像这样构造复杂正则，最后只验个“合格/不合格”，真的费脑子又不划算。

Answer 3

如果括号的层次不确定，那么在 Java 当中没办法采用正则表达式来进行验证。1 楼提供的正则表达式在 Java 中不能用，那个正则表达式中含有 .net 中特有的
平衡组 (?<o>)、(?<-o>)，这种语法目前仅有 .net 能支持。有了这种语法，正则
表达式可以匹配嵌套结构的字符串。在 Java 中建议采用栈的方式来进行检查。

Answer 4

不就是喜欢代码么！给你吧：http://topic.csdn.net/u/20081011/11/c69b34f6-7605-44a4-918b-a4bed78e8654.html

Answer 5

喂喂。。宝宝别生气啦
数据结构的时候就有学这跟编译原理搭个P界啊
没层次的括号匹配如果用正则，是不可能实现的。。啥语言实现的PERL都搞不定
也就是个操作数，操作符的问题。优先级的问题，你说最后多个操作符或者操作数出来，是不是就是不合法了
合法了就直接帮你把4则运算结果都算出来好不好？
给你个提示，自己去查去
居然把我们可爱的火龙果弄火了。。啦出去枪毙5分钟

Answer 6

编译原理要学好是不容易，不过有现成的工具，写个解析器什么的也不是什么难事。lz可以去看看ANTLRWorks。学起来不难，学会了很有用。写了个四则运算的语法规则，可以粘到ANTLRWorks看。NUMBER部分写得很简单，只能识别正整数，lz根据要求自己改写吧。文件名：MathLexer.glexer grammar MathLexer;@header { org.myorg.math; }VAR : 'A'..'Z';
NUMBER : '1'..'9' '0'..'9' +;
PLUS : '+';
MINUS : '-';
TIMES : '*';
OVER : '/';
TO_THE_NTH_POWER
: '^';
LPAREN : '(';
RPAREN : ')';文件名：MathParser.gparser grammar MathParser;options {
backtrack = true;
}tokens {
VAR;
NUMBER;
PLUS;
MINUS;
TIMES;
OVER;
TO_THE_NTH_POWER;
LPAREN;
RPAREN;
}@header { org.myorg.math; }expr : level_3_expr
| addition_subtraction_expr
;level_1_expr
: VAR
| NUMBER
| parenthesis_expr
;

level_2_expr
: level_1_expr
| power_expr
;

level_3_expr
: level_2_expr
| multiplication_division_expr
;

parenthesis_expr
: LPAREN expr RPAREN
;power_expr
: level_1_expr TO_THE_NTH_POWER level_1_expr
;multiplication_division_expr
: level_2_expr TIMES level_2_expr
| level_2_expr OVER level_2_expr
;addition_subtraction_expr
: level_3_expr PLUS level_3_expr
| level_3_expr MINUS level_3_expr
;公司不能上传图片，贴个官网的图片。