完整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 StackString convertToPostfix (StringSplit x) { String s = x.getNext () ; StackString st = new StackString () ; StackString rSt = new StackString () ; 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