中缀表达式转后缀表达式

通过前面的逆波兰计算器的代码实现，可以看到：后缀表达式对于计算机来说很方便，但是对于人类来说，后缀表达式却不是那么容易写出来的。

中缀表达式转后缀表达式步骤：

1. 初始化两个栈：

   • 运算符栈：s1
   • 中间结果栈：s2

2. 从左到右扫描中缀表达式

3. 遇到操作数时，将其压入 s2

4. 遇到运算符时

   比较 它 与 s1 栈顶运算符的优先级：

   1. 如果 s1 为空，或则栈顶运算符号为 ( ，则将其压入符号栈 s1

   2. 如果：优先级比栈顶运算符 高，也将其压入符号栈 s1

   3. 如果：优先级比栈顶运算符 低 或 相等，将 s1 栈顶的运算符 弹出，并压入到 s2 中

   再重复第 4.1 步骤，与新的栈顶运算符比较（因为 4.3 将 s1 栈顶运算符弹出了）

   这里重复的步骤在实现的时候有点难以理解，下面进行解说：

   1. 如果 s1 栈顶符号 优先级比 当前符号 高或则等于，那么就将其 弹出，压入 s2 中（循环做，是只要 s1 不为空）

      如果栈顶符号为 (，优先级是 -1，就不会弹出，就跳出循环了

   2. 跳出循环后，则将当前符号压入 s1

5. 遇到括号时：

   1. 如果是左括号 ( ：则直接压入 s1

   2. 如果是右括号 )：

      则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到 左括号 为止，此时将这一对括号 丢弃

6. 重复步骤 2 到 5，直到表达式最右端

7. 将 s1 中的运算符依次弹出并压入 s2

8. 依次弹出 s2 中的元素并输出，结果的 逆序 即为：中缀表达式转后缀表达式

下面进行举例说明：

将中缀表达式：1+((2+3)*4)-5 转换为后缀表达式

扫描到的元素	s2 （栈底 -> 栈顶）	s1（栈底 -> 栈顶）	说明
1	1	空	遇到操作数，将其压入 s2
+	1	+	s1 栈为空，将其压入 s1
(	1	+ (	是左括号，压入 s1
(	1	+ ( (	是左括号，压入 s1
2	1 2	+ ( (	遇到操作数，将其压入 s2
+	1 2	+ ( ( +	遇到操作符：与 s1 栈顶运算符比较，为 (，将其压入 s1
3	1 2 3	+ ( ( +	遇到操作数，将其压入 s2
)	1 2 3 +	+ (	遇到右括号：弹出 s1 中的 + 压入 s2 中，这里去掉这一对小括号
*	1 2 3 +	+ ( *	遇到操作符：与 s1 栈顶比较，为 (，将其压入 s1 栈
4	1 2 3 + 4	+ ( *	遇到操作数：将其压入 s2
)	1 2 3 + 4 *	+	遇到右括号：弹出 s 1 中的 * 压入 s2 中，这里去掉这一队小括号
-	1 2 3 + 4 * +	-	遇到操作符：与 s1 栈顶比较，优先级一致，将 s1 中的 + 弹出，并压入 s2 中
5	1 2 3 + 4 * + 5	-	遇到操作数：将其压入 s2
	1 2 3 + 4 * + 5 -	空	解析完毕，将 s1 中的符号弹出并压入 s2 中

由于 s2 是一个栈，弹出是从栈顶弹出，因此逆序后结果就是 1 2 3 + 4 * + 5 -

一个疑问

老师，你怎么知道这个中缀表达式转后缀表达式的思路是这样的？

在学习和使用上有两个层次：

1. 应用层次：别人发明出来的东西，你学习、理解它，并灵活运用它
2. 自创：你自己发明一个东西出来，并使用它

那么这里的中缀转后缀表达式的思路步骤，则属于第一个层次，相关的计算机专家之类的，发明出来了。我们要理解它并灵活运用它。等你能力达到一定层度时，有可能发明出来一个算法。

再比如：绝世武功 -> 降龙十八掌，别人已经创造出来了，你不去学习理解它，如何加以改进并自创？如果没有人教你，你怎么能学会降龙十八掌？

代码实现

package cn.mrcode.study.dsalgtutorialdemo.datastructure.stack.calculator;

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

/**
 * 中缀表达式转后缀表达式
 */
public class InfixToSuffix {
    public static void main(String[] args) {
        InfixToSuffix infixToSuffix = new InfixToSuffix();
        // 目标：1+((2+3)*4)-5  转为 1 2 3 + 4 * + 5 -
        // 1. 将中缀表达式转成 List，方便在后续操作中获取数据
        String infixExpression = "1+((2+3)*4)-5";
        List<String> infixList = infixToSuffix.infix2List(infixExpression);
        System.out.println(infixList); // [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
        // 2. 将中缀表达式转成后缀表达式
        ArrayList<String> suffixList = infixToSuffix.infixList2SuffixList(infixList);
       System.out.println(suffixList); // [1, 2, 3, +, 4, *, +, 5, -]
    }


    /**
     * 将中缀表达式解析成单个元素的 List，
     *
     * @param infixExpression
     * @return 1+((2+3)*4)-5 -> [1,+,(,(,2,+,3,),*,4,),5]
     */
    public List<String> infix2List(String infixExpression) {
        ArrayList<String> res = new ArrayList<>();
        // 扫描并解析
        int index = 0;
        char ch = 0;
        String tempNum = ""; // 支持多位数
        while (index < infixExpression.length()) {
            ch = infixExpression.charAt(index++);
            // 如果不是数字，就是符号，直接添加到容器中
            // 0 = 48, 9 = 57
            if (!(ch >= 48 && ch <= 57)) {
                // 如果拼接的多位数还有值，则添加到容器中
                if (!tempNum.isEmpty()) {
                    res.add(tempNum);
                    tempNum = "";
                }
                res.add(ch + "");
                continue;
            }
            // 如果是数字，则考虑处理多位数
            tempNum += ch;
            // 如果已经是最后一个字符了，则将这个多位数添加到容器中
            if (index == infixExpression.length()) {
                res.add(tempNum);
                tempNum = "";
            }
        }
        return res;
    }

    /**
     * 中缀表达式 List 转为后缀表达式 List
     *
     * @param infixList
     * @return
     */
    private ArrayList<String> infixList2SuffixList(List<String> infixList) {
        // 符号栈
        Stack<String> s1 = new Stack<>();
        // 思路是使用栈来存储表达式元素
        // 仔细观察他的解析步骤，会发现：只是在入栈，并未出现出栈操作
        // 而且，最后的结果还要逆序，所以这里使用 list，直接顺序读取出来就是最后的结果了
        ArrayList<String> s2 = new ArrayList<>();

        for (String item : infixList) {
            // 如果是数字，则加入 s2
            if (item.matches("\\d+")) {
                s2.add(item);
            }
            // 如果是左括号，直接压入 s1
            else if (item.equals("(")) {
                s1.push(item);
            }
            // 如果是右括号
            // 则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到 左括号 为止，此时将这一对括号 丢弃
            else if (item.equals(")")) {
                // 如果不是左括号，则取出 s1 中的符号，添加到 s2 中
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                // 上面循环完之后，那么就是遇到了左括号
                // 则直接弹出这个左括号丢弃
                s1.pop();
            }
            // 剩下的则是运算符
            else {
                // 如果 s1 为空，或则栈顶运算符为 （，则压入符号栈 s1
                // 如果优先级比栈顶运算符 高，则压入符号栈 s1,否则，否则将 s1 栈顶的运算符弹出，压入 s2 中
                // 上面两句话，转换成下面的描述
                // 上面如果  s1 栈顶符号优先级比 当前符号高，则弹出加入到 s2 中。
                // 因为：如果栈顶符号是 （ 返回优先级为 -1.比当前符号低，则不会走该方法
                while (!s1.isEmpty() && priority(s1.peek().charAt(0)) >= priority(item.charAt(0))) {
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }
        // 将 s1 中的运算符依次弹出并加入 s2 中
        while (!s1.isEmpty()) {
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     * 计算操作符号优先级，暂时只支持 + - * /
     *
     * @param ch
     * @return 优先级越高，数值越大
     */
    private int priority(char ch) {
        switch (ch) {
            case '+':
            case '-':
                return 0;
            case '*':
            case '/':
                return 1;
            default:
                return -1;
        }
    }
}

测试输出

[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
[1, 2, 3, +, 4, *, +, 5, -]

可以看到，已经变成后缀表达式的顺序了。下面结合前面实现的逆波兰计算器来计算下这个表达式的结果

package cn.mrcode.study.dsalgtutorialdemo.datastructure.stack.calculator;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰计算器实现（后缀表达式）
 */
public class ReversePolishCalculatorTest {
    /**
     * 中缀表达式转后缀表达式，再给定计算器计算测试
     */
    @Test
    public void test2() {
        InfixToSuffix infixToSuffix = new InfixToSuffix();
        // 目标：1+((2+3)*4)-5  转为 1 2 3 + 4 * + 5 -
        // 1. 将中缀表达式转成 List，方便在后续操作中获取数据
        String infixExpression = "1+((2+3)*4)-5";
        List<String> infixList = infixToSuffix.infix2List(infixExpression);
        // 2. 将中缀表达式转成后缀表达式
        ArrayList<String> suffixList = infixToSuffix.infixList2SuffixList(infixList);
        System.out.println(suffixList); // [1, 2, 3, +, 4, *, +, 5, -]

        ReversePolishCalculator calculator = new ReversePolishCalculator();
        int res = calculator.start(suffixList);
        System.out.println(infixExpression + " = " + res);
    }
}

输出结果

[1, 2, 3, +, 4, *, +, 5, -]
1+((2+3)*4)-5 = 16

完整版逆波兰计算器

package cn.mrcode.study.dsalgtutorialdemo.datastructure.stack.calculator;

/**
 * <pre>
 * 完整版的逆波兰计算器，功能包括
 * 支持 + - * / ( )
 * 多位数，支持小数,
 * 兼容处理, 过滤任何空白字符，包括空格、制表符、换页符
 *
 * 逆波兰计算器完整版考虑的因素较多，下面给出完整版代码供同学们学习，其基本思路和前面一样，也是使用到：中缀表达式转后缀表达式。
 * </pre>
 */

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

public class ReversePolishMultiCalc {

    /**
     * 匹配 + - * / ( ) 运算符
     */
    static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";

    static final String LEFT = "(";
    static final String RIGHT = ")";
    static final String ADD = "+";
    static final String MINUS = "-";
    static final String TIMES = "*";
    static final String DIVISION = "/";

    /**
     * 加減 + -
     */
    static final int LEVEL_01 = 1;
    /**
     * 乘除 * /
     */
    static final int LEVEL_02 = 2;

    /**
     * 括号
     */
    static final int LEVEL_HIGH = Integer.MAX_VALUE;


    static Stack<String> stack = new Stack<>();
    static List<String> data = Collections.synchronizedList(new ArrayList<String>());

    /**
     * 去除所有空白符
     *
     * @param s
     * @return
     */
    public static String replaceAllBlank(String s) {
        // \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
        return s.replaceAll("\\s+", "");
    }

    /**
     * 判断是不是数字 int double long float
     *
     * @param s
     * @return
     */
    public static boolean isNumber(String s) {
        Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
        return pattern.matcher(s).matches();
    }

    /**
     * 判断是不是运算符
     *
     * @param s
     * @return
     */
    public static boolean isSymbol(String s) {
        return s.matches(SYMBOL);
    }

    /**
     * 匹配运算等级
     *
     * @param s
     * @return
     */
    public static int calcLevel(String s) {
        if ("+".equals(s) || "-".equals(s)) {
            return LEVEL_01;
        } else if ("*".equals(s) || "/".equals(s)) {
            return LEVEL_02;
        }
        return LEVEL_HIGH;
    }

    /**
     * 匹配
     *
     * @param s
     * @throws Exception
     */
    public static List<String> doMatch(String s) throws Exception {
        if (s == null || "".equals(s.trim())) throw new RuntimeException("data is empty");
        if (!isNumber(s.charAt(0) + "")) throw new RuntimeException("data illeagle,start not with a number");

        s = replaceAllBlank(s);

        String each;
        int start = 0;

        for (int i = 0; i < s.length(); i++) {
            if (isSymbol(s.charAt(i) + "")) {
                each = s.charAt(i) + "";
                //栈为空，(操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及是 ) 不能直接入栈
                if (stack.isEmpty() || LEFT.equals(each)
                        || ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)) {
                    stack.push(each);
                } else if (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())) {
                    //栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈
                    while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())) {
                        if (calcLevel(stack.peek()) == LEVEL_HIGH) {
                            break;
                        }
                        data.add(stack.pop());
                    }
                    stack.push(each);
                } else if (RIGHT.equals(each)) {
                    // ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈
                    while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())) {
                        if (LEVEL_HIGH == calcLevel(stack.peek())) {
                            stack.pop();
                            break;
                        }
                        data.add(stack.pop());
                    }
                }
                start = i;    //前一个运算符的位置
            } else if (i == s.length() - 1 || isSymbol(s.charAt(i + 1) + "")) {
                each = start == 0 ? s.substring(start, i + 1) : s.substring(start + 1, i + 1);
                if (isNumber(each)) {
                    data.add(each);
                    continue;
                }
                throw new RuntimeException("data not match number");
            }
        }
        //如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个stack 添加到队列
        Collections.reverse(stack);
        data.addAll(new ArrayList<>(stack));

        System.out.println(data);
        return data;
    }

    /**
     * 算出结果
     *
     * @param list
     * @return
     */
    public static Double doCalc(List<String> list) {
        Double d = 0d;
        if (list == null || list.isEmpty()) {
            return null;
        }
        if (list.size() == 1) {
            System.out.println(list);
            d = Double.valueOf(list.get(0));
            return d;
        }
        ArrayList<String> list1 = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            list1.add(list.get(i));
            if (isSymbol(list.get(i))) {
                Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
                list1.remove(i);
                list1.remove(i - 1);
                list1.set(i - 2, d1 + "");
                list1.addAll(list.subList(i + 1, list.size()));
                break;
            }
        }
        doCalc(list1);
        return d;
    }

    /**
     * 运算
     *
     * @param s1
     * @param s2
     * @param symbol
     * @return
     */
    public static Double doTheMath(String s1, String s2, String symbol) {
        Double result;
        switch (symbol) {
            case ADD:
                result = Double.valueOf(s1) + Double.valueOf(s2);
                break;
            case MINUS:
                result = Double.valueOf(s1) - Double.valueOf(s2);
                break;
            case TIMES:
                result = Double.valueOf(s1) * Double.valueOf(s2);
                break;
            case DIVISION:
                result = Double.valueOf(s1) / Double.valueOf(s2);
                break;
            default:
                result = null;
        }
        return result;

    }

    public static void main(String[] args) {
        //String math = "9+(3-1)*3+10/2";
        String math = "12.8 + (2 - 3.55)*4+10/5.0";
        try {
            doCalc(doMatch(math));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}