解析表达式的问题

Question

还是用正则表达式吧，regexp包不错的说，和c/c++也兼容了

Answer 1

([asdf,123,ccc]∧[da,43,aaa])　∨　([fd,324,ddd]∧[asdf,43,eee])可将一个节点[asdf,123,ccc]附值为true或者false
最后生成的式子为(true && false) || (true && false)只要能够保障最后可为true或false就可以了

Answer 2

还是不明白你的逻辑
你到底是要比较字符串还是要比较变量?
([asdf,123,ccc]∧[da,43,aaa])　∨　([fd,324,ddd]∧[asdf,43,eee])
[]内的没有一对完全相同, 都不一样怎么赋值?你的式子是固定的([...]∧[...])∨([...]∧[...])
还是任意格式的?请将问题描述清楚!

Answer 3

简单的说就是要解析这样的表达式
(true && false) || (true && false)... 而且格式不固定,true,false ,||,&&都是随机生成的if("(true && false) || (true && false)... ")
{
  ...
}
else...

Answer 4

3Q我刚搜到一段源码,看来问题有望解决哦//:表达式解析-两栈算法.txt
//:Arithmetic.javapackage citi;
import java.util.Iterator;
import java.util.Stack;
import java.util.ArrayList;public class Arithmetic{
  //定义操作符，为简单起见，只涉及四则运算，可相应扩充之
  static String Operators="+-*/()#";
  //定义操作符的比较优先级，
  //其中1表示前面的操作符优于后面的操作符
  //   -1表示前面的操作符低于后面的操作符  
  //    0表示前面的操作符等于后面的操作符
  //    2表示前面的操作符不可能与后面的操作符相比较，如果碰到，则表达式有错  
  //PrecedeList[0][]表示+和+-*/()#这七个操作符相比较的优先级
  //PrecedeList[1][]表示-和+-*/()#这七个操作符相比较的优先级
  //以此类推
  static byte PrecedeList[][]={
                                { 1, 1,-1,-1,-1, 1, 1},
                                { 1, 1,-1,-1,-1, 1, 1},
                                { 1, 1, 1, 1,-1, 1, 1},
                                { 1, 1, 1, 1,-1, 1, 1},
                                {-1,-1,-1,-1,-1, 0, 2},
                                { 1, 1, 1, 1, 2, 1, 1},
                                {-1,-1,-1,-1,-1, 2, 0}};
  //定义数据中可能出现的数字和小数点，可以扩展
  static String Numbers="0123456789.";
  private Stack Operator,Operand;
  private ArrayList Expression;
  
  public Arithmetic(String inputStr){
   Operator=new Stack();
   Operator.push("#");
   Operand=new Stack();
   Expression=new ArrayList();
   Parse(inputStr);
  }
  //解析输入的表达式，将操作符和数据分开
  //如输入表达式2+3*(32-2)则解析成2 + 3 * ( 32 - 2 )这九个字符串
  private void Parse(String instr){
   String single;  
   int temp;
   String tempstr="#";
   for(int i=0;i<instr.length();i++){  
   single=instr.substring(i,i+1);
   //排除非操作符、数字的非法输入，如2+3m
   //Operators.indexOf(single)==6排除#
   if(Numbers.indexOf(single)<0 && (Operators.indexOf(single)<0 || Operators.indexOf(single)==6)){
   System.out.println("Input have wrong char:"+single);
   Expression.clear();
   return;
   }
   //获得前一个输入字符
   temp=Expression.size()-1;
   if(temp>-1){
   tempstr=(String)Expression.get(temp);
   }
   //排除连续两个操作符的情况，如3**2
   if(Operators.indexOf(single)>-1 && temp>-1 && Operators.indexOf(tempstr)>-1){
   System.out.println("Input have wrong format,two Operators are conjoint");
   Expression.clear();
   return;
   }  
   //如果当前字符是数字（包括.）而且前一字符也是数字，则将当前字符加到前一字符后面
   //其他情况均新添加一个元素
   if(Operators.indexOf(single)<0 && temp>-1 && Operators.indexOf(tempstr)<0){
   Expression.set(temp,tempstr+single);
   }  
   else{
     Expression.add(single);//其他情况均新添加一个元素
   }
   }  
   //为了算法处理方便起见，添加特殊字符＃
   Expression.add("#");   
  }
  
  //比较两个操作符的优先级
  private byte Precede(String firstOperator,String secondOperator){
   return PrecedeList[Operators.indexOf(firstOperator)][Operators.indexOf(secondOperator)];
  }  
  
  //对两个数据字符串进行运算
  private double Operate(String firstOperand,String Operator,String secondOperand){
   if(Operator.equals("+")){
   return (Double.parseDouble(firstOperand)+Double.parseDouble(secondOperand));
   }
   else if(Operator.equals("-")){
   return (Double.parseDouble(firstOperand)-Double.parseDouble(secondOperand));
   }
   else if(Operator.equals("*")){
   return (Double.parseDouble(firstOperand)*Double.parseDouble(secondOperand));
   }
   else if(Operator.equals("/")){
   return (Double.parseDouble(firstOperand)/Double.parseDouble(secondOperand));
   }
   else{
     System.out.println("Operator is wrong!Can throw a Exception");
     return 0;
    }
  }
  //采用两个栈对接解析后的表达式进行运算
  public double Compute(){
   if(Expression.isEmpty()){
   System.out.println("Expresion is empty");
   return 0;
   }
   Iterator it = Expression.iterator();
   String single;
   String firstOperand,secondOperand;
     
   single=(String)it.next();
   while(!(single.equals("#") && Operator.peek().equals("#"))){
   if(Operators.indexOf(single)<0){
   Operand.push(single);single=(String)it.next();
   }
   else{
     switch(Precede((String)Operator.peek(),single)){
      case -1:Operator.push(single);single=(String)it.next();break;
      case 0: Operator.pop();single=(String)it.next();break;
      case 1: 
              secondOperand=(String)Operand.pop();
              firstOperand=(String)Operand.pop();
              Operand.push(String.valueOf(Operate(firstOperand,(String)Operator.pop(),secondOperand)));break;
      case 2: System.out.println("Expression is wrong!Can throw a Exception");break;
     }
     }
   }  
    return Double.parseDouble((String)Operand.pop());
  }
  
  public static void main(String[] args){
   long t1 = System.currentTimeMillis();    
     
   Arithmetic t=new Arithmetic(args[0]);
   System.out.println(t.Compute());  
  
   long t2 = System.currentTimeMillis();
    System.out.println("Time needed: " + (t2 - t1));
  }
}

Answer 5

import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;public class Evaluator {
    private int count;    private ArrayList list1 = new ArrayList(16);
    private ArrayList list2 = new ArrayList(32);    private String[] unite(String[] s1, String[] s2) {
        Object[] obj;
        String[] result;
        list1.clear();        for (int i = 0; i < s1.length; i++) {
            if (!list1.contains(s1[i])) {
                list1.add(s1[i]);
            }
            for (int j = 0; j < s2.length; j++) {
                if (!s1[i].equals(s2[j]) && !list1.contains(s2[j])) {
                    list1.add(s2[j]);
                }
            }
        }        obj = list1.toArray();
        result = new String[obj.length];
        for (int i = 0; i < obj.length; i++) {
            result[i] = (String) obj[i];
        }        return result;
    }    private String[] intersect(String[] s1, String[] s2) {
        Object[] obj;
        String[] result;
        list1.clear();        for (int i = 0; i < s1.length; i++) {
            for (int j = 0; j < s2.length; j++) {
                if (s1[i].equals(s2[j]) && !list1.contains(s1[i])) {
                    list1.add(s1[i]);
                }
            }
        }        obj = list1.toArray();
        result = new String[obj.length];
        for (int i = 0; i < obj.length; i++) {
            result[i] = (String) obj[i];
        }        return result;
    }    private void print(String[] s) {
        for (int i = 0; i < s.length; i++) {
            System.out.println(s[i]);
        }
    }    private String prepare(String example) {
        StringBuffer sbuff = new StringBuffer(1024);
        Pattern p_var = Pattern.compile("\\[(.*?)\\]");
        Matcher m_var = p_var.matcher(example);        list2.clear();
        while (m_var.find()) {
            m_var.appendReplacement(sbuff, String.valueOf(count));
            list2.add(m_var.group(1).split(","));
            count++;
        }
        m_var.appendTail(sbuff);        return sbuff.toString();
    }    private String[] calc(String example) {
        String[] result;
        String expression;
        int operand_l;
        int operand_r;
        Pattern[] exp_p = {
            Pattern.compile("\\((\\d)([&|])(\\d)\\)"),
            Pattern.compile("(\\d)([|])(\\d)"),
            Pattern.compile("(\\d)([&])(\\d)"),
        };
        Matcher exp_m;
        expression = prepare(example);        for (int i = 0; i < exp_p.length; i++) {
            exp_m = exp_p[i].matcher(expression);            for (; exp_m.find(); count++) {
                operand_l = Integer.parseInt(exp_m.group(1));
                operand_r = Integer.parseInt(exp_m.group(3));
                if (exp_m.group(2).equals("&")) {
                    list2.add(intersect((String[]) list2.get(operand_l),
                            (String[]) list2.get(operand_r)));
                } else {
                    list2.add(unite((String[]) list2.get(operand_l),
                            (String[]) list2.get(operand_r)));
                }
                expression = exp_m.replaceFirst(String.valueOf(count));
                exp_m.reset(expression);
            }
        }        result = (String[]) list2.get(count - 1);        return result;
    }    public static void main(String[] args) {
        Evaluator eva = new Evaluator();
        String example = "[123,345]&([123,234,345]&[123,345,456])|([234,sdf,dfg]|[987,654,321])";
        String[] result = eva.calc(example);
        eva.print(result);
    }
}
根据我的理解这可能是你想要的解析
计算没有用后缀求值法, 用的是面向对象暴力法
注意: 表达式中英文混合使用可能会出错

Answer 6

registered(已注册)真是太不好意思了,我的问题表达的太不清楚了!
([asdf,123,ccc]∧[da,43,aaa])　∨　([fd,324,ddd]∧[asdf,43,eee])... 
这个是初始生成的,在我的程序里最终每个[]中的内容都会被转换成true或者是false最终要生成这样的式子:
if("(true && false) || (true && false)... ")
{
  ...
}
else...
要保证if()中的String格式正确并且最终可以被解析成boolean型感觉要做健壮太难了,要check的东西太多太多......

Answer 7

还有,("(true && false) || (true && false)... ")并不是固定格式的个数，组合方式都是根据具体情况生成的

Answer 8

总结一下:
解析是从([asdf,123,ccc]∧[da,43,aaa])　∨　([fd,324,ddd]∧[asdf,43,eee])... 开始的
是数据库中读出的数据,并且与或组合以及()不固定,但子节点:[asdf,123,ccc]的格式是固定的!最终结果是boolean型

Answer 9

([asdf,123,ccc]∧[da,43,aaa])　∨　([fd,324,ddd]∧[asdf,43,eee])... 如果解析后格式正确的话,经处理会在子节点加一个字段true或false,变成这样的形式:
([asdf,123,ccc,true]∧[da,43,aaa,false])　∨　([fd,324,ddd,true]∧[asdf,43,eee,false])... 然后再解析为
if("(true && false) || (true && false)... ")
{
  ...
}
else...也就是说在保证子节点[asdf,123,ccc]格式正确的前提下,再保证替换子节点后的"(true && false) || (true && false)... "格式正确

Answer 10

你这个问题也太复杂了"if("(true && false) || (true && false)... ")
{
  ...
}
else..."
你是要把他变成字符串"(true && false) || (true && false)... "
还是变成布尔表达式 (true && false) || (true && false)
还是最终的一个布尔值 true / false ?"([asdf,123,ccc]∧[da,43,aaa])　∨　([fd,324,ddd]∧[asdf,43,eee])... 如果解析后格式正确的话,经处理会在子节点加一个字段true或false,变成这样的形式:
([asdf,123,ccc,true]∧[da,43,aaa,false])　∨　([fd,324,ddd,true]∧[asdf,43,eee,false])..."
这个是你处理还是在本贴问题的范围之内?
如果是本贴问题,那怎么样才算格式正确?不正确怎么办?"也就是说在保证子节点[asdf,123,ccc]格式正确的前提下,再保证替换子节点后的"(true && false) || (true && false)... "格式正确"
怎么样算格式正确,怎么样算不正确?

Answer 11

第一个问题:
 变成字符串
 ([asdf,123,ccc]∧[da,43,aaa])　∨　([fd,324,ddd]∧[asdf,43,eee])... 如果解析后格 式正确的话,经处理会在子节点加一个字段true或false,变成这样的形式:
([asdf,123,ccc,true]∧[da,43,aaa,false])　∨　([fd,324,ddd,true]∧[asdf,43,eee,false])... 
 即只取每个节点里的true或false第二个问题
 处理不在本帖问题范围内
第三个问题
 [asdf,123,ccc]这个的格式是固定的,[xxx,xxx,xxx],保证是字符和数字就可以

Answer 12

我的想法是去出与或符号,加入一个数组,然后find节点的正则表达式,没有报错然后把节点替换成boolean的与或操作进行解析,最后返回true或false

Answer 13

我描述一下你看看对不对:1.我最初得到
([asdf,123,ccc,true]∧[da,43,aaa,false])　∧　([fd,324,ddd,true]∧[asdf,43,eee,false])
2.检查表达式每个[]中的内容, 是[xxx,xxx,xxx]格式且xxx为字母或数字继续, 否则返回
3.根据每个[]单元中的 true/false 进行"与或运算"得到最终的一个 true/false
还有两个问题:
1.你的表达式中是否可以有空格(空格处理起来比较麻烦)
2.你的与或运算赋是否必须为"∧和∨", 是否可变为 "&和|" 或 "&&和||" 或 "AND和OR"

Answer 14

是的,思就是这个意这个表达式是由操作者生成的,所以任何可能都是有的,甚至是中文,但这些由我自己处理就可以了运算符用什么都可以,但要表达与/或的意思我觉得这个要check的东西很多,如果你的时间不允许的话,可以不用做的特别健壮

Answer 15

Mastering Regular Expressions
http://www.amazon.com/exec/obidos/ASIN/1565922573/qid%3D1020015647/sr%3D1-1/ref%3Dsr%5F1%5F1/104-8819039-5717504#product-details你这个东西什么时候要?

Answer 16

import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;/**
 * A class for evaluate certain expression.
 */
public class Evaluator2 {
    private Pattern[] correct_exp = {
        Pattern.compile("\\[(.+?)\\]"),
        Pattern.compile("\\w++,\\w++,\\w++,(?i:(true)|(false))"),
    };    private Pattern unit = Pattern.compile("\\[\\w++,\\w++,\\w++,(\\w++)\\]");    private Pattern[] exp_p = {
        Pattern.compile("\\((?!\\()([\\d&|]++)\\)"),
        Pattern.compile("(\\d++)([&])(\\d++)"),
        Pattern.compile("(\\d++)([|])(\\d++)"),
    };    private int count;    private ArrayList list = new ArrayList(64);
    /**
     * Check expression unit correctness.
     *
     * @param exp
     * @return
     */
    private boolean isCorrect(String exp) {
        Matcher m1 = correct_exp[0].matcher(exp);
        Matcher m2 = correct_exp[1].matcher(exp);        while (m1.find()) {
            m2.reset(m1.group(1));
            if (!m2.matches()) {
                return false;
            }
        }        return true;
    }    /**
     * Prepare internal expression.
     *
     * @param exp
     * @return
     */
    private String prepare(String exp) {
        Matcher m = unit.matcher(exp);
        StringBuffer sbuff = new StringBuffer();        list.clear();
        while (m.find()) {
            m.appendReplacement(sbuff, String.valueOf(count));
            list.add(count, Boolean.valueOf(m.group(1)));
            count++;
        }
        m.appendTail(sbuff);        return sbuff.toString();
    }    private Boolean and(Boolean b1, Boolean b2) {
        return new Boolean(b1.booleanValue() && b2.booleanValue());
    }    private Boolean or(Boolean b1, Boolean b2) {
        return new Boolean(b1.booleanValue() || b2.booleanValue());
    }    /**
     * Evaluate expression.
     *
     * @param exp
     * @return
     */
    private Boolean evaluate(String exp) {
        Matcher m;        if (!isCorrect(exp)) {
            return null;
        }        count = 0;
        list.clear();
        exp = prepare(exp);
        //System.out.println("exp = " + exp);        for (int i = 0; i < 3; i++) {
            m = exp_p[i].matcher(exp);
            for (; m.find(); count++) {
                list.add(count, eva(m.group(0)));
                exp = m.replaceFirst(String.valueOf(count));
                m.reset(exp);
            }
        }        return (Boolean) list.get(count - 1);
    }    /**
     * Evaluate sub expression.
     *
     * @param sub_exp
     * @return
     */
    private Boolean eva(String sub_exp) {
        int operand_l;
        int operand_r;
        Matcher m;        //System.out.println("exp = " + sub_exp);
        for (int i = 1; i < 3; i++) {
            m = exp_p[i].matcher(sub_exp);
            for (; m.find(); count++) {
                operand_l = Integer.parseInt(m.group(1));
                operand_r = Integer.parseInt(m.group(3));
                if (m.group(2).equals("&")) {
                    list.add(count, and((Boolean) list.get(operand_l),
                            (Boolean) list.get(operand_r)));
                } else {
                    list.add(count, or((Boolean) list.get(operand_l),
                            (Boolean) list.get(operand_r)));
                }
                sub_exp = m.replaceFirst(String.valueOf(count));
                m.reset(sub_exp);
            }
            //System.out.println("exp = " + sub_exp);
        }        return (Boolean) list.get(count - 1);
    }
    public static void main(String[] args) {
        /* Do NOT allow spaces! */
        String example = "([c,c,c,true]&[c,c,c,false]|[c,c,c,true])" +
                "&[c,c,c,true]&([c,c,c,false]|[c,c,c,true])";
        Evaluator2 e = new Evaluator2();
        System.out.println(e.evaluate(example));
    }
}你再测试测试

Answer 17

有个疏忽
你用的时候把 evaluate 方法改成 public

Answer 18

多谢你这两天的帮忙,问题基本已经解决
如果你有兴趣的话可以用不同的方法来把这个帖子完善了,程序写健全一些,
我把我的方法完善后也贴上,然后再把这个帖子结了.我想借这个机会把学过的东西都用一用^_^如果没时间的话就通知我一声,我马上结
你去数据结构留个脚印吧,我先结了它.谁说java版怎么怎么了,解决问题还是要来这里^_^

Answer 19

import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;/**
 * A class for evaluate certain expression.
 */
public class Evaluator2 {
    private Pattern[] correct_exp = {
        Pattern.compile("\\[(.+?)\\](?!\\])"),
        Pattern.compile("\\w++,\\w++,\\w++,(?i:(true)|(false))"),
    };    private Pattern unit = Pattern.compile("\\[\\w++,\\w++,\\w++,(\\w++)\\]");    private Pattern[] exp_p = {
        Pattern.compile("\\((?!\\()([\\d&|]++)\\)"),
        Pattern.compile("(\\d++)([&])(\\d++)"),
        Pattern.compile("(\\d++)([|])(\\d++)"),
    };    private int count;    private ArrayList list = new ArrayList(64);
    /**
     * Check expression unit correctness.
     *
     * @param exp
     * @return
     */
    private boolean isCorrect(String exp) {
        int count_unit = 1;
        int count_error = 1;
        boolean correct = true;
        String error_msg = "\n";
        Matcher m1 = correct_exp[0].matcher(exp);
        Matcher m2 = correct_exp[1].matcher(exp);        while (m1.find()) {
            m2.reset(m1.group(1));
            if (!m2.matches()) {
                error_msg += "Error " + count_error +
                        ": unit " + count_unit + " \"" + m1.group(0) + "\"\n";
                count_error++;
                correct = false;
            }
            count_unit++;
        }        if (!correct) {
            throw new IllegalArgumentException(error_msg);
        }        return correct;
    }    /**
     * Prepare internal expression.
     *
     * @param exp
     * @return
     */
    private String prepare(String exp) {
        Matcher m = unit.matcher(exp);
        StringBuffer sbuff = new StringBuffer();        list.clear();
        while (m.find()) {
            m.appendReplacement(sbuff, String.valueOf(count));
            list.add(count, Boolean.valueOf(m.group(1)));
            count++;
        }
        m.appendTail(sbuff);        return sbuff.toString();
    }    private Boolean and(Boolean b1, Boolean b2) {
        return new Boolean(b1.booleanValue() && b2.booleanValue());
    }    private Boolean or(Boolean b1, Boolean b2) {
        return new Boolean(b1.booleanValue() || b2.booleanValue());
    }    /**
     * Evaluate expression.
     *
     * @param exp
     * @return
     */
    public Boolean evaluate(String exp) {
        Matcher m;        isCorrect(exp);        count = 0;
        list.clear();
        exp = prepare(exp);
        //System.out.println("exp = " + exp);        for (int i = 0; i < 3; i++) {
            m = exp_p[i].matcher(exp);
            for (; m.find(); count++) {
                list.add(count, eva(m.group(0)));
                exp = m.replaceFirst(String.valueOf(count));
                m.reset(exp);
            }
        }        return (Boolean) list.get(count - 1);
    }    /**
     * Evaluate sub expression.
     *
     * @param sub_exp
     * @return
     */
    private Boolean eva(String sub_exp) {
        int operand_l;
        int operand_r;
        Matcher m;        //System.out.println("exp = " + sub_exp);
        for (int i = 1; i < 3; i++) {
            m = exp_p[i].matcher(sub_exp);
            for (; m.find(); count++) {
                operand_l = Integer.parseInt(m.group(1));
                operand_r = Integer.parseInt(m.group(3));
                if (m.group(2).equals("&")) {
                    list.add(count, and((Boolean) list.get(operand_l),
                            (Boolean) list.get(operand_r)));
                } else {
                    list.add(count, or((Boolean) list.get(operand_l),
                            (Boolean) list.get(operand_r)));
                }
                sub_exp = m.replaceFirst(String.valueOf(count));
                m.reset(sub_exp);
            }
            //System.out.println("exp = " + sub_exp);
        }        return (Boolean) list.get(count - 1);
    }
    public static void main(String[] args) {
        /* Do NOT allow spaces! */
        String example = "([c,c,c,true]]&[[[c,c,c,false]]]|[c,c,c,true])" +
                "&[c,c,c,true]&([c,c,c,falSe]]|[[c,c,c,true])";
        /*String example = "([c,c,c,true]&[c,c,c,false]|[c,c,c,true])" +
                "&[c,c,c,true]&([c,c,c,falSe]|[c,c,c,true])";*/
        Evaluator2 e = new Evaluator2();        try {
            System.out.println(e.evaluate(example));
        } catch (IllegalArgumentException ex) {
            ex.printStackTrace();
        }
    }
}这个只能发现[](单元)内的错误, 无法发现()&|等错误
正句语法检查你先前说不属于问题范围内所以没有做