完整的Java表达式算法.doc

完整的Java表达式算法-扩充容易本文的表达式求值采用标准的算法。首先从最简单的表达式求值开始，到后面的高级表达式求值。大郅算法如下，首先将表达式转换为后序表达式，然后对后序表达式求值。表示式求值的关键步骤式表达式语义的解析和分割，而对于表达式的求值反而简单。在实际应用中，经常会有如下的场景：1、对一行数据进行运算，例如：总价=单价*数量。2、对集合数据进行运算，例如：平均销售价格=sum(单价*数量)/sum(数量)。3、对集合数据进行运算，例如：全校平均成绩=(sum(数学平均分)*sum(数学考试人数)+sum(语文平均分)*sum(语文考试人数)/(sum(数学考试人数+语文考试人数)。本文中的算法完全可以解决此类问题。一、将公式变换为后序表达式1)检查输入的下一元素。2)假如是个操作数，输出。3)假如是个开括号，将其压栈。4)假如是个运算符，则i) 假如栈为空，将此运算符压栈。ii) 假如栈顶是开括号，将此运算符压栈。iii) 假如此运算符比栈顶运算符优先级高，将此运算符压入栈中。iv) 否则栈顶运算符出栈并输出，重复步骤4。5)假如是个闭括号，栈中运算符逐个出栈并输出，直到遇到开括号。开括号出栈并丢弃。6)假如输入还未完毕，跳转到步骤1。7)假如输入完毕，栈中剩余的所有操作符出栈并输出它们。算法如下：view plaincopy to clipboardprint? public static Stack convertToPostfix (StringSplit x) String s = x.getNext () ; Stack st = new Stack () ; Stack rSt = new Stack () ; 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 nSt = new Stack () ; while (!rSt.empty () nSt.push (rSt.pop () ; return nSt ; public static Stack convertToPostfix (StringSplit x) String s = x.getNext () ; Stack st = new Stack () ; Stack rSt = new Stack () ; 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 nSt = new Stack () ; while (!rSt.empty () nSt.push (rSt.pop () ; return nSt ; 类StringSplit是接口，目的是将表示式进行拆分，拆分为操作数、括号、运算符。本文中实现了单一字符解析、多字符解析以及函数解析等功能。以满足不同的应用场景。view plaincopy to clipboardprint? package net.csdn.blog.z3h.util ; public interface StringSplit String getNext () ; package net.csdn.blog.z3h.util ; public interface StringSplit String getNext () ;二、对后序表达式进行求值计算1)初始化一个空堆栈2)从左到右读入后缀表达式i)如果字符是一个操作数，把它压入堆栈。ii)如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈。如果您不能够弹出两个操作数，后缀表达式的语法就不正确。3)到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。view plaincopy to clipboardprint? public static double numberCalculate (Stack st) Stack tSt = new Stack () ; 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 () ; public static double numberCalculate (Stack st) Stack tSt = new Stack () ; 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 () ; 三、完整的求值单字符表达式分割对象。view plaincopy to clipboardprint? 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 ; 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 ; 表达式求值示例：view plaincopy to clipboardprint?/单字符求值。 /表达式分割对象 StringSplit split = new CharSplit(2*3/(2-1)+5*(4-1); /将表达式转化位后序表达式 Stack postFixStack = Expression.convertToPostfix(split); /对后序表达式进行运算 double result = Expression.numberCalculate(postFixStack); System.out.println (result) ; /单字符求值。 /表达式分割对象 StringSplit split = new CharSplit(2*3/(2-1)+5*(4-1); /将表达式转化位后序表达式 Stack postFixStack = Expression.convertToPostfix(split); /对后序表达式进行运算 double result = Expression.numberCalculate(postFixStack); System.out.println (result) ;四、高级表达式应用在实际应用中，经常会有如下的场景：1、 对一行数据进行运算，例如总价=单价*数量。2、 对集合数据进行运算，例如：平均销售价格=sum(单价*数量)/sum(数量)。view plaincopy to clipboardprint?StringSplit split = new FunctionSplit ( (a12+b23+c34)/($9+c34-12-b23)+9) ; /$9 表示9,9表示9 Stack postFixStack = Expression.convertToPostfix (split); double result =Expression.rowCalculate (rowData ,postFixStack); System.out.println (result) ; StringSplit split = new FunctionSplit ( (a12+b23+c34)/($9+c34-12-b23)+9) ; /$9 表示9,9表示9 Stack postFixStack = Expression.convertToPostfix (split); double result =Expression.rowCalculate (rowData ,postFixStack); System.out.println (result) ;对集合数据进行运算示例：view plaincopy to clipboardprint?ListMap dataTable = new ArrayListMap () ; . StringSplit split = new FunctionSplit ( (sum(a+b+c)/rowcount()-sum(a) ; Stack postFixStack = Expression.convertToPostfix (split); double result = Expression.tableCalculate (dataTable,postFixStack); System.out.println(result); ListMap dataTable = new ArrayListMap () ; . StringSplit split = new FunctionSplit ( (sum(a+b+c)/rowcount()-sum(a) ; Stack postFixStack = Expression.convertToPostfix (split); double result = Expression.tableCalculate (dataTable,postFixStack); System.out.println(result);对一行数据求值的算法view plaincopy to clipboardprint? /* * 对Map求值. * 例如：相应的表达式为 * “(a+b)/2”表示列a和列b的和的平均 * “(a+b)/$4”表示列a与列b求和，然后除 列4 * param map DataObject * param st Stack * return double */ public static double rowCalculate (Map map , Stack sourceStack) Stack calStack = new Stack () ; SuppressWarnings(unchecked) Stack cloneStack = (Stack)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 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 ; /* * 对Map求值. * 例如：相应的表达式为 * “(a+b)/2”表示列a和列b的和的平均 * “(a+b)/$4”表示列a与列b求和，然后除 列4 * param map DataObject * param st Stack * return double */ public static double rowCalculate (Map map , Stack sourceStack) Stack calStack = new Stack () ; SuppressWarnings(unchecked) Stack cloneStack = (Stack)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 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 ; 对二维数据进行求值的算法view plaincopy to clipboardprint? public static double tableCalculate (ListMap ds , Stack sourceStack) Stack callStack = new Stack () ; SuppressWarnings(unchecked) Stack cloneStack = (Stack)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 (ListMap 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 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 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 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 st = Expression.convertToPostfix (new FunctionSplit (cn) ; double max = Double.MIN_VALUE ; for (int i = 0 ; i 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 ; public static double tableCalculate (ListMap ds , Stack sourceStack) Stack callStack = new Stack () ; SuppressWarnings(unchecked) Stack cloneStack = (Stack)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 (ListMap ds , String fun) try fun = f