一个中缀表达式转后缀表达式的算法的java的实现版本

spiniper

浏览: 5958 次
性别:
来自: 上海

最近访客更多访客>>

promiseloney

somefuture

asyuanbo

1354727604

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

学习历程

算法 java 编程中缀转后缀表达式计算

此文章献给那些正在编程道路上艰难学习探索的同行们或者未来的同行们。这是我自己实现的。
此算法被分为三个步骤：
• 对中缀表达式进行语法分析
• 中缀表达式到后缀表达式的转换
• 对后缀表达式求值
中缀表示法为：
(A+B)*C-D/(E+F)
此表示法是为人类所接受的表示法，通俗易懂，结构清晰
后缀表示法为：
AB+C*DEF+/-
此表示法为计算机易识别的表示法，如果不是脑部发达的天才，估计很难看懂。
然后是具体算法实现步骤：
1. 初始化一个空堆栈，将结果字符串变量置空。
2. 从左到右读入中缀表达式，每次一个字符。
3. 如果字符是操作数，将它添加到结果字符串。
4. 如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入（push）堆栈。
5. 如果字符是个开括号，把它压入堆栈。
6. 如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。
7. 如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。
这个许多地方已有相关文章，此处贴出来便于与我代码对照。
下面就是具体的代码实现了：
首先要分析中缀表达式包含哪些元素，如何完成计算过程，怎样方便扩展与抽象，然后怎样方便用户程序调用所实现的功能等......
第一步，确定客户程序如何最方便的调用我们写的工具，调用必须包含哪些元素：
用户程序调用必须有一个函数，函数必须传一个参数，就是表达式字符串，然后这个函数返回一个浮点型的计算结果，即是double result=object.method("xxxx");
然而这里首先要确定此处是个静态方法还是对象方法，我所选择的是对象方法，因为静态方法难以扩展，对象方法可以往对象中放入各种参数然实现不同形式的计算，因此此处使用的是对象方法，对此我建立一个类，不过在类建立之前我们需要建立包，这个包即是整个该功能承载的所有组件的包名，我命名此包为org.spiniper.commons.tool.expression。然后在此包下建立此组件核心类OperatorExpression也就是org.spiniper.commons.tool.expression.OperatorExpression，然后在此核心类下建立一个核心方法，此方法为唯一对外接口，其他客户程序通过此方法完成对所有组件的调用:
public double getDouble(String express)即是org.spiniper.commons.tool.expression.OperatorExpression:getDouble(Ljava.lang.String)D
有了主要对外的接口，接下来就要分析计算过程，算术的计算过程一般都是两个数与一个操作符来得到一个结果的方式，无论表达式多复杂，都可以拆成若干个如此的子运算，而子运算存在不同类型的运算方式（加、减、乘、除），因此运算是一个存在多态类型的抽象，因此定义一个字运算类型的接口org.spiniper.commons.tool.expression.operator.Operator,我命名其为运算符接口，此接口需定义一必须实现的方法，接口代码如下：

package org.spiniper.commons.tool.expression.operator;

/**
 * 此接口表示数学运算符类型。
 * @author 
 *
 */
public interface Operator {
	/**
	 * 运算符计算方式方法。
	 * @param x 左操作数。
	 * @param y 右操作数。
	 * @return 计算结果。
	 */
	long getLong(long x,long y);
	/**
	 * 运算符计算方式方法。
	 * @param x 左操作数。
	 * @param y 右操作数。
	 * @return 计算结果。
	 */
	double getDouble(double x,double y);
	/**
	 * 运算符所对应的算术符号。
	 * @return 运算符字符。
	 */
	char getFlag();
	/**
	 * 运算符所对应的数学名称。
	 * @return 运算符名称。
	 */
	String getMathName();
	/**
	 * 运算符的优先级，数值越高的优先级越高。
	 * @return 优先级数值。
	 */
	int getPriority();
	/**
	 * 是否为左结合操作符，跟运算符的结核性有关。
	 * @return true为左结合，false为由结合。
	 */
	boolean isLeftLink();
}

接口定义完成以后，我们就可以完成实现此接口对应的一些具体的运算符类，在此就不一一列出，只给一个加法的运算示例

package org.spiniper.commons.tool.expression.operator.commons;

import org.spiniper.commons.tool.expression.operator.Operator;

public class Addition implements Operator {

	public double getDouble(double x, double y) {
		return x+y;
	}

	public char getFlag() {
		return '+';
	}

	public long getLong(long x, long y) {
		return x+y;
	}

	public String getMathName() {
		return "+";
	}

	public int getPriority() {
		return 1;
	}
	
	public boolean isLeftLink() {
		return true;
	}

}

接下来就是算法的实现了，以下是类OperatorExpression的代码，此代码首先确定好构造方法，构造方法先要初始化一些基本的运算符方法，然后也需要能够添加新的运算符的构造方法，同时一些对运算符读写的方法也需要建立。在此实现中，我将中缀转后缀与计算结果的逻辑写在两个不同的方法中，代码如下：

package org.spiniper.commons.tool.expression;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import org.spiniper.commons.tool.Validator;
import org.spiniper.commons.tool.expression.exceptions.NotNumberException;
import org.spiniper.commons.tool.expression.exceptions.WrongExpressException;
import org.spiniper.commons.tool.expression.exceptions.WrongOperatorFlagException;
import org.spiniper.commons.tool.expression.function.Function;
import org.spiniper.commons.tool.expression.function.commons.Power;
import org.spiniper.commons.tool.expression.function.commons.Sin;
import org.spiniper.commons.tool.expression.operator.Operator;
import org.spiniper.commons.tool.expression.operator.commons.Addition;
import org.spiniper.commons.tool.expression.operator.commons.Division;
import org.spiniper.commons.tool.expression.operator.commons.Logarithm;
import org.spiniper.commons.tool.expression.operator.commons.Multiplication;
import org.spiniper.commons.tool.expression.operator.commons.PowerOf;
import org.spiniper.commons.tool.expression.operator.commons.Roots;
import org.spiniper.commons.tool.expression.operator.commons.Subtraction;
/**
 * 运算表达式操作对象，将表达式转化为其运算结果。
 * @author 。
 *
 */
public class OperatorExpression {
	
	public static final Pattern functionregex = Pattern.compile("((\\(|\\+|-|\\*|\\/)|^)(([_a-zA-Z]\\w*)\\((\\d+(.\\d+)?(,\\d+(.\\d+)?)*)\\))((\\)|\\+|-|\\*|\\/)|$)");
	
	public OperatorExpression(){
		this.operators=new HashMap<Character, Operator>();
		this.functions=new HashMap<String, Function>();
		try{
			this.putOperator(new Addition());
			this.putOperator(new Subtraction());
			this.putOperator(new Multiplication());
			this.putOperator(new Division());
			this.putOperator(new PowerOf());
			this.putOperator(new Roots());
			this.putOperator(new Logarithm());
			
			this.putFunction(new Power());
			this.putFunction(new Sin());
		}catch(Exception e){
			
		}
	}
	public OperatorExpression(Map<Character,Operator> operators){
		this.operators=operators;
	}
	private Map<Character, Operator> operators;
	private Map<String, Function> functions;
	static{
	}
	
	/**
	 * 获得表达式运算结果，结果类型为long类型
	 * @param expression 运算表达式字符串
	 * @return 运算结果
	 * @throws NotNumberException 当表达式的首字符不是数字或者括号时，抛出异常。
	 * @throws WrongExpressException 当运算表达式格式不正确时，抛出异常。
	 */
	public long getLong(String expression) throws NotNumberException,WrongExpressException{
		List<Object> list= this.infixToSuffix(expression);
		return (long)this.operator(list);
	}
	/**
	 * 获得表达式运算结果，结果类型为double类型
	 * @param expression 运算表达式字符串
	 * @return 运算结果
	 * @throws NotNumberException 当表达式的首字符不是数字或者括号时，抛出异常。
	 * @throws WrongExpressException 当运算表达式格式不正确时，抛出异常。
	 */
	public double getDouble(String expression) throws NotNumberException,WrongExpressException{
		List<Object> list= this.infixToSuffix(expression);
		return this.operator(list);
	}
	
	/**
	 * 添加新的运算符号以及运算方式。
	 * @param operator 运算符对象。
	 * @throws WrongOperatorFlagException 如果运算符对象的符号错误时抛出异常。
	 */
	public void putOperator(Operator operator) throws WrongOperatorFlagException{
		if(Validator.isNumber(String.valueOf(operator.getFlag()))){
			throw new WrongOperatorFlagException("不能以数字作为符号。");
		}
		this.operators.put(operator.getFlag(), operator);
	}
	
	public void putFunction(Function function) throws WrongOperatorFlagException{
		this.functions.put(function.getName(), function);
	}
	/**
	 * 判断某字符为合法运算符号。
	 * @param flag 运算符字符。
	 * @return true为合法符号，false为不合法符号。
	 */
	public boolean isFlag(char flag){
		Set<Character> set=this.operators.keySet();
		for (Character character : set) {
			if(flag==character.charValue()){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 根据字符获得已经使用的运算符对象。
	 * @param flag 运算符字符。
	 * @return 运算符对象。
	 */
	public Operator getOperator(char flag){
		return operators.get(flag);
	}
	/**
	 * 获得所有支持操作符
	 * @return 所有支持操作符
	 */
	public Map<Character, Operator> getOperators(){
		return (Map<Character, Operator>)((HashMap<Character, Operator>)operators).clone();
	}
	
	//将中缀表达式转化为后缀表达式。
	private List<Object> infixToSuffix(String expression) throws WrongExpressException{
		expression=this.parseFunExpress(expression);
		List<Object> result=new ArrayList<Object>();
		Stack<Character> operator=new Stack<Character>();
		StringBuffer numbers=new StringBuffer();
		char[]chars=expression.toCharArray();
		char readchar=0;
		for (int i = 0; i < chars.length; i++) {
			if(i==0&&!Validator.isNumber(String.valueOf(chars[i]))){
				if(chars[i]!='(')
				throw new NotNumberException("表达式格式不正确，首字符必须是数值");
			}
			if(Validator.isNumber(String.valueOf(chars[i]))){
				if(readchar==')'){
					throw new WrongExpressException("表达式格式不正确：第"+(i+1)+"个字符'"+chars[i]+"'出现错误，括号不能与数字连接。");
				}
				numbers.append(chars[i]);
			}else if(chars[i]=='.'){ 
				if(numbers.indexOf(".")!=-1){
					throw new NotNumberException("表达式格式不正确：第"+(i+1)+"个字符'"+chars[i]+"'出现错误，数字中出现两个小数点。");
				}
				if("".equals(numbers.toString())){
					throw new WrongExpressException("表达式格式不正确：第"+(i+1)+"个字符'"+chars[i]+"'出现错误，小数点前必须有数字");
				}
				numbers.append(chars[i]);
			}else if(isFlag(chars[i])){
				if(isFlag(readchar)){
					throw new WrongExpressException("表达式格式不正确，第"+(i+1)+"个字符'"+chars[i]+"'出现错误，计算符不能互相连接。");
				}
				if(readchar!=')'){
					result.add(numbers);
					numbers=new StringBuffer();
				}
				if(operator.isEmpty()){
					operator.push(chars[i]);
				}else{
					Operator nowoper=operators.get(chars[i]);
					char popchar=operator.peek();
					inner:
					while(1==1){
						if(popchar=='('){
							break inner;
						}
						if(nowoper.getPriority()>operators.get(popchar).getPriority()){
							break inner;
						}
						popchar=operator.pop();
						
						result.add(popchar);
						if(operator.isEmpty()){
							break inner;
						}
						popchar=operator.peek();
					}
					operator.push(chars[i]);
				}
			}else if(chars[i]=='('){
				if(Validator.isNumber(String.valueOf(readchar))){
					throw new WrongExpressException("表达式格式不正确：第"+(i+1)+"个字符'"+chars[i]+"'出现错误 括号不能与数字连接。");
				}
				if(readchar==')'){
					throw new WrongExpressException("表达式格式不正确：第"+(i+1)+"个字符'"+chars[i]+"'出现错误 异括号不能连接。");
				}
				operator.push(chars[i]);
			}else if(chars[i]==')'){
				if(readchar=='('){
					throw new WrongExpressException("表达式格式不正确：第"+(i+1)+"个字符'"+chars[i]+"'出现错误 异括号不能连接。");
				}
				if(isFlag(readchar)){
					throw new WrongExpressException("表达式格式不正确：第"+(i+1)+"个字符'"+chars[i]+"'出现错误 括号不能与数字连接。");
				}
				if(readchar!=')'){
					result.add(numbers);
					numbers=new StringBuffer();
				}
				char oper=operator.pop();
				inner:
				while(1==1){
					if(oper=='('){
						break inner;
					}
					if(operator.isEmpty()){
						throw new WrongExpressException("表达式格式不正确：第"+(i+1)+"个字符'"+chars[i]+"'出现错误 此闭括号没有追朔到开阔号。");
					}
					result.add(oper);
					oper=operator.pop();
				}
			}else{
				throw new WrongExpressException("表达式格式不正确：第"+(i+1)+"个字符'"+chars[i]+"'出现错误 非法的表达式字符。");
			}
			readchar=chars[i];
		}
		if(readchar!=')')
			result.add(numbers);
		while(1==1){
			if(operator.isEmpty()){
				break;
			}
			char oper=operator.pop();
			if(oper=='('){
				throw new WrongExpressException("表达式格式不正确：发现有括号没有闭合。");
			}
			result.add( oper);
		}
		return result;
	}
	
	//将后缀表达式计算出结果。
	private double operator(List<Object> suffixExpression) throws WrongExpressException{
		Stack<String> operator=new Stack<String>();
		for (int i = 0; i < suffixExpression.size(); i++) {
			Object obj=suffixExpression.get(i);
			if(obj instanceof StringBuffer){
				operator.push(obj.toString());
			}else if(obj instanceof Character){
				Operator oper=operators.get(obj);
				if(operator.isEmpty()){
					throw new WrongExpressException("表达式格式不正确：发现多余操作符");
				}
				double y=Double.parseDouble(operator.pop());
				if(operator.isEmpty()){
					throw new WrongExpressException("表达式格式不正确：发现多余操作符");
				}
				double x=Double.parseDouble(operator.pop());
				operator.push(String.valueOf(oper.getDouble(x, y)));
			}else{
				throw new WrongExpressException("表达式格式不正确：出现不兼容处理类型");
			}
		}
		double result=Double.parseDouble(operator.pop());
		if(!operator.isEmpty()){
			throw new WrongExpressException("表达式格式不正确：操作符不足");
		}
		return result;
	}
	
	public String parseFunExpress(String express) throws WrongExpressException{
		Matcher m=functionregex.matcher(express);
		while(m.find()){
			double res=this.execfunction(express.substring(m.start(),m.end()));
			String resstr="";
			if(res<0){
				resstr="(0"+String.valueOf(res)+")";
			}else{
				resstr=String.valueOf(res);
			}
			express=m.replaceFirst("$1 "+resstr+"$9");
			
			m=functionregex.matcher(express);
		}
		return express.replace(" ", "");
	}
	
	public double execfunction(String funstr) throws WrongExpressException{
		 Matcher m=functionregex.matcher(funstr);
		 if(!m.matches()){
			 throw new WrongExpressException("函数格式不正确");
		 }
		 String[]param=m.replaceAll("$5").split(",");
		 double []paramdouble=new double[param.length];
		 for (int i = 0; i < paramdouble.length; i++) {
			paramdouble[i]=Double.parseDouble(param[i]);
		 }
		 Function f=this.functions.get(m.replaceAll("$4"));
		 if(f==null){
			 throw new WrongExpressException("未找到对应函数");
		 }
		 return f.execute(paramdouble);
	}
}

在此其中，我自定义了一些异常，通常自定义一些异常来抛出不正确的输入给用户程序，让错误的程序不会继续执行，并提示客户程序有效的错误信息是很必要的，在此要说明，尽量不要抛出jdk的内置异常，这些异常并没有做什么特殊设计，完全可以自己实现。
这些代码中我初步实现了一些支持函数的代码，但函数并不支持表达式的嵌套运算，因为此示例仅供学习使用，因此也未做任何性能上的处理，只是简单的算法实现。关于函数接口的代码如下，同时提供一个简单的实现：

package org.spiniper.commons.tool.expression.function;

/**
 * 运算函数接口
 * @author spiniper
 *
 */
public interface Function {
	
	/**
	 * 执行函数体
	 * @param params 函数参数
	 * @return 执行结果
	 */
	public double execute(double[] params);
	
	/**
	 * 获得函数名称
	 * @return 函数名称
	 */
	public String getName();
	
	/**
	 * 参数个数
	 * @return 参数个数
	 */
	public int paramNum();
}

实现：

package org.spiniper.commons.tool.expression.function.commons;

import org.spiniper.commons.tool.expression.function.Function;

public class Power implements Function {

	public double execute(double[] params) {
		if(params.length<2){
			return 0;
		}
		return Math.pow(params[0], params[1]);
	}

	public String getName() {
		// TODO Auto-generated method stub
		return "power";
	}

	public int paramNum() {
		// TODO Auto-generated method stub
		return 2;
	}

}

分享到：