博客

一、简介

根据中缀表达式转后缀表达式的，实现了完整版的逆波兰计算器。可进行加减乘除和括号以及小数点的计算。实现原理如下：





以

1+((2+3)*4)-5

为例：

二、源代码

package stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.regex.Pattern;

// 逆波兰表达式完整版(可以匹配小数点)
public class PolandNotationFullVersion {
	
	//完成将一个中缀表达式转成后缀表达式的功能
	//说明
	//1. 1+((2+3)×4)-5 => 转成  1 2 3 + 4 × + 5 –
	//2. 因为直接对str 进行操作，不方便，因此 先将  "1+((2+3)×4)-5" =》 中缀的表达式对应的List
	//   即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
	//3. 将得到的中缀表达式对应的List => 后缀表达式对应的List
	//   即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]  =》 ArrayList [1,2,3,+,4,*,+,5,–]

	public static void main(String[] args) {
		String expression = "1+((2+3)*4)-5";
		List<String> expressionList = expressionSplit(expression);
		List<String> postfixExpression = postfixExpressionChange(expressionList);
		System.out.println("中缀转后缀表达式:"+postfixExpression);
		double ans = calculate(postfixExpression);
		System.out.println(expression + "=" + ans);
	}
	
	/*
		1.将字符串的表达式拆分开来，保存到List中，目的是为了方便后续的计算。
	*/
    public static List<String> expressionSplit(String str) {
    	List<String> expressionList = new ArrayList<String>();
    	String temp = "";
    	
    	for(int i=0;i<str.length();i++) {
    		char item = str.charAt(i);
    		
    		if(!numberJudge(item)) {
    			expressionList.add(String.valueOf(item));
    		}else if( item>= 48 && item<= 57 || item == 46) {
    			temp+= item;
    			if(i+1==str.length() || !numberJudge(str.charAt(i+1))) {
    				expressionList.add(String.valueOf(temp));
    				temp = "";
    			}
    		}else {
    			throw new RuntimeException("表达式格式不正确");
    		}
    	}
    	
    	return expressionList;
    }
    
	/*
		2. 根据规则，将中缀表达式转为后缀表达式。一个stack，一个List存储结果
	*/
    public static List<String> postfixExpressionChange(List<String> expressionSplited){
    	Stack<String> stack = new Stack<String>(); //存储符号
    	List<String> postfixExpression = new ArrayList<String>(); //存储后缀表达式
    	
    	for(String item : expressionSplited) {
    		if(numberJudge(item.toCharArray()[0])) {
    			postfixExpression.add(item);
    		}else {    			
    			// 初始状态，符号栈里面什么都没有
    			if(stack.size()==0) {
    				stack.push(item);
    			} else {
    				Operation oprCls = new Operation();
        			String lastOpr = stack.peek();
        			if(item.equals("(") || oprCls.oprPriority(item) > oprCls.oprPriority(lastOpr)) {
        				stack.push(item);
        			}else if(item.equals(")")) {
        				while(stack.size()>0 && !stack.peek().equals("(")) {
            				postfixExpression.add(stack.pop());
        				}
        				stack.pop();
        			}else {
        				postfixExpression.add(stack.pop());
        				stack.push(item);
        			}
        			lastOpr = "";
    			}
    		}
    	}
    	
    	while(stack.size()!=0) {
    		postfixExpression.add(stack.pop());
    	}
    	
    	return postfixExpression;
    }
    
    /*
	  	3.根据逆波兰表达式直接给计算器进行相应的计算
	 */
	public static Double calculate(List<String> list) {
		Stack<String> stack = new Stack<String>();
		
		for(String item : list) {
			
			if(item.matches("((\\d+)(\\.\\d+)?)")) {
				stack.push(item);
			}else {
				
				String num2Str = stack.pop();
				String num1Str = stack.pop();
				
				double num2 = Double.parseDouble(num2Str),
					num1 = Double.parseDouble(num1Str),
					ans = 0;
				
				if(item.equals("+")) {
					ans = num1 + num2;
				}else if(item.equals("-")) {
					ans = num1 - num2;
				}else if(item.equals("*")) {
					ans = num1 * num2;
				}else if(item.equals("/")) {
					ans = num1 / num2; 
				}
				
				stack.push("" + ans);
			}
		}
		
		return Double.parseDouble(stack.pop());
	}
	
	/*
	 * 4.定义一个方法，判断该字符是数字还是符号
	 */
	public static Boolean numberJudge(char ch) {
    	String oprRegEx = "[\\+\\-\\*\\/()]";
    	if(Pattern.matches(oprRegEx,String.valueOf(ch))) {
    		return false;
    	}
    	return true;
	}
}

class Operation {
	private int BRACKET = 0;
	private int ADD = 1;
	private int DELETE = 1;
	private int MULTIPLY = 2;
	private int DIVIDE = 2;
	
	public Integer oprPriority(String opr) {
		int result = 0;
		
		switch(opr) {
			case "+":
				result = ADD;
				break;
			case "-":
				result = DELETE;
				break;
			case "*":
				result = MULTIPLY;
				break;
			case "/":
				result = DIVIDE;
				break;
			default:
				result = BRACKET;
				break;
		}
		
		return result;
	}
}

三、结果