混合运算 后缀表达式算法实现

因为要用到四则混合运算，写了一个工具类，是基于后缀表达式的实现

 

package com.eden.door.util;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;



/**
 * 处理四则混合运算 , 支持负数+,-,*,/,%,^,括号
 * @author Eden
 *
 */
public class Calculator {
	private static Calculator instance = new Calculator() ;
	
	private String operators = "+-*/%^()#" ;
	
	//运算符栈外优先级
	private Map<String, Integer> icp = null ;
	//运算符栈内优先级
	private Map<String, Integer> isp = null ;
	
	public static Calculator newInstance(){
		return instance ;
	}
	
	public Calculator(){
		icp = new HashMap<String, Integer>();
		isp = new HashMap<String, Integer>();
		
		icp.put("#", 0) ;
		icp.put(")", 1) ;
		icp.put("+", 2) ;
		icp.put("-", 2) ;
		icp.put("*", 4) ;
		icp.put("/", 4) ;
		icp.put("%", 4) ;
		icp.put("^", 6) ;
		icp.put("(", 8) ;
		
		isp.put("#", 0) ;
		isp.put("(", 1) ;
		isp.put("+", 3) ;
		isp.put("-", 3) ;
		isp.put("*", 5) ;
		isp.put("/", 5) ;
		isp.put("%", 5) ;
		isp.put("^", 7) ;
		isp.put(")", 8) ;
	}
	/**
	 * 格式化表达式  ，有符号的，在前面加上0
	 * 例如(-2) + 3 格式化之后 (0-2) + 3
	 * @param exp 
	 * @return
	 */
	protected String formatExp(String exp) {
		
		String sign = "+-" ;
		StringBuilder sbExp = new StringBuilder(exp.trim().replace(" ", "")) ;
		
		if(sign.contains(sbExp.subSequence(0, 1))){
			sbExp.insert(0, "0") ;
		}
		for(int i = 0; i < sbExp.length(); i++) {
			if(sbExp.charAt(i) == '('){
				if(sign.contains(String.valueOf(sbExp.charAt(i+1)))){
					sbExp.insert(i+1, "0") ;
				}
			}
		}
		return sbExp.toString() ;
	}
	
	/**
	 * 判断字符是否为运算符
	 * @param c
	 * @return
	 */
	protected boolean isOperator(char c) {
		if(operators.contains(String.valueOf(c)))
			return true ;
		return false ;
	}
	protected boolean isOperator(String s){
		if(operators.contains(s))
			return true ;
		return false ;
	}
	

	
	/**
	 * 优先级的比较 
	 * @param currOp 当前运算符
	 * @param preOp 栈顶运算符
	 * @return 
	 * 当前运算符 > 栈顶运算符 返回 -1  
	 * 当前运算符 = 栈顶运算符 返回 0  
	 * 当前运算符 < 栈顶运算符 返回1 
	 */
	protected int opComp(String currOp , String preOp) {
		
		int currPriority = icp.get(currOp) ;
		int prePriority = isp.get(preOp) ;
		
		if( prePriority > currPriority )
			return 1 ;
		else if ( prePriority == currPriority ) {
			return 0;
		} else
			return -1 ;
	}
	
	/**
	 * 中缀表达式转换为后缀表达式
	 * @param infix
	 * @return
	 */
	protected List<String> infix2Postfix(String infix){
		List<String> postfixList = new ArrayList<String>() ;
		
		List<String> infixList = infixStr2List(infix) ;
		Deque<String> opStack = new ArrayDeque<String>() ;
		
		
		String str = "" ;
		for(int i = 0 ; i < infixList.size() ; i++){
			str = infixList.get(i) ;
			
			if(isOperator(str)){
				
				if( "(".equals(str) ){
					opStack.push(str) ;
				} 
				else if( ")".equals(str) ){
					while(!"(".equals(opStack.peek()) ){
						postfixList.add(opStack.pop()) ;
					}
					opStack.pop() ;
				}
				
				else if(opStack.peek() == null){
					opStack.push(str) ;
				} else {
					//如果栈顶运算符优先级比当前运算符优先级低将栈顶运算符弹邮放到后缀表达式中
					while( opStack.peek()!= null && opComp(str , opStack.peek()) >= 0 ){
						postfixList.add(opStack.pop()) ;
					}
					if(opStack.peek() == null){
						opStack.push(str) ;
					} 
					//如果栈顶运算符优先级比当前运算符优先级高压到后缀表达式中
					else if ( opComp(str , opStack.peek()) == -1 ) {
						opStack.push(str) ;
					}
				}
			} else {
				postfixList.add(str) ;
			}
		}
		//最后把栈中的运算符加到后缀表达式中
		while(opStack.peek() != null){
			postfixList.add(opStack.pop()) ;
		}
		
		return postfixList ;
	}
	
	/**
	 * 将中缀表达式字符串转换为中缀List
	 * @param infix
	 * @return
	 */
	protected List<String> infixStr2List(String infix){
		List<String> infixList = new ArrayList<String>() ;
		int start = 0 ;
		for(int i = 0 ; i < infix.length() ; i++){
			if(isOperator(infix.charAt(i)) ){
				if(i - start > 0){
					//截取两个运算 符之间的数字
					infixList.add(infix.substring(start , i) ) ;
				}
				start = i+1 ;
				//将运算符放到中缀表达式中
				infixList.add(infix.substring(i, i+1)) ;
			}
		}
		
		//如果最 后一位为数字
		if(start<infix.length()){
			infixList.add(infix.substring(start)) ;
		}
		return infixList ;
	}
	/**
	 * 计算运算表达式
	 * @param expression
	 * @return
	 */
	public double calculate(String expression) {
		//格式化运算式
		String infix = this.formatExp(expression) ;
		//求出中缀表达式
		List<String> infixList = infixStr2List(infix) ; 
		//得出后缀表达式
		List<String> postfixList = infix2Postfix(infix) ;
		
		System.out.println(infix) ;
		System.out.println(infixList) ;
		System.out.println(postfixList) ;
		
		//计算后缀表达式
		double r = computePostfix(postfixList) ;
		
		return r ;
	}
	
	/**
	 * 对后缀表达式求值
	 * @param postfixList
	 * @return
	 */
	protected double computePostfix(List<String> postfixList) {
		Deque<Double> rsStack = new ArrayDeque<Double>() ;
		
		double r = 0 ;
		for(String item : postfixList) {
			if(!isOperator(item)){
				rsStack.push(Double.parseDouble(item)) ;
			} else {
				double num1 = rsStack.pop() ;
				double num2 = rsStack.pop() ;
				
				if("+".equals(item)){
					r = num2 + num1 ;
				} else if("-".equals(item)){
					r = num2 - num1 ;
				} else if("*".equals(item)){
					r = num2 * num1 ;
				} else if("/".equals(item)){
					r = num2 / num1 ;
				} else if("%".equals(item)){
					r = num2 % num1 ;
				} else if("^".equals(item)){
					r = Math.pow(num2, num1) ;
				}
				
				rsStack.push(r) ;
			}
		}
		
		return rsStack.pop() ;
	}
	
	//测试
	public static void main(String[] args){
		
		String exp = "1/(0.3243e3) * ((-20 + 28) + (2 + 2))" ;
		
//		System.out.println( System.currentTimeMillis()) ;
		System.out.println(Calculator.newInstance().calculate(exp) ) ;
//		System.out.println( System.currentTimeMillis() ) ;
	}
}

 

        for(String item : postfixList) {
            if(!isOperator(item)){
                rsStack.push(Double.parseDouble(item)) ;
            } else {
                double num1 = rsStack.pop() ;
                double num2 = rsStack.pop() ;
               
                if("+".equals(item)){
                    r = num2 + num1 ;
                } else if("-".equals(item)){
                    r = num2 - num1 ;
                } else if("*".equals(item)){
                    r = num2 * num1 ;
                } else if("/".equals(item)){
                    r = num2 / num1 ;
                } else if("%".equals(item)){
                    r = num2 % num1 ;
                } else if("^".equals(item)){
                    r = Math.pow(num2, num1) ;
                }
               
                rsStack.push(r) ;
            }
        }
       
        return rsStack.pop() ;
    }
   
    //测试
    public static void main(String[] args){
       
        String exp = "1/(0.3243e3) * ((-20 + 28) + (2 + 2))" ;
       
//        System.out.println( System.currentTimeMillis()) ;
        System.out.println(Calculator.newInstance().calculate(exp) ) ;
//        System.out.println( System.currentTimeMillis() ) ;
    }
}