前言

最近在看数据结构，看到如此神奇的后缀表达式运用思想，于是就自己写代码实现了

一、原理

简单算术表达式是使用中缀表达式进行表达的，但是这样就无法解决表达式优先级问题，因此利用栈先进后出原理转换为后缀表达来解决简单算术表达式优先级问题。

二、使用步骤

1.中缀表达式转换为后缀表达式

遍历中缀表达式，数字则直接输出，（除括号外）符号则进栈，进栈前先判断栈顶元素的符号优先级和当前需要进栈的符号的优先级，如果栈顶符号优先级要高的话就栈顶元素先出栈输出，然后当前元素入栈,否则直接入栈。左括号直接入栈，因为优先规则最高，右括号则将栈元素一个一个出栈直到找到与之匹配的左括号。遍历完成后查看栈中是否还存在元素，如果存在则一个一个出栈输出。

2.计算结果

遍历后缀表达式，遇到符号就将符号前两个元素进行计算并保存计算后的结果删除两个计算元素

三、实现代码

1.启动类

代码如下（示例）：

public class CalculateTest {


    public static void main(String[] args) {

        System.out.println("请输入：（只支持+ - * / ( ) 符号 ）");
        Scanner scanner = new Scanner(System.in);
        String express = scanner.nextLine();

        express = express.replaceAll("\\("," ( ").replaceAll("\\)"," ) ")
                .replaceAll("\\+"," + ").replaceAll("-"," - ")
                .replaceAll("\\*"," * ").replaceAll("/"," / ");
        // 切割一个或多个空格
        String[] expressArray = express.split("\\s+");
        CalculateUtils.isValid(expressArray);
        BigDecimal result = CalculateUtils.calculate(CalculateUtils.translate(expressArray));

        System.out.println("结果：" + result.toString());

    }
}

2.工具类

代码如下（示例）：

public class CalculateUtils {

    private static final Map<String, SymbolInterface> SYMBOL_STRATEGY_MAP;
    private static final List<String> CALCULATE_SYMBOL_LIST = SymbolConstants.getCalculateSymbol();


    static {
        SYMBOL_STRATEGY_MAP = new HashMap<>(8);
        SYMBOL_STRATEGY_MAP.put(SymbolConstants.LEFT_PARENTHESIS_SYMBOL, new LeftParenthesisSymbolStrategy());
        SYMBOL_STRATEGY_MAP.put(SymbolConstants.RIGHT_PARENTHESIS_SYMBOL, new RightParenthesisSymbolStrategy());
        SYMBOL_STRATEGY_MAP.put(SymbolConstants.PLUS_SYMBOL, new PlusOrSubtractionSymbolStrategy());
        SYMBOL_STRATEGY_MAP.put(SymbolConstants.SUBTRACTION_SYMBOL, new PlusOrSubtractionSymbolStrategy());
        SYMBOL_STRATEGY_MAP.put(SymbolConstants.MULTIPLICATION_SYMBOL, new MultiplicationOrDivisionSymbolStrategy());
        SYMBOL_STRATEGY_MAP.put(SymbolConstants.DIVISION_SYMBOL, new MultiplicationOrDivisionSymbolStrategy());
    }


    /**
     * 校验字符是否输入合法
     *
     * @param expressArray
     */
    public static void isValid(String[] expressArray) {

        int lengthFlag = 3;
        int leftParenthesisCount = 0;
        int rightParenthesisCount = 0;
        int specialCount = 0;
        for (String express : expressArray) {
            if (express.equals(SymbolConstants.LEFT_PARENTHESIS_SYMBOL)) {
                leftParenthesisCount++;
                specialCount++;
            } else if (express.equals(SymbolConstants.RIGHT_PARENTHESIS_SYMBOL)) {
                rightParenthesisCount++;
                specialCount++;
            }
            if (CALCULATE_SYMBOL_LIST.contains(express)) {
                specialCount++;
            }
        }
        if (leftParenthesisCount != rightParenthesisCount) {
            throw new RuntimeException("表达式异常");
        }
        int numberCount = expressArray.length - specialCount;
        int calculateSymbolCount = specialCount - leftParenthesisCount - rightParenthesisCount;
        if (numberCount - calculateSymbolCount != 1) {
            throw new RuntimeException("表达式异常");
        }
        if (expressArray.length < lengthFlag) {
            throw new RuntimeException("表达式异常");
        }
    }

    /**
     * 中缀表达式 转换为后缀表达式
     *
     * @param expressArray
     * @return
     */
    public static LinkedList<String> translate(String[] expressArray) {
        // 初始化栈大小
        Stack<String> stack = new Stack<>();

        LinkedList<String> suffixLinkedList = Lists.newLinkedList();

        for (String temp : expressArray) {
            boolean numberFlag = isNumber(temp);
            if (numberFlag) {
                suffixLinkedList.add(temp);
                continue;
            }
            SymbolInterface symbolInterface = SYMBOL_STRATEGY_MAP.get(temp);
            if (null == symbolInterface) {
                throw new RuntimeException("不支持该字符计算");
            }
            if (stack.isEmpty()) {
                stack.push(temp);
            } else {
                symbolInterface.operate(stack, suffixLinkedList, temp);
            }
        }
        while (!stack.isEmpty()) {
            String pop = stack.pop();
            suffixLinkedList.add(pop);
        }


        return suffixLinkedList;
    }

    /**
     * 校验是否是数字
     *
     * @param express
     * @return
     */
    public static Boolean isNumber(String express) {
        boolean hasDecimal = express.contains(".");
        if (hasDecimal) {
            String[] integerAndDecimal = express.split("\\.");
            int decimalFlag = 2;
            if (integerAndDecimal.length != decimalFlag) {
                throw new RuntimeException("表达式异常");
            }
            boolean isInteger = isNumber(integerAndDecimal[0]);
            boolean isDecimal = isNumber(integerAndDecimal[1]);
            if (!isInteger || !isDecimal) {
                throw new RuntimeException("表达式异常");
            }
        }
        for (Character temp : express.toCharArray()) {
            if (!Character.isDigit(temp) && express.length() > 1) {
                throw new RuntimeException("表达式异常");
            } else if (!Character.isDigit(temp) && express.length() == 1) {
                return false;
            }
        }

        return true;
    }

    /**
     * 计算结果
     *
     * @param list
     * @return
     */
    public static BigDecimal calculate(LinkedList<String> list) {


        for (int i = 2; i < list.size(); i++) {
            // list.get(i) 内部是循环获取
            String express = list.get(i);
            if (CALCULATE_SYMBOL_LIST.contains(express)) {
                String pre = list.get(i - 1);
                String prePre = list.get(i - 2);
                SymbolInterface symbolInterface = SYMBOL_STRATEGY_MAP.get(express);
                if (null == symbolInterface) {
                    throw new RuntimeException("不支持该字符计算");
                }
                String result = symbolInterface.calculate(pre, prePre, express);
                list.set(i - 2, result);
                // 清除计算的两个元素
                list.remove(i - 1);
                list.remove(i - 1);
                // 复原下标
                i = 1;

            }
        }


        return new BigDecimal(list.get(0));
    }
}

3.策略类

代码如下（示例）：

/**
 * 中缀表达式转换为后缀表达式时各符号策略接口
 *
 */
public interface SymbolInterface {

    /**
     * 符号进栈出栈操作
     *
     * @param stack
     * @param suffixList
     * @param express
     */
    void operate(Stack<String> stack, LinkedList<String> suffixList, String express);

    /**
     * 计算
     *
     * @param left
     * @param right
     * @param express
     * @return
     */
    String calculate(String left, String right, String express);

}



/**
 * 左括号策略
 */
public class LeftParenthesisSymbolStrategy implements SymbolInterface {
    @Override
    public void operate(Stack<String> stack, LinkedList<String> suffixList, String express) {
        // 左括号优先级最高 直接入栈
        stack.push(express);
    }

    @Override
    public String calculate(String left, String right, String express) {
        return null;
    }


}
/**
 * 乘除策略
 */
public class MultiplicationOrDivisionSymbolStrategy implements SymbolInterface {
    @Override
    public void operate(Stack<String> stack, LinkedList<String> suffixList, String express) {
        // 获取栈顶元素
        String peek = stack.peek();
        if (peek.equals(SymbolConstants.LEFT_PARENTHESIS_SYMBOL) || peek.equals(SymbolConstants.SUBTRACTION_SYMBOL) || peek.equals(SymbolConstants.PLUS_SYMBOL)) {
            stack.push(express);
        } else {
            String pop = stack.pop();
            stack.push(express);
            suffixList.add(pop);
        }

    }

    @Override
    public String calculate(String left, String right, String express) {
        BigDecimal result;
        BigDecimal rightBigDecimal = new BigDecimal(right);
        BigDecimal leftBigDecimal = new BigDecimal(left);
        if (express.equals(SymbolConstants.MULTIPLICATION_SYMBOL)) {
            result = leftBigDecimal.multiply(rightBigDecimal);
        } else {
            int zero = 0;
            if (zero == rightBigDecimal.signum()) {
                throw new RuntimeException("表达式异常");
            }
            result = rightBigDecimal.divide(leftBigDecimal, 2, BigDecimal.ROUND_HALF_UP);
        }
        return result.toString();
    }


}
/**
 * 加减策略
 */
public class PlusOrSubtractionSymbolStrategy implements SymbolInterface {
    @Override
    public void operate(Stack<String> stack, LinkedList<String> suffixList, String express) {
        // 获取栈顶元素
        String peek = stack.peek();
        if (peek.equals(SymbolConstants.LEFT_PARENTHESIS_SYMBOL)) {
            stack.push(express);
        } else {
            String pop = stack.pop();
            stack.push(express);
            suffixList.add(pop);
        }

    }

    @Override
    public String calculate(String left, String right, String express) {
        BigDecimal result ;
        if(express.equals(SymbolConstants.SUBTRACTION_SYMBOL)){
            result =  new BigDecimal(left) .subtract(new BigDecimal(right));
        }else{
            result =  new BigDecimal(left) .add(new BigDecimal(right));
        }
        return result.toString();
    }
}

/**
 * 右括号策略
 */
public class RightParenthesisSymbolStrategy implements SymbolInterface {
    @Override
    public void operate(Stack<String> stack, LinkedList<String> suffixList, String express) {
        // 获取栈顶元素
        while (!stack.isEmpty() && !stack.peek().equals(SymbolConstants.LEFT_PARENTHESIS_SYMBOL)) {
            String pop = stack.pop();
            suffixList.add(pop);
        }
        if (!stack.isEmpty() && stack.peek().equals(SymbolConstants.LEFT_PARENTHESIS_SYMBOL)) {
            stack.pop();
            return;
        }
    }

    @Override
    public String calculate(String left, String right, String express) {
        return null;
    }


}

4.常量类

代码如下（示例）：

/**
 * 符号常量
 */
public final class SymbolConstants {
    /**
     * 乘号
     */
    public static final String MULTIPLICATION_SYMBOL = "*";
    /**
     * 除号
     */
    public static final String DIVISION_SYMBOL = "/";

    /**
     * 加号
     */
    public static final String PLUS_SYMBOL = "+";

    /**
     * 减号
     */
    public static final String SUBTRACTION_SYMBOL = "-";

    /**
     * 左括号
     */
    public static final String LEFT_PARENTHESIS_SYMBOL = "(";

    /**
     * 右括号
     */
    public static final String RIGHT_PARENTHESIS_SYMBOL = ")";

    /**
     * 获取计算符号
     *
     * @return
     */
    public static List<String> getCalculateSymbol() {
        List<String> list = Lists.newArrayListWithExpectedSize(4);
        list.add(MULTIPLICATION_SYMBOL);
        list.add(DIVISION_SYMBOL);
        list.add(PLUS_SYMBOL);
        list.add(SUBTRACTION_SYMBOL);
        return list;
    }


}

总结

如何保持对这一行业的热爱，就是不断的将想法付出实践。

努力了的才叫梦想，不努力的就是空想！如果你一直空想的话，无论看多少正能量语录，也赶不走满满的负能量！你还是原地踏步的你，一直在看别人进步的你。