这么长的代码，还是放在github比较合适。改天再详细的对比着书上的章节认真分析，我觉得书上的说法是有问题的，按照书上的说法是无法完成 中缀表达式转 后缀表达式的。
package com.getqiu.datastructure;/** * have fun in reading bugs... * qiulimao@getqiu.com * */import java.lang.reflect.InvocationTargetException;import java.lang.reflect.Method;import java.util.*;import java.util.regex.Matcher;import java.util.regex.Pattern;/** * 运算符类 支持 +-*\/()<> * * */class Operator{ /** * 运算符号，字符串 * */ private String operationSymbol; /** * 运算符到对应函数计算的映射 * 比如 + 对应 add()运算 * -对应 minus() * */ private HashMap operatorToFunc = new HashMap<>(); /** * 运算符的优先级 * 比如 +的运算级为 1，-的运算等级和+一样，所以也可以是1， * 乘法运算优先级更高，可以为2 * */ private HashMap priority = new HashMap<>(); /** * 构造方法 * */ public Operator(String op) { this.operationSymbol = op; //加入方法映射 operatorToFunc.put("+","add"); operatorToFunc.put("-","minus"); operatorToFunc.put("*","times"); operatorToFunc.put("/","divide"); operatorToFunc.put("<","lower"); operatorToFunc.put(">","greater"); operatorToFunc.put("(","doNothing"); operatorToFunc.put(")","doNothing"); //加入优先级映射 priority.put("<",0); priority.put(">",0); priority.put("+",1); priority.put("-",1); priority.put("*",2); priority.put("/",2); priority.put("(",3); priority.put(")",3); } /** * 返回运算符 * */ public String getOperator() { return this.operationSymbol; } /** * 只要两者的运算符相等就考虑相等 * */ @Override public boolean equals(Object o) { if(! (o instanceof Operator)) { return false; } String operator = ((Operator)o).getOperator(); return operator.equals(operationSymbol); } /** * 返回当前运算符的 运算等级 * */ public int getPriority() { int p; p = priority.get(operationSymbol); return p; } /** * 根据当前类对应的运算符计算两个数相互运算的结果，采用反射 * 根据运算符找到对应的运算函数，然后做运算 * */ public int compute(int n1,int n2) { String toApplyMethodName = operatorToFunc.get(operationSymbol); try { Method toApplyMethod = this.getClass().getDeclaredMethod(toApplyMethodName,int.class,int.class); return (int)toApplyMethod.invoke(this,n1,n2); } catch (NoSuchMethodException|IllegalAccessException | InvocationTargetException e) { e.printStackTrace(); } return 0; } @Override public String toString() { return this.operationSymbol; } private int doNothing(int n1,int n2) { return 0; } private int add(int n1,int n2) { return n1 + n2; } private int minus(int n1, int n2) { return n1-n2; } private int times(int n1,int n2) { return n1*n2; } private int divide(int n1,int n2) { return n1/n2; } private int lower(int n1,int n2) { return n1>n2?1:0; } private int greater(int n1,int n2) { return n1 { private String subExpression; Pattern number = Pattern.compile("^(\\d+)"); Pattern basicOperator = Pattern.compile("^(\\+|-|\\*|/|<|>)"); Pattern bracket = Pattern.compile("^(\\(|\\))"); Pattern[] knownSymbolsPattern = {number,basicOperator,bracket}; Matcher[] matchers = new Matcher[3]; private int nextPointer = 0; public InputExpressionIterator(String expression) { //去除多余的空格，对于表达式前面有正负号的进行处理 this.subExpression = expression.replaceAll("\\s*","").replaceFirst("^\\+","0+").replaceFirst("^-","0-"); matchers[0] = knownSymbolsPattern[0].matcher(subExpression); matchers[1] = knownSymbolsPattern[1].matcher(subExpression); matchers[2] = knownSymbolsPattern[2].matcher(subExpression); } @Override public boolean hasNext() { return subExpression.length()>0; } @Override public String next() { /** * 轮流去匹配每个正则，匹配上了说明当前是 数字、运算符、括号的一种 * */ for(Matcher m:matchers) { m.reset(subExpression); if(m.find()) { String nextVal = m.group(); subExpression = subExpression.substring(nextVal.length()); return nextVal; } } //这种情况肯定是出错了，所以直接置空，跳出 subExpression = ""; return null; } } /** * 返回当前待运算表达式的迭代器 * */ public Iterator iterator(){ return new InputExpressionIterator(this.toCalculate); } /** * 根据当前类中的 toCalculate 计算表达式运算结果 * */ public int compute() { Iterator iterator = iterator(); //因为 计算后缀表达式需要把后缀转为 一个 数组，所以这里费了一些代码去把iterator转为数组， // 不知道这一步是不是有便捷的现成函数 ArrayList tmpList = new ArrayList<>(); while(iterator.hasNext()) { tmpList.add(iterator.next()); } String[] tmp = new String[tmpList.size()]; for(int i=0;i numberStack = new ArrayDeque<>(); for(String e: suffix) { if(isDigit(e)) { numberStack.push(Integer.valueOf(e)); } else { Operator currentOperator = new Operator(e); Integer numberSecond = numberStack.pop(); Integer numberFirst = numberStack.pop(); Integer tmpResult; tmpResult = currentOperator.compute(numberFirst,numberSecond); numberStack.push(tmpResult); } } return numberStack.pop(); } /** * 判断一个字符串是不是一个值 * */ private boolean isDigit(String var) { if(var.matches("^\\d+")) { return true; } return false; } /** * 根据中缀表达式 计算后缀表达式 * */ public String[] getSuffix(String[] theSymbols) { /** * 运算符的栈 * */ ArrayDeque operatorStack = new ArrayDeque<>(); /** * 存放后缀表达式 * */ ArrayList reversedExpression = new ArrayList<>(); Operator leftBracket = new Operator("("); Operator rightBracket = new Operator(")"); for(String e:theSymbols) { //是数字就直接添加进入 后缀表达式 if(isDigit(e)) { reversedExpression.add(e); } else {//不是数字，处理符号 if(operatorStack.isEmpty()) { //当前栈是空的，添加到运算符栈当中去 operatorStack.push(new Operator(e)); } else { //当前栈不是空的，需要和栈 的第一个元素比较 Operator currentOperator = new Operator(e); Operator previewsOperator = operatorStack.getFirst(); //如果当前处理的符号是右括号 if( currentOperator.equals(rightBracket) ) { while(! previewsOperator.equals(leftBracket)) {//只要还没到左括号，就一直弹出，知道遇到左括号 previewsOperator = operatorStack.pop(); reversedExpression.add(previewsOperator.toString()); if(operatorStack.isEmpty()) { break;//弹空了就跳出，别数组越界 } previewsOperator = operatorStack.getFirst(); } operatorStack.pop();//弹出最后的左括号 } else { //如果不是右括号 //第一个元素是通过getFirst得到的，因此再pop，还是这个元素，要想轮到下一个元素，那么 // pop之后，再用getFirst取下一个，如果不满足条件，那么这个元素可以不被弹出去。 while( (previewsOperator.getPriority() >= currentOperator.getPriority()) && !previewsOperator.equals(leftBracket)) { // 看看栈的第一个元素和当前运算符的优先级关系， // 栈中的运算符优先级高于和等于当前运算符优先级就出站（遇到左括号就不出了） previewsOperator = operatorStack.pop(); reversedExpression.add(previewsOperator.toString()); if(operatorStack.isEmpty()) { break;//同样，不要越界了 } previewsOperator = operatorStack.getFirst(); } //把这个符号压进去 operatorStack.push(currentOperator); } } } } Operator theRemainedOperator; //最后还有在栈当中的符号，需要弹出来 while(!operatorStack.isEmpty()) { theRemainedOperator = operatorStack.pop(); reversedExpression.add(theRemainedOperator.toString()); } String[] theResult = new String[reversedExpression.size()]; for(int i=0;i 这么长的代码，是没有人看的。