完整的Java表达式算法，扩充容易。

完整的Java表达式算法

---扩充容易

本文的表达式求值采用标准的算法。首先从最简单的表达式求值开始，到后面的高级表达式求值。大郅算法如下，首先将表达式转换为后序表达式，然后对后序表达式求值。表示式求值的关键步骤式表达式语义的解析和分割，而对于表达式的求值反而简单。

在实际应用中，经常会有如下的场景：

1、对一行数据进行运算，例如：总价=单价*数量。

2、对集合数据进行运算，例如：平均销售价格=sum(单价*数量)/sum(数量)。

3、对集合数据进行运算，例如：全校平均成绩=(sum(数学平均分)*sum(数学考试人数)+sum(语文平均分)*sum(语文考试人数))/(sum(数学考试人数+语文考试人数)。

本文中的算法完全可以解决此类问题。

一、将公式变换为后序表达式

1)检查输入的下一元素。

2)假如是个操作数，输出。

3)假如是个开括号，将其压栈。

4)假如是个运算符，则

i) 假如栈为空，将此运算符压栈。

ii) 假如栈顶是开括号，将此运算符压栈。

iii) 假如此运算符比栈顶运算符优先级高，将此运算符压入栈中。

iv) 否则栈顶运算符出栈并输出，重复步骤4。

5)假如是个闭括号，栈中运算符逐个出栈并输出，直到遇到开括号。开括号出栈并丢弃。

6)假如输入还未完毕，跳转到步骤1。

7)假如输入完毕，栈中剩余的所有操作符出栈并输出它们。

算法如下：

  
  public static Stack<String> convertToPostfix (StringSplit x) {
    String s = x.getNext () ;
    Stack<String> st = new Stack<String> () ;
    Stack<String> rSt = new Stack<String> () ;
    while (s != null) {
      if (isBlank (s)) {
        //break;
      } else if (isOpenParenthesis (s)) {
        st.push (s) ;
      } else if (isCloseParenthesis (s)) {
        String as = null ;
        if (st.isEmpty ()) {
          System.out.println ("错误：缺少(") ;
        } else {
          as = st.pop () ;
          while (!isOpenParenthesis (as)) {
            rSt.push (as) ;
            if (st.isEmpty ()) {
              System.out.println ("错误：缺少(") ;
              break ;
            } else {
              as = st.pop () ;
            }
          }
        }
      } else if (isOperator (s)) {
        if (!st.isEmpty ()) {
          String as = st.pop () ;
          while (priority (as) >= priority (s)) {
            rSt.push (as) ;
            if (st.isEmpty ()) {
              as = null ;
            } else {
              as = st.pop () ;
            }
          }
          if (as != null) {
            st.push (as) ;
          }
          st.push (s) ;
        } else {
          st.push (s) ;
        }
      } else {
        rSt.push (s) ;
      }
      s = x.getNext () ;
    }
 
    while (!st.isEmpty ()) {
      String as = st.pop () ;
      if (isOpenParenthesis (as)) {
        System.out.println ("错误：缺少)") ;
      } else if (isCloseParenthesis (as)) {
        System.out.println ("错误：缺少(") ;
      } else {
        rSt.push (as) ;
      }
    }
    Stack<String> nSt = new Stack<String> () ;
    while (!rSt.empty ()) {
      nSt.push (rSt.pop ()) ;
    }
    return nSt ;
  }

类StringSplit是接口，目的是将表示式进行拆分，拆分为操作数、括号、运算符。本文中实现了单一字符解析、多字符解析以及函数解析等功能。以满足不同的应用场景。

  
package net.csdn.blog.z3h.util ;
 
public interface StringSplit {
  String getNext () ;
}

二、对后序表达式进行求值计算

1)初始化一个空堆栈

2)从左到右读入后缀表达式

i)如果字符是一个操作数，把它压入堆栈。

ii)如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈。如果您不能够弹出两个操作数，后缀表达式的语法就不正确。

3)到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。

  
  public static double numberCalculate (Stack<String> st) {
    Stack<String> tSt = new Stack<String> () ;
    while (!st.empty ()) {
      String a = st.pop () ;
      //System.out.println (a) ;
      if (isOperator (a)) {
        double d2 = Double.parseDouble (tSt.pop ()) ;
        double d1 = Double.parseDouble (tSt.pop ()) ;
        double d3 = 0 ;
        if ("+".equals (a)) {
          d3 = d1 + d2 ;
        } else if ("-".equals (a)) {
          d3 = d1 - d2 ;
        } else if ("*".equals (a)) {
          d3 = d1 * d2 ;
        } else if ("/".equals (a)) {
          d3 = d1 / d2 ;
        }
        tSt.push (String.valueOf (d3)) ;
      } else {
        tSt.push (a) ;
      }
    }
    return Double.parseDouble (tSt.pop ()) ;
  }

三、完整的求值

单字符表达式分割对象。

  
package net.csdn.blog.z3h.util ;
 
public class CharSplit
    implements StringSplit {
  private String s ;
 
  private int pos = 0 ;
 
  public CharSplit (String s) {
    this.s = s ;
  }
 
  public String getNext () {
    if (pos < s.length ()) {
      return s.charAt (pos++) + "" ;
    } else {
      return null ;
    }
  }
}

表达式求值示例：

  
           //单字符求值。
            //表达式分割对象
           StringSplit split = new CharSplit("2*3/(2-1)+5*(4-1)");
           //将表达式转化位后序表达式
           Stack<String> postFixStack = Expression.convertToPostfix(split);
           //对后序表达式进行运算
           double result = Expression.numberCalculate(postFixStack);
           System.out.println (result) ;

四、高级表达式应用

在实际应用中，经常会有如下的场景：

1、 对一行数据进行运算，例如总价=单价*数量。

2、 对集合数据进行运算，例如：平均销售价格=sum(单价*数量)/sum(数量)。

  
           StringSplit split = new FunctionSplit (
               "(a12+b23+c34)/($9+c34-12-b23)+9") ; //$9 表示"9",9表示9
           Stack<String> postFixStack = Expression.convertToPostfix (split);
           double result =Expression.rowCalculate (rowData ,postFixStack);
           System.out.println (result) ;

对集合数据进行运算示例：

  
           List<Map<String,Double>> dataTable = new ArrayList<Map<String,Double>> () ;
           ......
 
           StringSplit split = new FunctionSplit (
               "(sum('a'+'b'+'c'))/rowcount()-sum('a')") ;
           Stack<String> postFixStack = Expression.convertToPostfix (split);
           double result = Expression.tableCalculate (dataTable,postFixStack);
           System.out.println(result);

对一行数据求值的算法

  
  /**
   * 对Map<String,Double>求值.
   * 例如：相应的表达式为
   * “(a+b)/2”表示列a和列b的和的平均
   * “(a+b)/$4”表示列a与列b求和，然后除 列4
   * @param map DataObject
   * @param st Stack
   * @return double
   */
  public static double rowCalculate (Map<String,Double> map , Stack<String> sourceStack) {
      Stack<String> calStack = new Stack<String> () ;
      @SuppressWarnings("unchecked")
      Stack<String> cloneStack = (Stack<String>)sourceStack.clone();; //保证之前的栈不变.
      while (!cloneStack.empty ()) {
        String a = cloneStack.pop () ;
        //System.out.println (a) ;
        if (isOperator (a)) {
          double d2 = doValues (map , calStack.pop ()) ;
          double d1 = doValues (map , calStack.pop ()) ;
          double d3 = 0 ;
          if ("+".equals (a)) {
            d3 = d1 + d2 ;
          } else if ("-".equals (a)) {
            d3 = d1 - d2 ;
          } else if ("*".equals (a)) {
            d3 = d1 * d2 ;
          } else if ("/".equals (a)) {
            d3 = d1 / d2 ;
          }
          calStack.push (String.valueOf (d3)) ;
        } else {
          calStack.push (a) ;
        }
      }
      return doValues (map , calStack.pop ()) ;
    }
 
  private static double doValues ( Map<String,Double> map , String columnName ){
    //System.out.println(columnName);
    columnName = columnName.replaceAll ("'" , "") ;
    columnName = columnName.replaceAll ("\"" , "") ;
    boolean isColumnName = false;
    if ( columnName.startsWith("$")){
      isColumnName = true;
      columnName = columnName.substring(1);
    }
    if ( isColumnName ){
      try{
        return map.get (columnName) ;
      }catch ( Exception sysEx ){
        return 0;
      }
    }else{
      try {
        return Double.parseDouble (columnName) ;
      } catch (NumberFormatException e) {
        try {
          return map.get (columnName) ;
        } catch (Exception sysEx) {
          return 0 ;
        }
      }
    }
  }

对二维数据进行求值的算法

  
  public static double tableCalculate (List<Map<String,Double>> ds , Stack<String> sourceStack) {
    Stack<String> callStack = new Stack<String> () ;
    @SuppressWarnings("unchecked")
    Stack<String> cloneStack = (Stack<String>)sourceStack.clone(); //保证之前的栈不变.
    while (!cloneStack.empty ()) {
      String a = cloneStack.pop () ;
      //System.out.println (a) ;
      if (isOperator (a)) {
        double d2 = tableFunValue (ds , callStack.pop ()) ;
        double d1 = tableFunValue (ds , callStack.pop ()) ;
        double d3 = 0 ;
        if ("+".equals (a)) {
          d3 = d1 + d2 ;
        } else if ("-".equals (a)) {
          d3 = d1 - d2 ;
        } else if ("*".equals (a)) {
          d3 = d1 * d2 ;
        } else if ("/".equals (a)) {
          d3 = d1 / d2 ;
        }
        callStack.push (String.valueOf (d3)) ;
      } else {
        callStack.push (a) ;
      }
    }
    return tableFunValue (ds , callStack.pop ()) ;
  }
 
  private static double tableFunValue (List<Map<String,Double>> ds , String fun) {
    try {
      fun = fun.trim () ;
      fun = fun.replaceAll (" " , "") ;
      fun = fun.replaceAll ("\t" , "") ;
      fun = fun.toLowerCase () ;
      String cn ;
      if (fun.startsWith ("sum")) {
        cn = fun ;
        cn = cn.substring (3) ;
        Stack<String> st = Expression.convertToPostfix (new FunctionSplit (cn)) ;
        double sum = 0 ;
        for (int i = 0 ; i < ds.size() ; i++) {
          sum += Expression.rowCalculate (ds.get (i) , st) ;
        }
        return sum ;
      } else if (fun.startsWith ("avg")) {
        cn = fun ;
        cn = cn.substring (3) ;
        Stack<String> st = Expression.convertToPostfix (new FunctionSplit (cn)) ;
        double sum = 0 ;
        for (int i = 0 ; i < ds.size () ; i++) {
          sum += Expression.rowCalculate (ds.get (i) , st) ;
        }
        return sum / ds.size () ;
      } else if (fun.startsWith ("min")) {
        cn = fun ;
        cn = cn.substring (3) ;
        Stack<String> st = Expression.convertToPostfix (new FunctionSplit (cn)) ;
        double min = Double.MAX_VALUE ;
        for (int i = 0 ; i < ds.size () ; i++) {
          double tmin = Expression.rowCalculate (ds.get (i) , st) ;
          if (tmin < min) {
            min = tmin ;
          }
        }
        return min;
      } else if (fun.startsWith ("max")) {
        cn = fun ;
        cn = cn.substring (3) ;
        Stack<String> st = Expression.convertToPostfix (new FunctionSplit (cn)) ;
        double max = Double.MIN_VALUE ;
        for (int i = 0 ; i < ds.size () ; i++) {
          double tmax = Expression.rowCalculate (ds.get (i) , st) ;
          if (tmax > max) {
            max = tmax ;
          }
        }
        return max ;
      } else if (fun.startsWith ("rowcount")) {
        return ds.size () ;
      } else {
        return Double.parseDouble (fun) ;
      }
    } catch (Exception ex) {
      ex.printStackTrace () ;
      return 0 ;
    }
  }

五、其他辅助函数

  
  /**
   * 字符串是运算符号.
   * @param s String
   * @return boolean
   */
  public static boolean isOperator (String s) {
    if ("+".equals (s) || "-".equals (s) || "*".equals (s) || "/".equals (s)) {
      return true ;
    } else {
      return false ;
    }
  }
 
  /**
   * 字符是运算符号.
   */
  public static boolean isOperator (char s) {
    if ('+' == s || '-' == s || '*' == s || '/' == s) {
      return true ;
    } else {
      return false ;
    }
  }
 
  public static boolean isOpenParenthesis (String s) {
    return "(".equals (s) ;
  }
 
  public static boolean isOpenParenthesis (char s) {
    return '(' == s ;
  }
 
  public static boolean isCloseParenthesis (String s) {
    return ")".equals (s) ;
  }
 
  public static boolean isCloseParenthesis (char s) {
    return ')' == s ;
  }
 
  public static boolean isBlank (String s) {
    if (" ".equals (s) || "\t".equals (s)) {
      return true ;
    } else {
      return false ;
    }
  }
 
  public static boolean isBlank (char s) {
    if (' ' == s || '\t' == s) {
      return true ;
    } else {
      return false ;
    }
  }
 
  public static boolean isDot (char s) {
    return s == '.' ;
  }
 
  static int priority (String s) {
    if (s == null) {
      return -1 ;
    }
    char c = s.charAt (0) ;
    if (c == '^') {
      return 3 ; /*Exponential operator*/
    }
    if (c == '*' || c == '/' || c == '%') {
      return 2 ;
    } else if (c == '+' || c == '-') {
      return 1 ;
    } else {
      return 0 ;
    }
  }

六、小结

实际上在实际应用中也会有如下的应用场景。

求每一行数据和平均数据平均值的偏差。次问题，可以在方法tableCalculate的基础上在进行适当的扩充即可。

  
            List<Map<String, Double>> dataTable = null;
           StringSplit split = new FunctionSplit(
                  "(avg(price)-price)/avg(price)*100.0");
           Stack<String> postFixStack = Expression.convertToPostfix(split);
           for (int rowNumber=0;rowNumber<dataTable.size();rowNumber++) {
              Map<String,Double> row = dataTable.get(rowNumber);
              System.out.println("本月销售价格:"+row.get("price"));
              System.out.println("本月销售价格偏差"
                     + Expression.tableRowCalculate(dataTable, rowNumber,
                            postFixStack));
           }     

完整的代码请到这里 http://z3h.download.csdn.net/下载。